【C++进阶】：红黑树

红黑树

  • 一.红黑树简单实现
    • 1.性质
    • 二.更新颜色
      • 1.情况一
      • 2.情况二
      • 3.情况三
    • 3.完整代码(代码有注释，稍微画图很容易理解,旋转部分可以看我的AVL树博客)
  • 二.map和set
    • 1.基本实现
    • 2.迭代器

一.红黑树简单实现

1.性质

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

  1. 每个结点不是红色就是黑色。
  2. 根节点是黑色的。
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的。
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点）。

创建节点

在这里插入图片描述

在这里插入图片描述

二.更新颜色

1.情况一

插入一个节点，它的父亲是红色的并且它有叔叔且叔叔也是红色的。

在这里插入图片描述

2.情况二

如果叔叔不存在

在这里插入图片描述
此时单纯的变色是无法解决问题的，需要进行旋转，在此情况是右旋。

在这里插入图片描述

3.情况三

叔叔存在且为黑，注意此时插入的点是在最下面，cur经过上面的转变后到达图示的位置。

在这里插入图片描述

在这里插入图片描述

3.完整代码(代码有注释，稍微画图很容易理解,旋转部分可以看我的AVL树博客)

测试

#include"RBTree.h"
#include<vector>int main()
{RBTree<int, int> t;srand(time(0));vector<int>a;for (int i = 0; i < 100; i++){int x = rand();a.push_back(x);}for (auto x : a)t.Insert(make_pair(x, x));cout << t.IsBalance() << endl;return 0;
}

树

#include<iostream>
#include<assert.h>
using namespace std;enum Color
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;RBTreeNode(const pair<K,V>& kv)//初始化节点:_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}Color _col;
};template<class K,class V>
class RBTree
{
public:typedef RBTreeNode<K, V> Node;bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根为黑色return true;}Node* parent = _root;Node* cur = _root;//一般的搜索二叉树插入while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(kv);cur->_parent = parent;if (parent->_kv > kv) parent->_left = cur;else parent->_right = cur;//进行颜色更新while (parent && parent->_col == RED){Node* grandparent = parent->_parent;Node* uncle;//找到叔叔if (grandparent->_left == parent)uncle = grandparent->_right;elseuncle = grandparent->_left;//如果叔叔存在且为红色if (uncle && uncle->_col == RED){//变颜色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续向上cur = grandparent;parent = cur->_parent;}//如果叔叔不存在或者是黑色else{//parent是左，cur是左，进行右单旋if (grandparent->_left == parent && parent->_left == cur){RotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}//parent是左，cur是右，进行左右旋else if (grandparent->_left == parent && parent->_right == cur){RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}//parent是右,cur是右,进行左单旋else if (grandparent->_right == parent && parent->_right == cur){RotateL(grandparent);grandparent->_col = RED;parent->_col = BLACK;}//parent是右，cur是左,进行右左旋else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}}}_root->_col = BLACK;}//旋转函数void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;//记录父节点的父节点//父节点的右孩子变成curleftparent->_right = curleft;if (curleft)//细节注意curleft为空时不能操作curleft->_parent = parent;//父节点变为cur的左孩子cur->_left = parent;parent->_parent = cur;//如果原来父节点是根节点if (parent == _root){_root = cur;cur->_parent = nullptr;}else//如果不是根节点判断它应该是左儿子还是右儿子{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* pphead = parent->_parent;//父节点到cur右边cur->_right = parent;parent->_parent = cur;//父节点的左孩子变成currightparent->_left = curright;if (curright)curright->_parent = parent;//cur的父节点变为原来父节点的父节点if (pphead)//如果不是根节点{if (pphead->_left == parent)pphead->_left = cur;elsepphead->_right = cur;cur->_parent = pphead;}else{_root = cur;cur->_parent = nullptr;}}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;RotateR(parent->_right);RotateL(parent);}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;RotateL(parent->_left);RotateR(parent);}//测试是否出问题bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){//根是否为黑色if (_root->_col != BLACK){cout << "根不是红色"<<endl;return false;}int blackcheck = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)blackcheck++;cur = cur->_left;}//判断是否有两个连续的红色和每条路径的黑色是否相同return CheckColor(_root,blackcheck,0);}bool CheckColor(Node*root,int blackcheck,int blacknum){if (root == nullptr){//检查是否每条路径的黑色相同if (blackcheck != blacknum){cout << "路径上黑色个数不同" << ' ';return false;}return true;}//判断是否有两个连续的红色Node* parent = root->_parent;if (root->_col == RED){if (parent && parent->_col == RED){cout << "有连续的红色" << ' ';return false;}}if (root->_col == BLACK) blacknum++;return CheckColor(root->_left, blackcheck, blacknum)&& CheckColor(root->_right, blackcheck, blacknum);}
private:Node* _root = nullptr;
};

