当前位置： 首页 > web >正文

C++_红黑树树

web 2025/7/30 14:15:57

1红黑树的概念

 AVL树和红黑树的比较

想出AVL树的人时大佬，想出红黑树的人是天才

他俩的性能是同一量级的，但是AVL树的严格平衡时要付出代价的，插入和删除的时候会大量旋转

 AVL树维持那么高的精度是没有必要的

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

 

2 红黑树的性质和定义

1. 每个结点不是红色就是黑色

2. 根节点是黑色的 

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？ 

原因：当一条路径全为黑色的时候是最短的，当红与黑交替出现的时候是最大的，而且这两种情况当中黑色都个数都是相同的，那么极端情况下是二倍关系

先来复习一下枚举

C enum(枚举) | 菜鸟教程

3 红黑树节点的插入 

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连 在一起的红色节点，此时需要对红黑树分情况来讨论： 约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

红黑树的插入要分三种情况

1，uncle 存在且为红

那么就让uncle和parent都变黑，让grandfather变红，然后cur到grandfather的位置继续向上判断

继续向上处理的条件：

        1 grandfather没有父亲，就是根，grandfather变黑即可

        2 grandfather有父亲，父亲是黑，结束了

        3  grandfather由父亲，父亲是红，跟刚才是类似的问题去处理

2，uncle 不存在

那么这时候就要去旋转即可，根据三者位置关系决定是左单旋还是右单旋还是双旋，旋转之后，让parent为红，grandfather为黑，就满足红黑树的要求了(旋转+变色)

3 ，uncle 存在且为黑

这时候单旋转和变色都不能解决问题了，要两个一起使用(旋转+变色)

 

抽象图

注意这里不是以高度来论, 而是黑节点的个数

情况一: cur为红，p为红，g为黑，u存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑  

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

这里就是双旋 

插入代码

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//找到插入的位置cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while(parent && parent->_col ==RED){//parent为红，要去看uncle,注意这里一定会有grandfatherNode* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//1如果uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;//若parent 为空那么grandfather就是根要将根置黑//而且还要继续}else{//2uncle不存在/或者为黑//这时候就要旋转了，根据g p c 的位置直接旋转if (parent->_left == cur){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//grandfather->_right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2uncle不存在/或者为黑//这时候就要旋转了，根据g p c 的位置直接旋转if (parent->_right == cur){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

4红黑树的检查

1检查是否有两个连续的红节点

2每条路径黑色节点的数量是否一致

//红黑树的验证有两点，1不能有连续的红节点，2所有路径的黑节点数量相同
bool _isBalance(Node* root)
{if (root == nullptr){return true;}//计算出一个基准值int basline = 0;Node* cur = root;while (cur){if (cur->_col == BLACK)++basline;cur = cur->_left;}return Checkcolor(root,0, basline);}bool Checkcolor(Node* root,int blacknum,int basline)
{if (root == nullptr){if (blacknum != basline){return false;}return true;}if (root->_col == BLACK)++blacknum;if (root->_col == RED && root->_parent && root->_parent->_col == RED){return false;}return Checkcolor(root->_left,blacknum,basline) && Checkcolor(root->_right, blacknum, basline);
}

5 红黑树模拟实现STL中的map与set

底层都是用红黑树，map和set都是对红黑树的封装

5.1 红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代 器，需要考虑以前问题：

begin()与end() STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后， 可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位 置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？ 能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最 后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：

1右不为空， 访问右树的最左节点

2右为空，（1如果child是parent的左访问parent,2如果child是parent的右，此时说明父亲已经访问里，就去访问祖先）

代码展示：

template <class T, class Ptr, class Ref>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;typedef __TreeIterator<T, T*, T&> Iterator;Node* _node;__TreeIterator(Node* node):_node(node){}//这个构造是为了让普通迭代器构造一个const迭代器__TreeIterator(const Iterator& it):_node(it._node){}Ref operator* (){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}//--的操作与加加相反Self& operator--(){if (_node->_left){//找到左树的最大Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}else{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur ==parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator++(){if (_node->_right){//找到右树的最小Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{Node* cur = _node;Node* parent = _node->_parent;while(parent && cur == parent->_right){ cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};

5.2set

#include "RBTree.h"
namespace cy
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://普通迭代器和const迭代器都不能修改typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}pair<iterator,bool> insert(const K& key){//这里pair<iterator,bool> Insert返回的是普通迭代器RBTree::iterator//但是在set这一层iterator 是const_iterator//在类模板里面取内嵌类型要加typenamepair<typename RBTree<K,K,SetKeyOfT>::iterator, bool> ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyOfT> _t;};}

5.3map

#include "RBTree.h"
namespace cy
{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<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin()const{return _t.begin();}const_iterator end()const{return _t.end();}pair<iterator,bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K,V>, MapKeyOfT> _t;};}

底层红黑树代码

