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<class K,class V>struct RBTreeNode{RBTreeNode<K,V>* _pLeft;RBTreeNode<K,V>* _pRight;RBTreeNode<K,V>* _pParent;Color _color;pair<K,V> _data;//新插入的节点默认是红色RBTreeNode(const pair<K,V>& 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<K,V>& data){if (_pRoot == nullptr){_pRoot = new Node(data);//根节点是黑色_pRoot->_color = BLACK;return true;}Node* cur = _pRoot, * parent = nullptr;while (cur){//比我小,往左找if (data.first < cur->_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 < parent->_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<K,V>& data){if (_pRoot == nullptr){_pRoot = new Node(data);//根节点是黑色_pRoot->_color = BLACK;return true;}Node* cur = _pRoot, * parent = nullptr;while (cur){//比我小,往左找if (data.first < cur->_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 < parent->_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 K,class V>class RBTree{typedef RBTreeNode<K,V> Node;public:// 检测红黑树中是否存在关键字为key的节点，存在返回该节点的地址，否则返回nullptrNode* Find(const K& key){Node* cur = _pRoot;while (cur){if (cur->_data.first > key){cur = cur->_pLeft;}else if (cur->_data.second < key){cur = cur->_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 << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}//验证性质: 红黑树中不能存在连续的红色节点//如果一个节点是红色,该节点一定不是根节点,因此该节点一定有父亲//只需要保证红色节点的父亲不是红色节点即可if (pRoot->_color == RED){if (pRoot->_pParent->_color == RED){cout << "存在连续的红色节点" << endl;return false;}}else{blackCount++;}return _IsValidRBTRee(pRoot->_pLeft, blackCount, ReferenceCount) && _IsValidRBTRee(pRoot->_pRight, blackCount, ReferenceCount);}private:Node* _pRoot = nullptr;};

五.完整代码

1.RBTree.h

#pragma onceenum Color{RED,BLACK};template<class K,class V>struct RBTreeNode{RBTreeNode<K,V>* _pLeft;RBTreeNode<K,V>* _pRight;RBTreeNode<K,V>* _pParent;Color _color;pair<K,V> _data;//新插入的节点默认是红色RBTreeNode(const pair<K,V>& data):_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_color(RED),_data(data){}};template<class K,class V>class RBTree{typedef RBTreeNode<K,V> Node;public:// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false// 注意：为了简单起见，本次实现红黑树不存储重复性元素bool Insert(const pair<K,V>& data){if (_pRoot == nullptr){_pRoot = new Node(data);//根节点是黑色_pRoot->_color = BLACK;return true;}Node* cur = _pRoot, * parent = nullptr;while (cur){//比我小,往左找if (data.first < cur->_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 < parent->_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的节点，存在返回该节点的地址，否则返回nullptrNode* Find(const K& key){Node* cur = _pRoot;while (cur){if (cur->_data.first > key){cur = cur->_pLeft;}else if (cur->_data.second < key){cur = cur->_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 << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}//验证性质: 红黑树中不能存在连续的红色节点//如果一个节点是红色,该节点一定不是根节点,因此该节点一定有父亲//只需要保证红色节点的父亲不是红色节点即可if (pRoot->_color == RED){if (pRoot->_pParent->_color == RED){cout << "存在连续的红色节点" << endl;return false;}}else{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是_pRootif (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 << root->_data.first << " " << root->_data.second << " ";_InOrder(root->_pRight);}private:Node* _pRoot = nullptr;};

2.test.cpp

#include using namespace std;#include #include "RBtree1.h"#include void test1(){int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << endl;cout << t.IsValidRBTRee() << endl;}void test2(){const int N = 10000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << t.IsValidRBTRee() << endl;}int main(){test2();return 0;}

验证完毕

以上就是C++红黑树的全部内容,希望能对大家有所帮助!