二.map和set

1.基本实现

map和set虽然功能不同，但在库里都是使用红黑树实现的，接下来对红黑树的代码进行改造。在库里，set和map走的是泛型，也就是map和set可以使用同一份红黑树代码。

对红黑树进行泛化处理，方便之后传参

在这里插入图片描述

这里有一个问题：对于data，如果是set那么我们可以直接比较，但如果是map呢？map的T是一个pair，我们是不能直接比较的，为了解决这个问题，我们可以使用仿函数（如果不了解可以看看我的仿函数这篇博客）。

map里返回pair的firist
在这里插入图片描述

set为了保持一致，直接返回key
在这里插入图片描述

在树里创建一个对象，用该对象的规则进行比较
在这里插入图片描述

分别对map和set加入插入操作

在这里插入图片描述

在这里插入图片描述

2.迭代器

首先需要明确迭代器的功能，就是能够将整棵树进行中序遍历。

在这里插入图片描述

我们需要++，*，–，!=等操作。对于++操作，我们需要进行中序遍历。

在这里插入图片描述

在这里插入图片描述

其他一些小功能就不细说，下面是完整代码

RBTree.h

#pragma once
#include<iostream>
using namespace std;enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};template<class T>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T> Self;Node* _node;__TreeIterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_right){// 右树的最左节点(最小节点)Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{Node* cur = _node;Node* parent = cur->_parent;// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点while (parent){if (cur == parent->_left){break;}else{cur = cur->_parent;parent = parent->_parent;}}_node = parent;}return *this;}
};// set->RBTree<K, K, SetKeyOfT> _t;
// map->RBTree<K, pair<K, V>, MapKeyOfT> _t;template<class K, class T, class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator<T> iterator;// const_iteratoriterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}Node* Find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data);cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}private:Node* _root = nullptr;public:int _rotateCount = 0;
};

Map.h

#include"RBTree.h"namespace Mine
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const K& key);bool insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};
}

Set.h

#include"RBTree.h"namespace Mine
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/131256.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

中国各省市相关图标

中国各省市相关图标

中国各省市相关图标
阅读更多...
长胜证券：政策东风频吹 慢牛格局或已打开

长胜证券：政策东风频吹 慢牛格局或已打开

长胜证券认为&#xff0c;目前商场遭到央行社融数据提振&#xff0c;全体预期出现了必定的回暖&#xff0c;经济运行的部分不确定性得以落地&#xff0c;8月社融数据作为先行指标提振了出资者信心。操作上看出资者可逐步加大仓位&#xff0c;选择前期调整较为充沛&#xff0c;有…
阅读更多...
代码随想录算法训练营day50|123.买卖股票的最佳时机III|188.买卖股票的最佳时机IV

代码随想录算法训练营day50|123.买卖股票的最佳时机III|188.买卖股票的最佳时机IV

123.买卖股票的最佳时机III 力扣题目链接 给定一个数组&#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意&#xff1a;你不能同时参与多笔交易&#xff08;你必须在再次购买前出售掉…
阅读更多...
网络爬虫-----初识爬虫