#pragma onceenum Color
{RED,BLACK
};template <class T>
struct RBTreeNode
{RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){ }RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;T _data;
};template <class T, class Ptr, class Ref>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;typedef __TreeIterator<T, T*, T&> Iterator;Node* _node;__TreeIterator(Node* node):_node(node){}//这个构造是为了让普通迭代器构造一个const迭代器__TreeIterator(const Iterator& it):_node(it._node){}Ref operator* (){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}//--的操作与加加相反Self& operator--(){if (_node->_left){//找到左树的最大Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}else{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur ==parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator++(){if (_node->_right){//找到右树的最小Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{Node* cur = _node;Node* parent = _node->_parent;while(parent && cur == parent->_right){ cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};template <class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;public:typedef __TreeIterator<T,T*, T&> iterator;typedef __TreeIterator<T, const T*, const T&> const_iterator;iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return const_iterator(leftMin);}const_iterator end()const{return const_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;} pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}Node* cur = _root;Node* parent = nullptr;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 make_pair(iterator(cur), false);}}//找到插入的位置cur = new Node(data);cur->_col = RED;Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while(parent && parent->_col ==RED){//parent为红，要去看uncle,注意这里一定会有grandfatherNode* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//1如果uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;//若parent 为空那么grandfather就是根要将根置黑//而且还要继续}else{//2uncle不存在/或者为黑//这时候就要旋转了，根据g p c 的位置直接旋转if (parent->_left == cur){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//grandfather->_right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2uncle不存在/或者为黑//这时候就要旋转了，根据g p c 的位置直接旋转if (parent->_right == cur){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* pparent = parent->_parent;//先把父亲存起来parent->_parent = cur;if (pparent)//不为空说明是子树，parent不是根节点{if (pparent->_right == parent){pparent->_right = cur;}else{pparent->_left = cur;}cur->_parent = pparent;}else{_root = cur;cur->_parent = nullptr;}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* pparent = parent->_parent;parent->_parent = cur;if (pparent){if (pparent->_right == parent){pparent->_right = cur;}else{pparent->_left = cur;}cur->_parent = pparent;}else{_root = cur;cur->_parent = nullptr;}}bool isBalance(){return _isBalance(_root);}//红黑树的验证有两点，1不能有连续的红节点，2所有路径的黑节点数量相同bool _isBalance(Node* root){if (root == nullptr){return true;}//计算出一个基准值int basline = 0;Node* cur = root;while (cur){if (cur->_col == BLACK)++basline;cur = cur->_left;}return Checkcolor(root,0, basline);}bool Checkcolor(Node* root,int blacknum,int basline){if (root == nullptr){if (blacknum != basline){return false;}return true;}if (root->_col == BLACK)++blacknum;if (root->_col == RED && root->_parent && root->_parent->_col == RED){return false;}return Checkcolor(root->_left,blacknum,basline) && Checkcolor(root->_right, blacknum, basline);}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr){return 0;}int Heightleft = Height(root->_left);int Heightright = Height(root->_right);return Heightleft > Heightright ? Heightleft + 1 : Heightright + 1;}private:Node* _root=nullptr;
};

http://www.xdnf.cn/news/16714.html

相关文章：

  • CMake 完全实战指南：从入门到精通
  • 使用redis 作为消息队列时， 如何保证消息的可靠性
  • Leetcode 08 java
  • 鸿蒙Harmony-自定义List组件，解决List组件手势滑动点击卡住问题
  • Apache Ignite 的分布式队列（IgniteQueue）和分布式集合（IgniteSet）的介绍
  • 【dropdown组件填坑指南】鼠标从触发元素到下拉框中间间隙时，下拉框消失，怎么解决？
  • 0基礎網站開發技術教學(一) --(前端篇)--
  • 《Java 程序设计》第 9 章 - 内部类、枚举和注解
  • Java07--面向对象
  • 自动调优 vLLM 服务器参数（实战指南）
  • 如何用USRP捕获手机信号波形（下）协议分析
  • 怎么理解使用MQ解决分布式事务 -- 以kafka为例
  • 小白学OpenCV系列1-图像处理基本操作
  • 机器学习-十大算法之一线性回归算法
  • gTest测试框架的安装与配置
  • Qt 并行计算框架与应用
  • 项目优化中对象的隐式共享
  • 从单机架构到分布式：Redis为何成为架构升级的关键一环？
  • 【开源项目】轻量加速利器 HubProxy 自建 Docker、GitHub 下载加速服务
  • Less Less基础
  • Docker学习相关视频笔记（二）
  • 负载均衡、算法/策略
  • ROUGE-WE：词向量化革新的文本生成评估框架
  • Java 9 新特性解析
  • 考古学家 - 华为OD统一考试(JavaScript 题解)
  • 算法第29天|动态规划dp2：不同路径、不同路径Ⅱ、整数拆分、不同的二叉搜索树
  • uipath数据写入excel的坑
  • Python 程序设计讲义（25）：循环结构——嵌套循环
  • 《Spring Cloud Gateway 深度剖析：从核心原理到企业级实战》
  • WAIC 2025观察：昇腾助力AI融入多元化生活场景