数据结构：红黑树的模拟实现

1、什么是红黑树？

2、红黑树的相关操作与实现

1、节点定义

2、查找操作

3、插入操作

1、cur为红，p为红，g为黑，cur存在且为红

2、cur为红，p为红，g为黑，u不存在/u存在且为黑

4、判断是否为红黑树

3、完整实现代码

1、什么是红黑树？

前面的文章我们讲解了AVL树，AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度。但是AVL树为了保持平衡要旋转来操作，在删除时有可能要一直旋转到根部，效率就会比较低下，如果数据的个数为静态的(即不会改变)，可以考虑AVL树，如果一个结构经常修改，那么红黑树是个不错的选择。

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在普通的二叉搜索树的基础上增加了一些额外的规则来确保树的高度差别不会太大，从而保持了较为稳定的性能。在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质：

1、每个节点不是黑色就是红色。

2、根节点是黑色的。

3、如果一个节点是红色的，那么它的两个孩子是黑色的，也就是说，不可以有两个连续的红色节点。

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

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

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

个数的两倍？

因为不会有两个连续的红色节点，而每条路径上面的黑色节点数目都相同，所以所有节点的长度只会在：

N为每条路径黑色节点的个数，而红色节点最多也为N，所以所有路径的长度只会在N~2N内。

2、红黑树的相关操作与实现

红黑树与AVL树都是二叉搜索树，在插入操作时也使用了左旋与右旋，这些在AVL树的文章中也做过讲解，可以参考这篇文章：数据结构：AVL树

1、节点定义

enum Color
{RED,BLACK
};
template<class valuetype>
struct RBTreeNode
{RBTreeNode(const valuetype& data = valuetype(), Color color = RED):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}RBTreeNode<valuetype>* _left;RBTreeNode<valuetype>* _right;RBTreeNode<valuetype>* _parent;valuetype _data;Color _color;};

使用枚举类型来表示颜色，节点结构与AVL树类似

2、查找操作

红黑树的查找操作与二叉搜索树一致

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

3、插入操作

红黑树是在二叉搜索树的基础上附加了平衡条件来保持特性，其最长路径中节点个数不会超过最短路径节点个数的两倍，所以它的旋转次数相对AVL树会少一些，而深度相比AVL树也不会很大，对于计算机来说，查找20次和查找40次是差别不大的。

在寻找插入位置方面与AVL树一致，只不过在调整保持特性有所不同。

接下来cur表示当前节点，p表示该节点的父节点，g表示该节点的爷爷节点，也就是父节点的父节点，u表示叔叔节点，也就是父节点的兄弟节点。

1、cur为红，p为红，g为黑，cur存在且为红

p是g的左孩子还是右孩子操作都是一样的

这种情况如图所示，将g节点变红，p节点和u节点变黑来保证性质4不变。

如果g的父节点为红，就违反了性质3，需要继续向上调整。

2、cur为红，p为红，g为黑，u不存在/u存在且为黑

1、如果u不存在，那么cur一定是新增节点，由性质4可以得到。

如果p是g的左孩子，cur为左孩子则进行右单旋。

相反如果p是g的右孩子，cur为右孩子则进行左单旋。

2、如果u存在且为黑，那么cur一定是由（1、cur为红，p为红，g为黑，cur存在且为红）这种情况调整上来的，也是根据性质4就可以推出来，每条路径上的黑色节点数目是相同的。

接下来只需要判断需要进行左单旋还是右单旋即可：

🚀p是g的左孩子，cur是p的左孩子

🚀p是g的右孩子，cur是p的右孩子

为保证性质4，调整p为黑，g为红。

🚀p是g的右孩子，cur是p的左孩子

对p做右单旋后，仔细观察发现转变为了情况<2>，对g进行左单旋即可。

为保证性质4，调整cur为黑，g为红。

🚀p是g的左孩子，cur是p的右孩子

对p做左单旋后，仔细观察发现转变为了情况<1>，对g进行右单旋即可。

为保证性质4，调整cur为黑，g为红。

根据上述逻辑写出插入操作，代码如下：

