温馨提示：这篇文章已超过452天没有更新，请注意相关的内容是否还可用！
摘要：C++红黑树是一种自平衡二叉查找树，它通过维护树的性质来保证高效的查找、插入和删除操作。红黑树中的每个节点都具有红色或黑色的属性，通过调整节点的颜色以及进行旋转操作来保持树的平衡。它具有良好的性能，适用于需要频繁进行查找、插入和删除操作的场景。
C++红黑树
- 一.红黑树的概念和性质
- 1.红黑树的概念和性质
- 2.AVL树和红黑树的区别
- 二.我们要实现的大致框架
- 1.红黑树节点的定义
- 2.为什么新节点默认是红色?
- 1.共识
- 2.新节点是黑色的坏处
- 3.新节点是红色的好处
- 三.红黑树的插入
- 1.插入逻辑跟BST相同的那一部分
- 2.分类讨论插入逻辑
- 1.新插入节点的父亲是黑色
- 2.新插入节点的父亲是红色
- 1.具体分类的说明
- 2.新插入节点的叔叔存在是红色
- 1.说明:
- 2.动图演示
- 3.总结:
- 3.新插入节点的叔叔不存在或者存在是黑色
- 1.叔叔是祖父的右孩子
- 1.说明
- 2.旋转方案
- 1.cur是parent的左孩子(右旋)
- 2.cur是parent的右孩子(左右双旋)
- 2.叔叔是祖父的左孩子
- 1.cur是parent的右孩子(左旋)
- 2.cur是parent的左孩子(右左双旋)
- 3.叔叔不存在
- 4.总结:
- 3.插入代码
- 四.红黑树的验证
- 五.完整代码
前置说明:
需要学习AVL树的旋转之后再来看红黑树的旋转
因为红黑树的旋转是复用的AVL树的旋转的:
大家可以看我的这篇博客,里面详细介绍了AVL树的四种旋转
C++ AVL树(四种旋转,插入)
一.红黑树的概念和性质
1.红黑树的概念和性质
2.AVL树和红黑树的区别
二.我们要实现的大致框架
1.红黑树节点的定义
对于颜色我们采用枚举类型定义
对于红黑树节点,依旧采用Key-Value模型存储pair
enum Color { RED, BLACK }; template struct RBTreeNode { RBTreeNode* _pLeft; RBTreeNode* _pRight; RBTreeNode* _pParent; Color _color; pair _data; //新插入的节点默认是红色 RBTreeNode(const pair& data) :_pLeft(nullptr) ,_pRight(nullptr) ,_pParent(nullptr) ,_color(RED) ,_data(data) {} };2.为什么新节点默认是红色?
1.共识
首先我们要达成一个共识:
对于性质3和性质4,如果非要违反一个的话
我们选择违反性质3,而不是性质4
因为:
违反性质3还可以通过变色和旋转的方式来解决
而违法性质4的话,其他所有路径都要重新修改
因此违法性质3的损失更小,调整更简单
违法性质4…后果不言而喻…
2.新节点是黑色的坏处
插入之前:
插入过程:
插入之后:
3.新节点是红色的好处
插入之前:
插入过程:
插入之后:
三.红黑树的插入
1.插入逻辑跟BST相同的那一部分
下面是跟BST普通二叉搜索树的插入逻辑相同的那部分
唯一不太相同的是把根节点的颜色改成黑色了而已
bool Insert(const pair& data) { if (_pRoot == nullptr) { _pRoot = new Node(data); //根节点是黑色 _pRoot->_color = BLACK; return true; } Node* cur = _pRoot, * parent = nullptr; while (cur) { //比我小,往左找 if (data.first _data.first) { parent = cur; cur = cur->_pLeft; } //比我大,往右找 else if (data.first > cur->_data.first) { parent = cur; cur = cur->_pRight; } //有重复元素,插入失败 else { return false; } } //找到空位置,开始插入 cur = new Node(data); //连接父亲和孩子 if (cur->_data.first _data.first) { parent->_pLeft = cur; } else { parent->_pRight = cur; } cur->_pParent = parent; //开始讨论节点颜色问题 //..... return true; }2.分类讨论插入逻辑
介绍了新插入的节点必须是红色之后
我们就可以分情况讨论了
1.新插入节点的父亲是黑色
因为红黑树的性质3:所有红色节点的孩子不能是红色节点
这也就说明了红黑树不能存在连续的红色节点
2.新插入节点的父亲是红色
1.具体分类的说明
下面我们就对叔叔进行分类讨论
2.新插入节点的叔叔存在是红色
1.说明:
这里以叔叔是祖父的右孩子为例演示
其实叔叔是祖父的左孩子的话是一模一样的,就不再赘述了
2.动图演示
插入前:
调整过程:
调整之后:
刚才一开始时演示的是:
cur是新增节点时的情况
但是中间过程借由祖父向上继续调整修改时,我们就已经能看出即使cur不是新增节点,调整方式和逻辑也是一模一样的!!
3.总结:
3.新插入节点的叔叔不存在或者存在是黑色
刚才的那种情况只需要变色即可
现在就需要旋转+变色了
跟AVL树的旋转类似,依然是分为4种情况
依然是画抽象图来理解
画图里面规定:
p:代表parent,父亲
c:代表cur,孩子
g:grandParent,祖父
u:uncle,叔叔
a,b,c,d,e代表红黑树或者空节点
ar:ancestor:祖父的父亲
1.叔叔是祖父的右孩子
1.说明
1.uncle存在且为黑时:cur一定不是新增节点
2.为什么不能按照之前的方式只去修改颜色
2.旋转方案
1.cur是parent的左孩子(右旋)
修改之前:
修改过程:
这里是对g进行右旋,动图里面刚才写错了,抱歉
修改之后:
修改之后没有违反性质3
注意:因为此时祖父变成了p,而且p是黑色,所以就不会继续往上修改了,证明修改完毕
下面我们对照一下修改之前和修改之后,看看是否违反了性质4
没有违反,完美的一次修改
2.cur是parent的右孩子(左右双旋)
旋转之前:
旋转过程:
旋转之后:
修改之后没有违反性质3
注意:因为此时祖父变成了c而且c是黑色,所以无需继续往上修改了
但是因为此时p是红色,会继续进入循环,这样就会发生一些意想不到的错误,所以此时必须break
下面我们对照一下修改之前和修改之后,看看是否违反了性质4
完美修改
2.叔叔是祖父的左孩子
跟叔叔是祖父的右孩子就特别像了,直接给动图了
1.cur是parent的右孩子(左旋)
旋转之前:
旋转过程:
旋转之后:
2.cur是parent的左孩子(右左双旋)
旋转之前:
旋转过程:
旋转之后:
3.叔叔不存在
以右旋为例:
旋转之前:
旋转过程:
旋转之后:
以左右双旋为例:
旋转之前:
旋转过程:
旋转之后:
4.总结:
调整颜色的总结:
3.插入代码
// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false // 注意：为了简单起见，本次实现红黑树不存储重复性元素 bool Insert(const pair& data) { if (_pRoot == nullptr) { _pRoot = new Node(data); //根节点是黑色 _pRoot->_color = BLACK; return true; } Node* cur = _pRoot, * parent = nullptr; while (cur) { //比我小,往左找 if (data.first _data.first) { parent = cur; cur = cur->_pLeft; } //比我大,往右找 else if (data.first > cur->_data.first) { parent = cur; cur = cur->_pRight; } //有重复元素,插入失败 else { return false; } } //找到空位置,开始插入 cur = new Node(data); //连接父亲和孩子 if (cur->_data.first _data.first) { parent->_pLeft = cur; } else { parent->_pRight = cur; } cur->_pParent = parent; //父亲是黑色,插入成功 if (parent->_color == BLACK) { return true; } //父亲是红色,需要调整 //且此时爷爷一定是黑色 //根据叔叔的颜色来调整 while (parent && parent->_color == RED) { Node* grandParent = parent->_pParent; //爸爸是爷爷的左孩子 if (parent == grandParent->_pLeft) { Node* uncle = grandParent->_pRight; //根据叔叔的颜色来调整 //1.叔叔存在且为红 if (uncle && uncle->_color == RED) { //修改爸爸,叔叔,爷爷的颜色 uncle->_color = parent->_color = BLACK; grandParent->_color = RED; //此时视爷爷为新插入的红色节点继续向上影响 cur = grandParent; parent = cur->_pParent; } //2.叔叔不存在或者叔叔是黑 else { //1.我是爸爸的左孩子 if (parent->_pLeft == cur) { //对爷爷进行一次右旋 RotateR(grandParent); //把爷爷改成红色,爸爸改成黑色 grandParent->_color = RED; parent->_color = BLACK; //此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了 } //2.我是爸爸的右孩子 else { //1.对爸爸进行左旋 RotateL(parent); //2.对爷爷右旋 RotateR(grandParent); //3.孩子改成黑色,爷爷改成红色 cur->_color = BLACK; grandParent->_color = RED; //4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了 break; } } } //爸爸是爷爷的右孩子 else { Node* uncle = grandParent->_pLeft; //1.叔叔存在且为红 if (uncle && uncle->_color == RED) { uncle->_color = parent->_color = BLACK; grandParent->_color = RED; cur = grandParent; parent = cur->_pParent; } //2.叔叔不存在或者叔叔为黑 else { //1.我是爸爸的右孩子 if (parent->_pRight == cur) { //对爷爷左旋 RotateL(grandParent); //爷爷改成红色,爸爸改成黑色 grandParent->_color = RED; parent->_color = BLACK; //此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了 } //2.我是爸爸的左孩子 else { //1.对爸爸右旋 RotateR(parent); //2.对爷爷左旋 RotateL(grandParent); //3.把孩子改成黑色,爷爷改成红色 cur->_color = BLACK; grandParent->_color = RED; //4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了 break; } } } } _pRoot->_color = BLACK; return true; }四.红黑树的验证
template class RBTree { typedef RBTreeNode Node; public: // 检测红黑树中是否存在关键字为key的节点，存在返回该节点的地址，否则返回nullptr Node* Find(const K& key) { Node* cur = _pRoot; while (cur) { if (cur->_data.first > key) { cur = cur->_pLeft; } else if (cur->_data.second _pRight; } else { return cur; } } return nullptr; } // 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测 bool IsValidRBTRee() { //1.空树是红黑树 if (_pRoot == nullptr) { return true; } //2.根节点不能为红色 if (_pRoot->_color == RED) { return false; } //3.为了验证性质: 红黑树的任意一条路径上的黑色节点个数相同 找参考值 size_t ReferenceCount = 0; Node* cur = _pRoot; while (cur) { if (cur->_color == BLACK) { ReferenceCount++; } cur = cur->_pLeft; } return _IsValidRBTRee(_pRoot, 0, ReferenceCount); } private: bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t& ReferenceCount) { if (pRoot == nullptr) { if (blackCount != ReferenceCount) { cout if (pRoot-_pParent->_color == RED) { cout blackCount++; } return _IsValidRBTRee(pRoot-_pLeft, blackCount, ReferenceCount) && _IsValidRBTRee(pRoot-_pRight, blackCount, ReferenceCount); } private: Node* _pRoot = nullptr; };五.完整代码
1.RBTree.h
#pragma once enum Color { RED, BLACK }; template struct RBTreeNode { RBTreeNode* _pLeft; RBTreeNode* _pRight; RBTreeNode* _pParent; Color _color; pair _data; //新插入的节点默认是红色 RBTreeNode(const pair& data) :_pLeft(nullptr) ,_pRight(nullptr) ,_pParent(nullptr) ,_color(RED) ,_data(data) {} }; template class RBTree { typedef RBTreeNode Node; public: // 在红黑树中插入值为data的节点，插入成功返回true，否则返回false // 注意：为了简单起见，本次实现红黑树不存储重复性元素 bool Insert(const pair& data) { if (_pRoot == nullptr) { _pRoot = new Node(data); //根节点是黑色 _pRoot->_color = BLACK; return true; } Node* cur = _pRoot, * parent = nullptr; while (cur) { //比我小,往左找 if (data.first _data.first) { parent = cur; cur = cur->_pLeft; } //比我大,往右找 else if (data.first > cur->_data.first) { parent = cur; cur = cur->_pRight; } //有重复元素,插入失败 else { return false; } } //找到空位置,开始插入 cur = new Node(data); //连接父亲和孩子 if (cur->_data.first _data.first) { parent->_pLeft = cur; } else { parent->_pRight = cur; } cur->_pParent = parent; //父亲是黑色,插入成功 if (parent->_color == BLACK) { return true; } //父亲是红色,需要调整 //且此时爷爷一定是黑色 //根据叔叔的颜色来调整 while (parent && parent->_color == RED) { Node* grandParent = parent->_pParent; //爸爸是爷爷的左孩子 if (parent == grandParent->_pLeft) { Node* uncle = grandParent->_pRight; //根据叔叔的颜色来调整 //1.叔叔存在且为红 if (uncle && uncle->_color == RED) { //修改爸爸,叔叔,爷爷的颜色 uncle->_color = parent->_color = BLACK; grandParent->_color = RED; //此时视爷爷为新插入的红色节点继续向上影响 cur = grandParent; parent = cur->_pParent; } //2.叔叔不存在或者叔叔是黑 else { //1.我是爸爸的左孩子 if (parent->_pLeft == cur) { //对爷爷进行一次右旋 RotateR(grandParent); //把爷爷改成红色,爸爸改成黑色 grandParent->_color = RED; parent->_color = BLACK; //此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了 } //2.我是爸爸的右孩子 else { //1.对爸爸进行左旋 RotateL(parent); //2.对爷爷右旋 RotateR(grandParent); //3.孩子改成黑色,爷爷改成红色 cur->_color = BLACK; grandParent->_color = RED; //4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了 break; } } } //爸爸是爷爷的右孩子 else { Node* uncle = grandParent->_pLeft; //1.叔叔存在且为红 if (uncle && uncle->_color == RED) { uncle->_color = parent->_color = BLACK; grandParent->_color = RED; cur = grandParent; parent = cur->_pParent; } //2.叔叔不存在或者叔叔为黑 else { //1.我是爸爸的右孩子 if (parent->_pRight == cur) { //对爷爷左旋 RotateL(grandParent); //爷爷改成红色,爸爸改成黑色 grandParent->_color = RED; parent->_color = BLACK; //此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了 } //2.我是爸爸的左孩子 else { //1.对爸爸右旋 RotateR(parent); //2.对爷爷左旋 RotateL(grandParent); //3.把孩子改成黑色,爷爷改成红色 cur->_color = BLACK; grandParent->_color = RED; //4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了 break; } } } } _pRoot->_color = BLACK; return true; } // 检测红黑树中是否存在关键字为key的节点，存在返回该节点的地址，否则返回nullptr Node* Find(const K& key) { Node* cur = _pRoot; while (cur) { if (cur->_data.first > key) { cur = cur->_pLeft; } else if (cur->_data.second _pRight; } else { return cur; } } return nullptr; } // 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测 bool IsValidRBTRee() { //1.空树是红黑树 if (_pRoot == nullptr) { return true; } //2.根节点不能为红色 if (_pRoot->_color == RED) { return false; } //3.为了验证性质: 红黑树的任意一条路径上的黑色节点个数相同 找参考值 size_t ReferenceCount = 0; Node* cur = _pRoot; while (cur) { if (cur->_color == BLACK) { ReferenceCount++; } cur = cur->_pLeft; } return _IsValidRBTRee(_pRoot, 0, ReferenceCount); } void InOrder() { _InOrder(_pRoot); } private: bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t& ReferenceCount) { if (pRoot == nullptr) { if (blackCount != ReferenceCount) { cout if (pRoot-_pParent->_color == RED) { cout blackCount++; } return _IsValidRBTRee(pRoot-_pLeft, blackCount, ReferenceCount) && _IsValidRBTRee(pRoot-_pRight, blackCount, ReferenceCount); } // 右单旋 void RotateR(Node* pParent) { Node* subL = pParent->_pLeft; Node* subLR = subL->_pRight; Node* grandParent = pParent->_pParent; subL->_pRight = pParent; pParent->_pParent = subL; pParent->_pLeft = subLR; if (subLR) subLR->_pParent = pParent; if (grandParent == nullptr) { _pRoot = subL; _pRoot->_pParent = nullptr; } else { if (pParent == grandParent->_pLeft) { grandParent->_pLeft = subL; } else { grandParent->_pRight = subL; } subL->_pParent = grandParent; } } // 左单旋 void RotateL(Node* pParent) { Node* subR = pParent->_pRight; Node* subRL = subR->_pLeft; Node* grandParent = pParent->_pParent; pParent->_pParent = subR; subR->_pLeft = pParent; pParent->_pRight = subRL; if (subRL) subRL->_pParent = pParent; //说明此时pParent是_pRoot if (grandParent == nullptr) { _pRoot = subR; _pRoot->_pParent = nullptr; } //说明此时pParent所在的树是一颗子树,需要跟父亲链接 else { if (pParent == grandParent->_pLeft) { grandParent->_pLeft = subR; } else { grandParent->_pRight = subR; } subR->_pParent = grandParent; } } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_pLeft); cout _data.first int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; RBTree t.Insert(make_pair(e, e)); } t.InOrder(); cout const int N = 10000000; vector v.push_back(rand() + i); } size_t begin2 = clock(); RBTree t.Insert(make_pair(e, e)); } size_t end2 = clock(); cout test2(); return 0; }
文章版权声明：除非注明，否则均为VPS857原创文章，转载或复制请以超链接形式并注明出处。
还没有评论，来说两句吧...