拿捏红黑树（C++）

文章目录

前言
一、红黑树介绍
二、插入操作
三、验证红黑树
四、红黑树与AVL性能比较与应用
五、总体代码
总结

前言

我们之前介绍了一种AVL的高阶数据结构，在本篇文章中，我们将会介绍一种与AVL旗鼓相当的数据结构–红黑树。
我们并且会对它的部分接口进行模拟实现

一、红黑树介绍

AVL是保证左右高度不超过1，实现平衡。
红黑树是在每个节点存储位表示颜色，包括红色和黑色，并且保证最长路径的节点个数不超过最短节点路径的两倍，我们就可以达到一种近似平衡
在这里插入图片描述

性质

🌟每个节点颜色不是红色就是黑色
🌟根节点是黑色的
🌟如果一个节点是红色，那么它的孩子必须是黑色节点（不允许出现连续的红色节点）
🌟每条路径都包含相同数量的黑色节点（路径：根节点到空）
🌟空节点设置为黑色，这个节点也称为NIL节点

为什么这几条规则就可以保证最长路径的节点数量不超过最短路径节点数量的两倍呢？？

我们从极端场景分析：
最短路径：全黑节点
最长路径：一黑一红

二、插入操作

我们需要一个位置表示颜色，这里我们采用枚举（enum）的方式。

我们插入到节点是插入红色呢还是黑色呢？？

我们看一下主要的规则：每条路径都包含相同数量的黑色节点；不允许出现连续的红色节点。

如果我们插入黑色节点，每条路径都会受到影响，我们是很难控制调整的。
如果我们插入红色节点，不允许出现连续的红色节点。我们只是在一条路径上插入，只需要调整这条路径上的节点，保证不出现连续的红色节点就可以。

先把大框架实现。

enum Col
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Col  _col;//表示颜色pair<K, V>_kv;RBTreeNode(const pair<K, V>kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)//初始化为红色,_kv(kv){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

如何插入节点呢？？
1.按照二叉搜索树规则找到插入节点
2.进行颜色调整

我们插入的是红色节点，如果父亲节点的颜色也是红色，我们就需要进行调整。
如果父亲节点的颜色是黑色，我们就不需要进行处理，直接退出。

调整：
我们这里的关键是看叔叔
因为我们已经知道我们插入的节点是红色，并且父亲也是红色，爷爷节点必定是黑色。
我们唯一不确定的就是叔叔节点

uncle存在且为红

在这里插入图片描述

我们分析一下具象图

当a/b/c/d/e都为空时，cur就是新插入节点。
在这里插入图片描述

我们需要把p和u变黑，同时把g变黑
在这里插入图片描述

如果这个节点是根节点，我们就把g变黑。
否则cur=g，p=g->p;继续调整。（原来根是黑色，现在变为红色）

当c/d/e是包含一个黑色节点的子树

有四种情况
在这里插入图片描述

我们选择最简单的看一下，插入的位置有四个选择。
在这里插入图片描述

我们把p和u变黑，同时g变红

下图才是我们这种去情况的具象图，这种情况是由之前的情况调整过来的。
在这里插入图片描述

把p和u变黑，同时g变红
如果这个节点是根节点，我们就把g变黑。
否则cur=g，p=g->p;继续调整。（原来根是黑色，现在变为红色）

在这里插入图片描述
我们发现g就是根节点，我们把g变黑

在这里插入图片描述

我们发现现在每条路径上黑节点的数量增加了，由原来两个黑节点变为现在3个黑节点。
黑色节点的数量增加是在根节点增加的，根节点增加就相当于每条路径都增加。

uncle不存在，或者存在且为黑

在这里插入图片描述

如果u不存在，cur就是新增加点，我们通过之前的变色已经完成不了了。
在这里插入图片描述

我们这时就需要进行旋转，旋转方式还是按照AVL树的情况。
这个场景下我们需要右旋

在这里插入图片描述、
旋转完之后，进行变色，p变黑，g变红

如果是下面这种情况，我们就需要进行双旋之后，再进行变色
在这里插入图片描述

首先对p进行左旋
在这里插入图片描述

再对g进行右旋
在这里插入图片描述
最后进行变色，cur变为黑，g变为红