bool Insert(const  valuetype& data){if (_root == nullptr){_root = new Node(data, BLACK);//根的双亲为头结点return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data < data){parent = cur;cur = cur->_right;}else if(cur->_data>data){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data, RED);if (cur->_data < parent->_data){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_color == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_color == RED){grandparent->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateL(parent);RotateR(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}else{Node* uncle = grandparent->_left;if (uncle && uncle->_color == RED){grandparent->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateR(parent);RotateL(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}}_root->_color = BLACK;return true;}

4、判断是否为红黑树

我们主要验证性质3和性质4

bool Check(Node* root, int blacknum, const int refval){if (root == nullptr){if (blacknum != refval){cout << "有黑色节点数目不同的路径";return false;}return true;}if (root->_color == RED && root->_parent->_color == RED){cout << "存在连续的红色节点";return false;}if (root->_color == BLACK){blacknum++;}return Check(root->_left, blacknum, refval)&& Check(root->_right, blacknum, refval);}

每次一条路径走完时，我们需要把它和一个标准值来比较，验证性质4.

我们走完一条路径得到标准值refval来调用Check递归函数检查。

//判断是否为红黑树bool IsRBTree(){if (_root == nullptr)return true;if (_root->_color == RED)return false;Node* cur = _root;int refval = 0;while (cur){if (cur->_color == BLACK)refval++;cur = cur->_left;}return Check(_root, 0, refval);  //调用检查函数，black为0；}

3、完整实现代码

#pragma onceenum Color
{RED,BLACK
};
template<class valuetype>
struct RBTreeNode
{RBTreeNode(const valuetype& data = valuetype(), Color color = RED):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}RBTreeNode<valuetype>* _left;RBTreeNode<valuetype>* _right;RBTreeNode<valuetype>* _parent;valuetype _data;Color _color;};template<class valuetype>
class RBTree
{
public:typedef RBTreeNode<valuetype> Node;bool Insert(const  valuetype& data){if (_root == nullptr){_root = new Node(data, BLACK);//根的双亲为头结点return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data < data){parent = cur;cur = cur->_right;}else if(cur->_data>data){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data, RED);if (cur->_data < parent->_data){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_color == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_color == RED){grandparent->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateL(parent);RotateR(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}else{Node* uncle = grandparent->_left;if (uncle && uncle->_color == RED){grandparent->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateR(parent);RotateL(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}}_root->_color = BLACK;return true;}void RotateL(Node* parent){Node* sub = parent->_right;Node* subl = sub->_left;parent->_right = subl;sub->_left = parent;Node* ppnode = parent->_parent;parent->_parent = sub;if (subl){subl->_parent = parent;}if (parent == _root){_root = sub;sub->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = sub;}else{ppnode->_right = sub;}sub->_parent = ppnode;}}void RotateR(Node* parent){Node* subl = parent->_left;Node* subr = subl->_right;parent->_left = subr;if (subr){subr->_parent = parent;}subl->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subl;if (parent == _root){_root = subl;subl->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = subl;}else{ppnode->_right = subl;}subl->_parent = ppnode;}}bool Check(Node* root, int blacknum, const int refval){if (root == nullptr){if (blacknum != refval){cout << "有黑色节点数目不同的路径";return false;}return true;}if (root->_color == RED && root->_parent->_color == RED){cout << "存在连续的红色节点";return false;}if (root->_color == BLACK){blacknum++;}return Check(root->_left, blacknum, refval)&& Check(root->_right, blacknum, refval);}//判断是否为红黑树bool IsRBTree(){if (_root == nullptr)return true;if (_root->_color == RED)return false;Node* cur = _root;int refval = 0;while (cur){if (cur->_color == BLACK)refval++;cur = cur->_left;}return Check(_root, 0, refval);  //调用检查函数，black为0；}void _inorder(Node* root){if (root == nullptr){return;}_inorder(root->_left);cout << root->_data<<" ";_inorder(root->_right);}void inorder(){_inorder(_root);}
private:Node* _root=nullptr;
};

以上就是对于红黑树的简单讲解，红黑树从根到叶子的最长路径不超过最短路径的两倍长。这确保了树的高度始终保持在对数级别，使得查找、插入和删除等操作的时间复杂度始终保持较低水平O(log n)。通过引入颜色标记和自平衡规则，提供了一种高效的二叉搜索树实现，适用于需要频繁插入、删除和查找操作的场景。