✅<1>主页：我的代码爱吃辣
📃<2>知识讲解：数据结构——红黑树
☂️<3>开发环境：Visual Studio 2022
💬<4>前言：红黑树也是一颗二叉搜索树，其作为map，set的底层容器，具有非常好的搜索性能，仅仅通过控制颜色和位置就能达到一种，近似平衡的效果，大大减少了旋转的次数。
目录
编辑
一.红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。
编辑
二. 红黑树的性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)NIL结点
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
答案：因为性质3限制了，一条路径上，不可能出现连续的两个红色结点。又因为性质4，每条路径上黑色结点数目相同，那么最短路径就一定是全是黑色结点的路径，最长路径一定是红黑交错的路径，因为根节点一定是黑色，那么最长路径上红黑结点树一定是相等的，所以最长路径最多是最短路径的两倍。
三.红黑树节点及其整体的定义
//枚举 enum Color { RED,//红色 BLACK//黑色 }; template<class K,class V> struct _RBTreeNode { _RBTreeNode(pair<K,V> kv) :_kv(kv), _col(RED),//默认红色 _left(nullptr), _right(nullptr), _parent(nullptr) { } pair<K, V> _kv; //存储数值 Color _col; //颜色 _RBTreeNode<K, V>* _left; //左孩子 _RBTreeNode<K, V>* _right; //右孩子 _RBTreeNode<K, V>* _parent; //父亲 };
#pragma once #include<iostream> using namespace std; template<class K,class V> class RBTRee { typedef _RBTreeNode<K, V> Node;//结点 public: Node* find(const K key) { //.... } bool insert(pair<K, V> kv) { //.... } void Inorder() { //... } ~RBTRee() { //... } private: Node* _root = nullptr;//根节点 };
思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？
答案：新创建的结点，妖色要么红色，要么黑色，除了颜色区别之外，就是在插入时对整个树的影响不同，如果插入的是黑色，会影响整颗树，所有路径上的黑色结点说就会不同，必然违反性质4。如果插入的是红色结点，仅仅是局部的影响，可能会影响性质3，一定不会影响性质4。
编辑
四.红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1. 按照二叉搜索的树规则插入新节点。
bool insert(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 (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else { return false; } } //找到了合适的位置 cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //.... }
因为性质2，所以我们每一次插入数据都想根节点变成黑色。
2.检测新节点插入后，红黑树的性质是否造到破坏，若满足直接退出，否则对红黑树进行旋转着色处理。
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。
情况一： cur为红，p为红，g为黑，u存在且为红
编辑
解决方式：将 p , u 改为黑，g 改为红，然后把 g 当成 cur，继续向上调整。
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
编辑
编辑
- p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
- p、g变色--p变黑，g变红
情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑
编辑
- p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；
编辑
- p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
- p、g变色--p变黑，g变红
这里的cur的也有可能是新增的结点，如果是cur本身就是新增节点那么u结点就是不存在的，否则违反规则 4，也有可能是因为cur下面的结点变黑导致 cur 变红色。
编辑
编辑 代码：
while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; // g(B) g(R) // p(R) u(R) --> p(B) u(B) //c(R) c(R) if (grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; //继续向上调整 cur = grandfather; parent = cur->_parent; } else //u不存在/u存在且为黑，旋转+变色 { // g(B) p(R) // p(R) u(B) --> u(B) g(B) //c(R) u(B) if (cur == parent->_left) { //右单旋 RotateR(grandfather); parent->_col = BLACK; //cur->_col = RED; grandfather->_col = RED; } else { // g(B) P(B) // p(R) u(B) --> c(R) g(R) // c(R) u(B) // 左右双旋 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 = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else //u不存在/u存在且为黑，旋转+变色 { if (cur == parent->_right) { //左单旋 RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // 右左双旋 RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } }
旋转：
void RotateL(Node* parent) { Node* curR = parent->_right; Node* curRL = curR->_left; //调整结点，并且修改其父亲结点指针 parent->_right = curRL; if (curRL)//可能为空 { curRL->_parent = parent; } //在修改子树根节点之前，保存子树根节点的父亲 Node* pparent = parent->_parent; //修改子树根节点 curR->_left = parent; parent->_parent = curR; //子树根节点有可能是整棵树的根节点 if (pparent == nullptr) { _root = curR; _root->_parent = nullptr; } else//子树根节点不是整棵树的根节点 { //还要看子树是它父亲的左孩子还是右孩子 if (pparent->_left == parent) { pparent->_left = curR; } else { pparent->_right = curR; } curR->_parent = pparent; } } void RotateR(Node* parent) { Node* curL = parent->_left; Node* curLR = curL->_right; parent->_left = curLR; if (curLR) { curLR->_parent = parent; } Node* pparent = parent->_parent; curL->_right = parent; parent->_parent = curL; if (parent == _root) { _root = curL; _root->_parent = nullptr; } else { if (pparent->_left == parent) { pparent->_left = curL; } else { pparent->_right = curL; } curL->_parent = pparent; } }
红黑树顺序插入：
编辑
红黑树随机插入：
编辑
五.红黑树 find
根据二叉搜索树特性去查找：
Node* find(const K key) { Node* cur = _root; while (cur) { if (key < cur->_kv.first) { cur = cur->_left; } else if (key > cur->_kv.first) { cur = cur->_right; } else { return cur; } } return nullptr; }
六.析构函数
后续遍历析构树：
~RBTRee() { _Destrory(_root); _root = nullptr; } void _Destrory(Node* root) { if (root == nullptr) { return; } _Destrory(root->_left); _Destrory(root->_right); delete root; }
七.红黑树的验证
红黑树的检测分为两步：
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 检测其是否满足红黑树的性质
其中是否满足搜索树我们只要对其中序遍历是否有序即可。
完整代码：
#pragma once #include<iostream> using namespace std; enum Color { RED, BLACK }; template<class K,class V> struct _RBTreeNode { _RBTreeNode(pair<K,V> kv) :_kv(kv), _col(RED), _left(nullptr), _right(nullptr), _parent(nullptr) { } pair<K, V> _kv; Color _col; _RBTreeNode<K, V>* _left; _RBTreeNode<K, V>* _right; _RBTreeNode<K, V>* _parent; }; template<class K,class V> class RBTRee { typedef _RBTreeNode<K, V> Node; public: Node* find(const K key) { Node* cur = _root; while (cur) { if (key < cur->_kv.first) { cur = cur->_left; } else if (key > cur->_kv.first) { cur = cur->_right; } else { return cur; } } return nullptr; } bool insert(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 (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(kv); //找到了合适的位置 if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; while ( parent && parent->_col == RED) { Node* grandfather = parent->_parent; // g(B) g(R) // p(R) u(R) --> p(B) u(B) //c(R) c(R) if ( grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; //继续向上调整 cur = grandfather; parent = cur->_parent; } else //u不存在/u存在且为黑，旋转+变色 { // g(B) p(R) // p(R) u(B) --> u(B) g(B) //c(R) u(B) if (cur == parent->_left) { //右单旋 RotateR(grandfather); parent->_col = BLACK; //cur->_col = RED; grandfather->_col = RED; } else { // g(B) P(B) // p(R) u(B) --> c(R) g(R) // c(R) u(B) // 左右双旋 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 = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else //u不存在/u存在且为黑，旋转+变色 { 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; } void Inorder(vector<K> & v) { _inorder(_root,v); cout << endl; } ~RBTRee() { _Destrory(_root); _root = nullptr; } private: void _Destrory(Node* root) { if (root == nullptr) { return; } _Destrory(root->_left); _Destrory(root->_right); delete root; } void _inorder(Node* root, vector<K>& v) { if (root == nullptr) { return; } _inorder(root->_left,v); v.push_back(root->_kv.first); _inorder(root->_right,v); } void RotateL(Node* parent) { Node* curR = parent->_right; Node* curRL = curR->_left; //调整结点，并且修改其父亲结点指针 parent->_right = curRL; if (curRL)//可能为空 { curRL->_parent = parent; } //在修改子树根节点之前，保存子树根节点的父亲 Node* pparent = parent->_parent; //修改子树根节点 curR->_left = parent; parent->_parent = curR; //子树根节点有可能是整棵树的根节点 if (pparent == nullptr) { _root = curR; _root->_parent = nullptr; } else//子树根节点不是整棵树的根节点 { //还要看子树是它父亲的左孩子还是右孩子 if (pparent->_left == parent) { pparent->_left = curR; } else { pparent->_right = curR; } curR->_parent = pparent; } } void RotateR(Node* parent) { Node* curL = parent->_left; Node* curLR = curL->_right; parent->_left = curLR; if (curLR) { curLR->_parent = parent; } Node* pparent = parent->_parent; curL->_right = parent; parent->_parent = curL; if (parent == _root) { _root = curL; _root->_parent = nullptr; } else { if (pparent->_left == parent) { pparent->_left = curL; } else { pparent->_right = curL; } curL->_parent = pparent; } } Node* _root = nullptr; };
//传参时benchmark是-1，代表还没有基准值，当走完第一条路径时， //将第一条路径的黑色节点数作为基准值，后续路径走到null时，就与基准值比较。 //blacknum记录路径上的黑色节点数 bool _isRBTree(Node* root, int blacknum, int benchmark) { if (root == nullptr) { if (benchmark == -1) { benchmark = blacknum; } else { if (blacknum != benchmark) { cout << "black Node !=" << endl; return false; } } return true; } if (root->_col == BLACK) { blacknum++; } //判断时候出现两个连续的红色结点 if (root->_col == RED && root->_parent && root->_parent->_col == RED) { cout << "red connect " << endl; return false; } return _isRBTree(root->_left, blacknum, benchmark) && _isRBTree(root->_right, blacknum, benchmark); }
main.cpp
#include<vector> #include<cassert> #include"RB_Tree.hpp" int main() { RBTRee<int, int> rb; int i = 100000; while(i--) { int num = rand() + i; rb.insert(make_pair(num,num)); } vector<int> v; rb.Inorder(v); for (int i = 0; i < v.size() - 1; i++) { if (v[i] > v[i + 1]) { assert(0); } } cout << rb.isRBTree() << endl; return 0; }
编辑
八. 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(
)，红黑树不追
求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，
所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红
黑树更多。