总结：
🌟我们新插入节点颜色是红色
🌟如果新插入节点的父亲节点是黑色，我们不进行调整，直接退出
🌟如果新插入节点的父亲节点是红色，此时关键看叔叔。
🌟如果叔叔存在且为红，将p和u变黑，g变红。判断g是否为根节点。如果为根节点，g变黑。否则继续调整。
我们不关心左右，p和u是g的左右都不收影响，cur是p的左右也不受影响。
🌟如果uncle不存在或者存在且为黑，调整完之后结束。原来根是黑色，现在根也是黑色，不影响
🌟p为g的左孩子，cur为p的左孩子，对g进行右单旋，p变黑，g变红
🌟p为g的右孩子，cur为p的右孩子，对g进行左单旋，p变黑，g变红
🌟p为g的左孩子，cur为p的右孩子，对p进行左单旋，对g进行右单旋，c变黑，g变红
🌟p为g的右孩子，cur为p的左孩子，对p进行右单旋，对g进行左单旋，c变黑，g变红

	bool Insert(const pair<K, V>kv){if (_root == nullptr){_root = new Node(kv);//根节点是黑色_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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存在且不是黑色节点，则parent一定不是根，一定存在。Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑else{//左子树的左边if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//左子树的右边else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑else{//右子树的右边if (cur == parent->_right){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;}

我们有可能需要大量判断是否为根节点的情况，我们直接在结尾处加上
_root->_col = BLACK;暴力处理

三、验证红黑树

我们如何进行验证是一颗红黑树呢？？
我们从主要的规则入手

🌟根节点是黑色的
🌟不允许出现连续的红色节点
🌟每条路径都包含相同数量的黑色节点

我们只需要判断这三条成立，就能保证最长路径的节点个数不超过最短节点路径的两倍，从而证明这就是一颗红黑树。

根是黑节点很好证明，其他两条呢？？

不允许出现连续红色节点,判断一个节点和它的父节点是否都是红色。
这里如果判断这个节点和它的孩子节点会很复杂。

每条路径都包含相同数量的黑色节点，我们可以选择其中一条路径，计算出有多少个黑色节点，从而判断其他路径的黑色节点数量。

bool  IsBalance(){if (_root && _root->_col == RED){cout << "根节点为红色" << endl;return false;}//参考值int level = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){level++;}cur = cur->_left;}return check(_root, 0, level);}//BlackNum不能加引用
bool check(Node* root, int BlackNum, int level)
{if (root == nullptr){if (BlackNum != level){cout << "不包含相同数量的黑色节点" << endl;return false;}return true;}//判断红节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红节点" << endl;return false;}if (root->_col == BLACK){BlackNum++;}return check(root->_left, BlackNum, level) && check(root->_right, BlackNum, level);
}

四、红黑树与AVL性能比较与应用

性能

红黑树和AVL都是高效的平衡二叉树，增删查改的时间复杂度为·O(logN).
红黑树不追求绝对平衡，只需要保证最长路径不超过最短路径的两倍。相对而言，降低了插入和旋转次数，所以在经常进行增删的结构中比AVL更优，红黑树的实现比较简单，实际应用中红黑树更多。

AVL高度logN，红黑树高度logN*2.红黑树搜索效率相对AVL差一点，但是logN足够小，可以忽略不计。
N=10亿。logN=30.

应用：
1.C++ STL库 – map/set、mutil_map/mutil_set
2.Java 库
3. linux内核
4.其他库

五、总体代码

#pragma onceenum Col
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Col  _col;pair<K, V>_kv;RBTreeNode(const pair<K, V>kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>kv){if (_root == nullptr){_root = new Node(kv);//根节点是黑色_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑else{//左子树的左边if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//左子树的右边else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑else{//右子树的右边if (cur == parent->_right){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;}//1.根节点是黑色//2.不包含连续的红色节点//3.每条路径都包含相同黑色节点bool  IsBalance(){if (_root && _root->_col == RED){cout << "根节点为红色" << endl;return false;}//参考值int level = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){level++;}cur = cur->_left;}return check(_root, 0, level);}void Inorder(){_Inorder(_root);}
private://BlackNum不能加引用bool check(Node* root, int BlackNum, int level){if (root == nullptr){if (BlackNum != level){cout << "不包含相同数量的黑色节点" << endl;return false;}return true;}//判断红节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红节点" << endl;return false;}if (root->_col == BLACK){BlackNum++;}return check(root->_left, BlackNum, level) && check(root->_right, BlackNum, level);}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right= subRL;if (subRL){subRL->_parent = parent;}subR->_left= parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}//右旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (ppnode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}Node* _root = nullptr;
};