网络爬虫-----初识爬虫

目录 1. 什么是爬虫&#xff1f; 1.1 初识网络爬虫 1.1.1 百度新闻案例说明 1.1.2 网站排名&#xff08;访问权重pv&#xff09; 2. 爬虫的领域&#xff08;为什么学习爬虫 ?&#xff09; 2.1 数据的来源 2.2 爬虫等于黑客吗&#xff1f; 2.3 大数据和爬虫又有啥关系&…
阅读更多...
el-select数据过多的解决（纯前端）

el-select数据过多的解决（纯前端）

前言 el-select数据过多这个问题应该很多人都遇到过&#xff0c;在生产环境中数据几百、几千条是比较常见的。当数据过多时&#xff0c;就会造成浏览器卡顿&#xff0c;如果客户电脑性能不行&#xff0c;浏览器直接卡死也有可能。 解决 先说一下现在项目中遇到的两种解决方案…
阅读更多...
python-爬虫-urllib3

python-爬虫-urllib3

导入模块 import urllib3urllib3&#xff1a;功能强大、条理清晰、用于HTTP客户端的python网络请求库 重要特征 1.线程安全 2.连接池 3.客户端SSL/TLS验证 4.使用分段编码长传文件 5.重试请求和处理HTTP复位的助手 6.支持gzip和deflate编码 7.HTTP和SOCKS的代理支持 8.100%的…
阅读更多...
认识网线上的各种参数标号

认识网线上的各种参数标号

最近工作需要&#xff0c;接触了很多不同类型的网线&#xff0c;为了能够区分不同型号的网线&#xff0c;特意做一篇笔记用来学习&#xff0c;如有记录有误之处&#xff0c;欢迎大家指正~初步认识网线 常用的网络电缆有三种&#xff1a;双绞线、同轴电缆和光纤电缆&#xff08…
阅读更多...
uni-app 之 uni.request 网络请求API接口

uni-app 之 uni.request 网络请求API接口

uni-app 之 uni.request 网络请求API接口 image.png <template><!-- vue2的<template>里必须要有一个盒子&#xff0c;不能有两个&#xff0c;这里的盒子就是 view--><view>--- uni.request 网络请求API接口 ---<view><!-- 免费的测试接口 --…
阅读更多...
Java线上故障排查（CPU、磁盘、内存、网络、GC）+JVM性能调优监控工具+JVM常用参数和命令

Java线上故障排查（CPU、磁盘、内存、网络、GC）+JVM性能调优监控工具+JVM常用参数和命令

CPU/堆/类/线程 根据服务部署和项目架构&#xff0c;从如下几个方面排查&#xff1a; &#xff08;1&#xff09;运用服务器&#xff1a;排查内存&#xff0c;cpu,请求数等&#xff1b; &#xff08;2&#xff09;文件图片服务器&#xff1a;排查内存&#xff0c;cpu,请求数等…
阅读更多...
Gateway网关

Gateway网关

本章目标 学习目标 1、服务网关 Gateway 2、ServerWebExchange 服务网关Gateway API 网关是一个服务&#xff0c;是系统的唯一入口。从面向对象设计的角度看&#xff0c;它与外观模式类似。API 网关封装了系统内部架构&#xff0c;为每个客户端提供一个定制的 API 。它可能…
阅读更多...
docker 方式安装mysql 主从方式keepalived实现高可用

docker 方式安装mysql 主从方式keepalived实现高可用

一、环境介绍 二、MySQL安装 在两台服务器上都安装mysql 1、拉取镜像 docker pull mysql:8.0.272、创建挂载目录 mkdir -p /data/mysql/3、运行容器 主节点 docker run \--restartalways \--name master_mysql -p 3306:3306 \-e MYSQL_ROOT_PASSWORD123456 -d \-v /data/m…
阅读更多...
FPGA开发

FPGA开发

