-
【二叉树进阶】红黑树（Red Black Tree） - 平衡二叉搜索树
一、红黑树的概念
红黑树，是一种平衡二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。
AVL树和红黑树：
- AVL树：严格平衡（左右子树高度差不超过1），所以AVL树的查找、插入、删除效率高：O(logN)，但插入和删除节点后，要维持树的平衡状态，做的旋转处理还是很多的。
- 红黑树：近似平衡（控制最长路径不超过最短路径的2倍），变了一种方式来控制树的平衡，相较于AVL树，没有那么严格。
红黑树更多是一种折中的选择，它舍弃平衡二叉树的严格平衡，换取节点插入时尽可能少的调整。
因为红黑树的旋转情况少于AVL树，使得红黑树整体性能略优于AVL树，不然map和set底层怎么会用红黑树呢，包括很多语言的库里面都用了红黑树。
如果发明AVL树的人是天才的话，那么发明红黑树的人就是天才中的天才，太妙了。
二、红黑树的性质
【核心 & 重要】
-
每个结点不是红色就是黑色
-
根节点是黑色的
-
如果一个节点是红色的，则它的两个孩子结点必须是黑色的（这就约束了红黑树里面没有连续的红色节点）
-
对于每个结点，从该结点到其所有可到达的叶结点的路径中，均包含相同数目的黑色结点
（即==每条路径都有相同数量的黑色节点==，注意：路径是走到 NIL 空节点）
-
每个 NIL 叶子结点都是黑色的（此处的叶子结点指的是空结点）
如图，这颗红黑树有11条路径，每条路径都有两个黑节点（不包括NIL）
【思考】
为什么满足以上性质后，就能保证 最长路径中节点个数不会超过最短路径中节点个数的2倍 了呢（不包括NIL）
当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点交替构成的（性质3限定了不能出现两个连续的红色节点）。
而性质4又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点，这么来说最长路径上的黑节点的数目和最短路径上的黑节点的数目相等。
最短路径：全是黑节点，最长路径：一黑一红，交替出现，所以最长路径刚好是最短路径的2倍。
2.1 红黑树和AVL树效率对比
对于一棵拥有 n 个内部结点（不包括NIL叶子结点）的红黑树，树的最大高度为 h = 2log2(n + 1)
当红黑树是一颗满二叉树时，高度最小 h = log2(n+1)，当红黑树中最长路径刚好是最短路径2倍的时候，红黑树的高度最大 h = 2log2(n+1)
如果数据量是10亿：
查找效率 查找次数(约等于) AVL树：log2n 30 红黑树：2log2n 60 【结论】：
- 虽然AVL树的查找效率优于红黑树，但对于现在的CPU，查找30次和60次是没有什么区别的，可以认为红黑树和AVL树的查找效率几乎是一样的，简化后为 O(log2n)。
- 红黑树整体性能略优于AVL树（因为红黑树旋转情况少于AVL树）。
- 红黑树的插入删除比AVL树更便于控制操作。
- 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2n)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
三、红黑树的结构（KV模型）
和AVL树类似。
1、定义红黑树的节点结构
// 定义红黑颜色 enum Colour // 枚举类型，枚举值默认从0开始，往后逐个加1（递增） { BLACK, RED }; // 红黑树节点的定义（KV模型） template<class K, class V> struct RBTreeNode { pair<K, V> _kv; // 键值对 Colour _col; // 用来标记节点颜色 RBTreeNode<K, V>* _left; // 三叉链结构 RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; // 构造函数 RBTreeNode(const pair<K, V>& kv) : _kv(kv) , _col(RED) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
2、定义红黑树结构
// 红黑树的定义（KV模型） template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; private: Node* _root; public: RBTree() :_root(nullptr) {} // 构造函数 bool Insert(const pair<K, V>& kv); // 插入节点 void RotateLeft(Node* parent); // 左单旋 void RotateRight(Node* parent); // 右单旋 bool IsBalance(); // 检测红黑树是否平衡 void InOrder(); // 中序遍历 // ...... private: void _InOrder(Node* root); // 中序遍历子函数 // ...... };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
【思考】：在节点的定义中，为什么要将节点的默认颜色给成红色的？
- 如果插入黑色节点，一定会破坏性质4（每条路径的黑色节点数量相等）；
- 如果插入红色节点，可能会破坏性质3（树中不能出现两个连续的红色节点）；
- 所以默认给红色。
四、红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
- 按照二叉搜索树的规则插入新节点
- 检测新节点插入后，红黑树的性质是否遭到破坏，然后进行平衡化操作
4.1 插入节点
思考：插入的新节点是红色好还是黑色好呢？
红色好，如果插入黑色，一定会破坏性质4（每条路径的黑色节点数量相等）；如果插入红色，可能会破坏性质3（树中不能出现两个连续的红色节点）
插入一个红色新节点后，检测红黑树的性质是否遭到破坏，分为2种情况：
-
如果其父节点颜色是黑色，没有违反红黑树任何性质，则不需要调整；
-
如果其父节点颜色是红色，则违反了性质3（树中不能出现两个连续的红色节点），此时需要对红黑树进行平衡化操作，分为以下几种情况来讨论👇
4.2 平衡化操作（难点）
约定：cur 为当前插入的节点，p (parent)为父节点，g (grandfather)为祖父节点，u (uncle)为叔叔节点
调整的关键：主要是看 cur 的叔叔节点 u 是否存在，以及叔叔节点 u 的颜色。
解析：cur为红，p为红，违反规则了，我们将p变黑，则导致p所在的所有路径上，黑节点数增加了一个，但因为 叔叔节点u 和 父节点p 在同一层上，所以叔叔节点u的状态会影响到 以祖父g为根的子树中 路径的黑节点数，可能导致违反规则（每条路径都有相同数量的黑色节点）。
👇注意：此处看到的树，可能是一颗完整的树，也可能是一颗子树。所以可能会一直调整到根节点才停止。
4.2.1 情况一
情况一：cur为红，p为红，g为黑，u存在且为红
对情况一进行平衡化操作：先调整颜色，再往上调整
无论父亲 p 是祖父 g 的左孩子还是右孩子，无论 cur 是父亲 p 的左孩子还是右孩子，处理方式都一样：
-
调整颜色：将 cur 的父亲 p 和叔叔 u 变黑，祖父 g 变红
-
把祖父 g 当成新的 cur，往上调整（即往上检测新的子树破坏了性质），分为以下情况：
- 如果 cur 父亲 p 不存在，说明 cur 就是根节点，调整到头了，此时将根节点改为黑色
- 如果 cur 父亲 p 存在且为黑色，无需调整（没有违反任何性质)
- 如果 cur 父亲 p 存在且为红色，继续调整，判断是否产生了情况二或三：
【注意】：
情况一在向上调整的过程中，可能会产生情况二或三，处理方式：旋转（先要判断是哪种旋转） + 变色处理
4.2.2 情况二
情况二： cur为红，p为红，g为黑，u不存在 / u存在且为黑
如图所示，情况一向上调整过程中，产生了情况二 - ①：
对情况二进行平衡化操作：先单旋，再调整颜色（不管是哪种单旋，颜色调整都一样：p变黑，g变红）
注意：对局部的一颗子树平衡化操作，整个过程中，我们要保持当前子树的每条路径中黑色节点数量不变。
① 如果父亲 p 是祖父 g 的左孩子， cur 是父亲 p 的左孩子，先对祖父 g 进行右单旋；然后将父亲 p 变黑，祖父 g 变红：
- u不存在
- u存在且为黑
② 如果父亲 p 是祖父 g 的右孩子， cur 是父亲 p 的右孩子，先对祖父 g 进行进行左单旋；然后将父亲 p 变黑，祖父 g 变红：
- u不存在
- u存在且为黑
4.2.3 情况三
情况三：cur为红，p为红，g为黑，u不存在 / u存在且为黑
如图所示，情况一向上调整过程中，产生了情况三 - ①：
对情况三进行平衡化操作：先双旋，再调整颜色（不管是哪种双旋，颜色调整都一样：cur变黑，g变红）
注意：对局部的一颗子树平衡化操作，整个过程中，我们要保持当前子树的每条路径中黑色节点数量不变。
① 如果父亲 p 是祖父 g 的左孩子， cur 是父亲 p 的右孩子，先对父亲 p 进行左单旋，再对祖父 g 进行右单旋；然后将 cur 变黑，祖父 g 变红：
- u不存在
- u存在且为黑
② 如果父亲 p 是祖父 g 的右孩子，cur 是父亲 p 的左孩子，先对父亲 p 进行右单旋，再对祖父 g 进行左单旋；然后将 cur 变黑，祖父 g 变红：
- u不存在
- u存在且为黑
4.3 总结
插入节点后，控制树的近似平衡，操作总结如下，整个逻辑拉通了，还是挺简单的👇
当插入红色新节点 cur 后，如果父亲 p 存在且为红，说明破坏红黑树性质了，需要平衡化操作。
首先记录 cur 的父亲 p 和祖父 g 的位置，然后判断父亲 p 的位置：
1）如果父亲 p 是祖父 g 的左孩子：
说明叔叔u是祖父g的右孩子，先判断叔叔的状态：
-
如果「叔叔u存在且为红」，说明是情况一，直接先变色处理，然后再往上调整。
-
先调整颜色：父亲 p 和叔叔 u 变黑，祖父 g 变红。
-
再往上调整：原先祖父 g 当成新的 cur，判断新 cur 的父亲 p：
-
若父亲 p 不存在，说明调整到头了，停止调整，然后将根节点变黑。
-
若父亲 p 存在且为黑，没有破坏性质，停止调整。
-
若父亲 p 存在且为红，继续调整，并判断是否出现了情况二或三，要一直调整到 根节点 或者 父亲 p 存在且为黑 时，才停止调整。
-
-
-
如果「叔叔u不存在」或者「叔叔u存在且为黑」，说明是情况二或者情况三，先判断 cur 的位置：
- 如果 cur 是父亲 p 的左孩子（此时 cur、p、g是一条直线，说明是情况二）
- 进行右单旋 + 变色处理（父亲 p 变黑，祖父 g 变红）
- 如果 cur 是父亲 p 的右孩子（此时 cur、p、g是一条折线，说明是情况三）
- 进行左右双旋 + 变色处理（cur 变黑，祖父 g 变红）
- 上述情况二或三处理完成后，当前子树的根节点为黑 (p / cur)，没有连续红节点了，则停止调整。
- 如果 cur 是父亲 p 的左孩子（此时 cur、p、g是一条直线，说明是情况二）
2）如果父亲 p 是祖父 g 的右孩子：
说明叔叔u是祖父g的左孩子，先判断叔叔的状态：
-
如果「叔叔u存在且为红」，说明是情况一，先变色处理（p和u变黑，g变红），然后再往上调整，去判断新的父亲p的状态，检测新的子树是否平衡，如果不平衡，是出现了哪种情况(1/2/3)呢？
情况一处理方式类似于上面，此处略……
-
如果「叔叔u不存在」或者「叔叔u存在且为黑」，说明是情况二或者情况三，先判断 cur 的位置：
-
如果 cur 是父亲 p 的右孩子（此时 cur、p、g是一条直线，说明是情况二）
- 进行左单旋 + 变色处理（父亲 p 变黑，祖父 g 变红）
-
如果 cur 是父亲 p 的左孩子（此时 cur、p、g是一条折线，说明是情况三）
- 进行右左单旋 + 变色处理（cur 变黑，祖父 g 变红）
-
上述情况二或三处理完成后，当前子树的根节点为黑 (p / cur)，没有连续红节点了，则停止调整。
-
要注意下，上面几个停止调整，是循环的出口，否则就要一直调整到 根节点 或者 父亲 p 存在且为黑 时
代码如下：
// 插入节点 bool Insert(const pair<K, V>& kv) { /* ----------------------------------------------------------------- */ /* 一、查找到适合插入的空位置 */ // 树为空 if (_root == nullptr) { _root = new Node(kv); // 插入新节点 _root->_col = BLACK; // 根节点为黑色 return true; } // 树不为空 Node* cur = _root; // 记录当前节点和它的父节点 Node* parent = nullptr; while (cur) // cur为空时，说明找到插入位置了 { if (kv.first > cur->_kv.first) // 键值大于当前节点 { parent = cur; cur = cur->_right; } else if (kv.first < cur->_kv.first) // 键值小于当前节点 { parent = cur; cur = cur->_left; } else if (kv.first == cur->_kv.first) // 键值等于当前节点 { return false; // 不允许数据冗余，返回false } } // 插入新节点，颜色为红色（可能会破坏性质3，产生两个连续红色节点） cur = new Node(kv); cur->_col = RED; // 判断新节点是其父亲的左孩子还是右孩子 if (cur->_kv.first > parent->_kv.first) { // 建立parent和cur之间的联系 parent->_right = cur; cur->_parent = parent; // 更新cur的双亲指针 } else { // 建立parent和cur之间的联系 parent->_left = cur; cur->_parent = parent; // 更新cur的双亲指针 } /* ----------------------------------------------------------------- */ /* 二、检测红黑树性质有没有被破坏，并控制树的平衡 */ // 如果cur的父亲p存在且为红，则树不平衡，就需要一直往上调整 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; // 记录cur的祖父grandfather // 1、如果parent是grandfather的左孩子 if (parent == grandfather->_left) { Node* uncle = grandfather->_right; // uncle是grandfather的右孩子 /* 调整的关键：判断叔叔的状态，得知具体是哪种情况，然后再进行处理 */ // （1）uncle存在且为红，说明是情况1 if (uncle && uncle->_col == RED) { // 调整颜色 parent->_col = uncle->_col = BLACK; // parent和uncle变黑 grandfather->_col = RED; // grandfather变红 // 继续往上调整 // 去判断新的父亲p的状态，检测新的子树是否平衡，如果不平衡，出现了哪种情况(1/2/3) cur = grandfather; // 更新cur和parent parent = cur->_parent; } // （2）uncle不存在/存在且为黑，说明是情况2或3 else if (uncle == nullptr || uncle->_col == BLACK) { // 先判断cur的位置： if (cur == parent->_left) // 如果cur是parent的左孩子，说明是情况2 { // 单旋 + 调整颜色 RotateRight(grandfather); // 右单旋 parent->_col = BLACK; // parent变黑 grandfather->_col = RED; // grandfather变红 } else if(cur == parent->_right) // 如果cur是parent的右孩子，说明是情况3 { // 双旋 + 调整颜色 RotateLeft(parent); // 左单旋 RotateRight(grandfather); // 右单旋 cur->_col = BLACK; // cur变黑 grandfather->_col = RED; // grandfather变红 } // 情况2或3处理完成后，当前子树的根节点为黑，没有连续红节点了，则停止调整 break; } } // 2、如果parent是grandfather的右孩子 else if (parent == grandfather->_right) { Node* uncle = grandfather->_left; // uncle是grandfather的左孩子 /* 调整的关键：判断叔叔的状态，得知具体是哪种情况，然后再进行处理*/ // (1) uncle存在且为红，说明是情况1 if (uncle && uncle->_col == RED) { // 调整颜色 parent->_col = uncle->_col = BLACK; // parent和uncle变黑 grandfather->_col = RED; // grandfather变红 // 继续往上调整 // 去判断新的父亲p的状态，检测新的子树是否平衡，如果不平衡，出现了哪种情况(1/2/3) cur = grandfather; // 更新cur和parent parent = cur->_parent; } // (2) uncle不存在/存在且为黑，说明是情况2或3 else if (uncle == nullptr || uncle->_col == BLACK) { // 先判断cur的位置： if (cur == parent->_right) // 如果cur是parent的右孩子，说明是情况2 { // 单旋 + 调整颜色 RotateLeft(grandfather); // 左单旋 parent->_col = BLACK; // parent变黑 grandfather->_col = RED; // grandfather变红 } else if (cur == parent->_left) // 如果cur是parent的左孩子，说明是情况3 { // 双旋 + 调整颜色 RotateRight(parent); // 右单旋 RotateLeft(grandfather); // 左单旋 cur->_col = BLACK; // cur变黑 grandfather->_col = RED; // grandfather变红 } // 情况2或3处理完成后，当前子树的根节点为黑，没有连续红节点了，则停止调整 break; } } } // 运行到这里来了，说明： // 1. cur的父亲p不存在，则cur就是根节点，将根节点变黑 // 2. cur的父亲p存在且为黑，树是平衡的，结束调整 _root->_col = BLACK; // 根节点变黑 /* ----------------------------------------------------------------- */ return true; } // 左单旋 void RotateLeft(Node* parent) { Node* subR = parent->_right; // 记录parent的右孩子 Node* subRL = subR->_left; // 记录parent右孩子的左孩子 // 建立parent和subRL之间的联系 parent->_right = subRL; if (subRL) subRL->_parent = parent; // 建立subR和parent之间的联系 Node* pp = parent->_parent; // 先记录下parent的父节点 subR->_left = parent; parent->_parent = subR; // 建立pp和subR之间的联系 if (pp == nullptr) // pp为空，说明parent原先是根节点 { _root = subR; // subR为新的根节点 subR->_parent = nullptr; // subR的双亲指针指向空 } else if(pp != nullptr) // pp不为空，说明parent原先是一个普通子树 { // 判断parent原先是父亲pp的左孩子还是右孩子 if (parent == pp->_left) { pp->_left = subR; } else if (parent == pp->_right) { pp->_right = subR; } subR->_parent = pp; // subR的双亲指针指向pp } } // 右单旋 void RotateRight(Node* parent) { Node* subL = parent->_left; // 记录parent的左孩子 Node* subLR = subL->_right; // 记录parent左孩子的右孩子 // 建立parent和subLR之间的联系 parent->_left = subLR; if (subLR) subLR->_parent = parent; // 建立subL和parent之间的联系 Node* pp = parent->_parent; // 先记录下parent的父节点 subL->_right = parent; parent->_parent = subL; // 建立pp和subL之间的联系 if (pp == nullptr) // pp为空，说明parent原先是根节点 { _root = subL; // subL为新的根节点 subL->_parent = nullptr; // subL的双亲指向指向空 } else if (pp != nullptr) // pp不为空，说明parent原先是一个普通子树 { // 判断parent原先是pp的左孩子还是右孩子 if (parent == pp->_left) { pp->_left = subL; } else if (parent == pp->_right) { pp->_right = subL; } subL->_parent = pp; // subL的双亲指针指向pp } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
五、红黑树的验证
红黑树的检测分为两步：
-
检测其是否满足二叉搜索树(中序遍历是否为有序序列)
-
检测其是否满足红黑树的性质
-
根节点是否为黑色
-
是否存在连续红节点
-
统计每条路径上的黑节点数是否相等
-
① 检测是否存在连续红节点：
// 检测红黑树是否有连续红节点 bool CheckRedRed(Node* root) { if (root == nullptr) return true; // 思路1：如果当前节点为红色，检测它的孩子是否为红色，但孩子可能为空，每次还得判断孩子是否为空，太麻烦了 // 思路2：如果当前节点为红色，我们去检测它的父亲是否为红色 // 因为根节点没有父亲，且根节点为黑色，是不会被判断的 if (root->_col == RED && root->_parent->_col == RED) { cout << "出现连续红节点，违反性质了" << endl; return false; } // 继续判断当前节点的左右孩子 return CheckRedRed(root->_left) && CheckRedRed(root->_right); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
② 检测每条路径上的黑节点数是否相等：
首先计算出红黑树其中一条路径的黑节点数，作为一个 baseValue 基准值(参考值)
然后再求出红黑树每条路径的黑节点数，与基准值比较，如果不相等，说明违反性质了。
- blackNum：表示从根节点到当前节点的黑节点数
- baseValue：基准值（最左侧路径的黑节点数）
// 计算红黑树最左侧这条路径的黑节点数，作为基准值(参考值) int CountBaseValue() { int count = 0; // 统计黑节点数 Node* cur = _root; while (cur) // 遇到NIL时，统计结束 { if (cur->_col == BLACK) count++; cur = cur->_left; } return count; } /* 检测红黑树每条路径的黑节点数是否相等 * 思路：求出每条路径的黑节点数，与基准值比较，如果不相等，说明违反性质了 * blackNum：表示从根节点到当前节点的黑节点数，默认从0开始 * baseValue：基准值（最左侧路径的黑节点数） */ bool CheckBlackNums(Node* root, int blackNum, int baseValue) { // 当前节点为空，说明遇到了NIL，判断该路径的黑节点数是否等于基准值 if (root == nullptr) { if (blackNum != baseValue) { cout << "每条路径黑节点数不相等，违反性质了" << endl; return false; } else return true; } // 当前节点为黑色，则从根节点到当前节点的黑节点数加1 if (root->_col == BLACK) blackNum++; return CheckBlackNums(root->_left, blackNum, baseValue) && CheckBlackNums(root->_right, blackNum, baseValue); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
【注意】：
这里计算每条路径的黑节点数 blackNum 时，使用的是传值，因为这样就可以在递归的过程中计算到每条路径的黑节点数，因为每个函数栈帧中的 blackNum 变量都是独立存在的。
下一层的 blackNum 是上一层的拷贝，下一层中++，不会影响上一层。
比如在 黑节点1 中对 blackNum++，变成2，但 红节点8 中的 blackNum 值还是1，所以就不会影响到计算右孩子即 黑节点11 所在路径的黑节点数。
求一棵树的叶子节点数和总的节点数，就可以用引用
红黑树的验证代码如下：
// 检测红黑树是否平衡 bool IsBalance() { if (_root == nullptr) return true; // 1、检测红黑树的根节点是否为红色 if (_root->_col == RED) { cout << "根节点为红色，违反性质了" << endl; return false; // 直接返回false } // 2、CheckRedRed：检测红黑树是否有连续红节点 // 3、CheckBlackNums：检测红黑树每条路径黑节点数是否相等 return CheckRedRed(_root) && CheckBlackNums(_root, 0, CountBaseValue()); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
用n个随机值元素来测试红黑树：
int main() { // 用n个随机值元素来测试红黑树 // 定义r的向量 const int n = 1000000; vector<int> a; a.reserve(n); // 初始化随机种子 srand(time(0)); for (size_t i = 0; i < n; i++) { // 生成随机值 a.push_back(rand()); // 如果只写rand()，这样生成的随机值不是真的随机，每次都是一样的 // 所以要初始化随机数生成器srand()，给它一个随机种子 } // 定义红黑树，插入n个元素 RBTree<int, int> rb; for (auto& e : a) { rb.Insert(make_pair(e, e)); } // 打印验证结果 cout << rb.IsBalance() << endl; return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
观察运行结果，插入n个元素后，红黑树是平衡的。
六、红黑树的删除（了解）
因为红黑树也是二叉搜索树，可按照二叉搜索树的方式将节点删除。
- 如果删除的一个红色节点，是不会违反任何规则的，
- 如果删除的是黑色节点，一定会破坏规则，导致每条路径上的黑节点数不相等了，这个时候就要小心了，我们要进行平衡化操作（旋转、变色），使树平衡。
推荐文章：红黑树 - Never - 博客园 (cnblogs.com)
七、红黑树的应用
-
C++ STL库 – map/set、mutil_map/mutil_set
-
Java 库
-
linux内核
-
其他一些库
-
相关阅读:
MySQL安装_win10（超详细）
java使用正则提取数据
升级PIP
SpringBoot学习之Redis下载安装启动【Mac版本】（三十七）
移动应用开发之路 01 Android Studio 项目文件介绍、创建虚拟机、完成第一个程序Hello World
《MLB棒球创造营》：走近棒球运动·西雅图水手队
Android——基本动画的使用
docker安装mysql（单体）
LeetCode·297.二叉树的序列化与反序列化·DFS·BFS
Ernie-gram, 显式、完备的 n-gram 掩码语言模型，实现了显式的 n-gram 语义单元知识建模。
- 原文地址：https://blog.csdn.net/weixin_48025315/article/details/125395585