https://www.enclustra.com.cn/?bd_vid11435475462206745180 https://www.monolithicpower.cn/design-tools/design-tools/llc-design-tool.html https://www.elecfans.com/article/88/143/2012/20120718280641_2.html
阅读更多...
HTTP协议初识·下篇

HTTP协议初识·下篇

介绍 承接上篇&#xff1a;HTTP协议初识中篇_清风玉骨的博客-CSDN博客 本篇内容&#xff1a; 长链接 网络病毒 cookie使用&session介绍 基本工具介绍 postman 模拟客户端请求 fiddler 本地抓包的软件 https介绍 https协议原理 为什么加密 怎么加密 CA证书介绍 数字签名介绍…
阅读更多...
阿里后端开发：抽象建模经典案例【文末送书】

阿里后端开发：抽象建模经典案例【文末送书】

文章目录 写作前面1.抽象思维2.软件世界中的抽象3. 经典抽象案例4. 抽象并非一蹴而就&#xff01;需要不断假设、验证、完善5. 推荐一本书 写作末尾 写作前面 在互联网行业&#xff0c;软件工程师面对的产品需求大都是以具象的现实世界事物概念来描述的&#xff0c;遵循的是人…
阅读更多...
Tomcat多实例部署和动静分离

Tomcat多实例部署和动静分离

一、多实例部署&#xff1a; 多实例&#xff1a;多实例就是在一台服务器上同时开启多个不同的服务端口&#xff0c;同时运行多个服务进程&#xff0c;这些服务进程通过不同的socket监听不同的服务端口来提供服务。 1.前期准备&#xff1a; 1.关闭防火墙&#xff1a;systemctl …
阅读更多...
Docker部署Canal监听MySQL binlog

Docker部署Canal监听MySQL binlog

文章目录 概念简述binlogCanal MySQL配置Canal配置创建挂载目录设置权限创建MySQl的Canal账户拉取镜像运行容器简单运行配置文件复制到宿主机修改配置文件删除之前运行的canal容器正式运行Canal容器 查看运行状态排查问题 概念简述 binlog MySQL的二进制日志binlog可以说是My…
阅读更多...
揭秘跑腿小程序开发中的5个关键技巧，让你的应用一炮而红

揭秘跑腿小程序开发中的5个关键技巧，让你的应用一炮而红

作为专注于跑腿小程序开发多年的领域专家&#xff0c;我深知在如今激烈的市场竞争中&#xff0c;如何打造一个引人注目且成功的跑腿小程序是至关重要的。在本文中&#xff0c;我将为大家揭秘跑腿小程序开发中的5个关键技巧&#xff0c;助你的应用一炮而红。无论你是一个初学者还…
阅读更多...
【Fiddler】mac m1 机器上使用 fiddler 抓取接口

【Fiddler】mac m1 机器上使用 fiddler 抓取接口

mac m1 机器上使用 fiddler 抓取接口&#xff08;非虚拟机模式&#xff09; author: jwensh date:2023.09.12 文章目录 mac m1 机器上使用 fiddler 抓取接口&#xff08;非虚拟机模式&#xff09;1. 环境准备2. 进行配置3. 使用情况 1. 环境准备 想要抓取 mac 上浏览器的接口&a…
阅读更多...
快速傅里叶变换

快速傅里叶变换

引言 目标 傅里叶变化&#xff08;Fourier transform&#xff09;是一种信号处理技术&#xff0c;它可以将时间信号转换为频率信号&#xff0c;即将一组具有相同数量频率的正弦波叠加在一起&#xff0c;形成一组新的正弦波。如果我们把时间信号从频域转换到时域&#xff0c;那么…
阅读更多...
酷开科技打造更好体验服务用户

酷开科技打造更好体验服务用户

智能电视以其海量资源、智慧大屏、高清画质等特点在国内快速普及。然而&#xff0c;随着用户量的增加、用户群体的需求多元化&#xff0c;导致消费者对智能电视的应用要求越来越高&#xff0c;不仅希望智能电视内容丰富&#xff0c;最好还能拥有“多合一”的功能。 好在&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023