红黑树详解：概念、规则与插入实现

红黑树

概念

也是以二叉搜索树为基础的，每个节点单位以​pair储存

他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

‍

储存规则

1. 每个结点不是红色就是黑色
2. 根结点是黑色的
3. 如果一个结点是红色的，则它的两个子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。
4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点

说明：《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道一下这个概念即可。

NIL。意味NULL。是空的意思

‍

注：空树也是红黑树，满足

• 每个结点不是红就是黑：空树没有结点，没有反例，成立。
• 根结点是黑色的：空树没有根结点，自然不违反“根必须是黑”的规则。或者可以理解为，空指针本身就是一个黑色的外部结点（NIL）。
• 红色结点的子结点必为黑：没有红色结点，成立。
• 所有路径包含相同数量的黑色结点：空树的所有路径（只有一条长度为零的路径）包含的黑色结点数都是相同的（通常黑高 Black Height 记为 0）。没有反例，成立。

‍

‍

路径：根节点到空节点

最短路径：h

最长路径：2*h

最短路径特点：全黑

最长路径特点：红黑交替

‍

红黑树是怎么保证最长路径不超过最短路径的2倍？

依据三条规则：

• 从根到任意 ​NIL空叶子的路径，黑节点数量相同。
• 红节点的孩子必须是黑节点。
• 根节点是黑色。

设路径上有b个黑色节点（不计末尾​NIL），那么最短路径至少有b个节点，他们都是黑色，那么最长路径的最长结果就是这b个黑色节点与红色节点交替出现，最多有b个红色节点出现，那么最长路径就是2b个节点

‍

效率

假设N是红黑树树中结点数量，h最短路径的长度，那么2 h − 1 ≤ N < 2 2 ∗ h − 1 2^h - 1 \le N < 2^{2*h} - 12h−1≤N<22∗h−1，由此推出
h ≈ l o g N h \approx logNh≈logN，也就是意味着红黑树增删查改最坏也就是走最长路径2 ∗ l o g N 2*logN2∗logN，那么时间复杂度还是O(logN)

红黑树的表达相对AVL树要抽象一些，AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束，间接的实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

‍

红黑树的查找：

按照搜索二叉树的规则来查找，效率也是logN

插入逻辑

1. 也是按照二叉搜索树的规则来进行

2. 如果是空树，那么直接插入黑色节点（要满足根节点是黑色的规则）

   如果不是空树，就必须插入红色（保证黑色节点总数始终保持不变，因为该规则最难维护，那么出现两个红色节点连续出现怎么办，后面通过旋转解决）

3. 如果非空节点插入红色，父节点是黑色，那么没有违反任何规则，插入结束

4. 如果非空节点插入红色，父节点也是红色，那么违反了红色节点不能连续出现的规则

   设当前节点为​cur​（简称c），父节点为​parent​（简称p），父节点的兄弟节点为​uncle​（简称u），父节点的父节点为​grandparent（简称g）

   进一步分析：c红，p红，g必为黑，那么就只要看u的颜色来分析，根据u分为下面几种情况来处理

‍

一共三种情况情况

一：只变色

c红p红g黑，u为红：

那么要将p和u变黑，g变红（因为，g的左右子树为p、u/u、p，要保证每条路的黑色数量不变就必须把g变红，p、u变黑，这同时也解决了红色连续的问题）。再把g当做新的c向上更新，如果g的父亲是红色，那么还要继续处理，如果是黑色就结束了；如果g就是整棵树的根节点，那么再把g变回黑色

情况1只变色，不旋转。所以无论c是p的左还是右，p是g的左还是右，都是上面的变色处理方式。

下面参考图由具体到抽象

‍

二：单旋+变色

c为红，p为红，g为黑，u为黑或u为空

• 当u为空时，c一定是新插入节点，直接进行旋转

• 当u为黑时，c一定不是新插入节点，而是由下面的节点通过情况一变色变上来的

三：双旋+变色

c为红，p为红，g为黑，u为空或u为黑

• u为空时，c一定是新增节点
• u不为空，与情况二同理，是变色变上来的

这里因为c节点出现在p节点的另一侧（参考AVL树双旋的情况），需要进行双旋

‍

尝试实现

#pragma once // 枚举值表示颜色 enum Colour { RED, BLACK }; // 这里我们默认按key/value结构实现 template<class K, class V> struct RBTreeNode { // 这里更新控制平衡也要加入parent指针 pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; RBTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: //右旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = parent->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent->_left; Node* Parentparent = parent->_parent; subL->_right = parent; parent->_parent = subL; // parent有可能是整棵树的根，也可能是局部的⼦树 // 如果是整棵树的根，要修改_root // 如果是局部的指针要跟上⼀层链接 if (Parentparent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (Parentparent->_left == parent) { Parentparent->_left = subL; } else if (Parentparent->_right == parent) { Parentparent->_right = subl; } subL->_parent = Parentparent; } parent->_bf = subL->_bf = 0; } //右旋 void RotateL(const Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_left = subRL; if (subRL) subRL->_parent = parent->_left; Node* Parentparet = parent->_parent; subR->_right = parent; parent->_parent = subR; if (Parentparet == nullptr) { _root = subR; subR->_parent = nullptr; } else { if (Parentparet->_left == parent) { Parentparet->_left = subR; } else if (Parentparet->_right == parent) { Parentparet->_right = subR; } subR->_parent = Parentparet; } parent->_bf = subR->_bf = 0; } 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); cur->_col = RED; if (parent->kv.first < kv.first) { cur = parent->left; } else { cur = parent->_right } cur->_parent = parent; while (parent && parent->_col == RED)//parent存在且为红 { Node* grandfa = parent->_parent; if (parent == grandfa->_left)//parent在grandfa左 { Node* uncle = grandfa->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfa->_col = RED; //继续往上处理 cur = grandfa; parent = cur->_parent; } else//uncle为黑或不存在 { //parent与cur都在左侧 if (cur = parent->_left) { RotateR(grandfa);//单旋，右旋 parent->_col = BLACK; grandfa->_col = RED } else//parent在grandfa左侧,cur在parent右侧 { RotateL(parent); RotateR(grandfa); cur->_col = BLACK; parent->_col = BLACK; grandfa->_col = RED; } break; } } else//parent在grandfa的右 { Node* uncle = grandfa->_left; //uncle存在，且为红，直接变色 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfa->_col = RED; //继续往上处理 cur = grandfa; parent = cur->_parent; } else//uncle不存在或为黑 { if (cur == parent->_right)//parent在grandfa右侧，cur在parent右侧 { RotateL(grandfa);//单旋，左旋 parent->_col = BLACK; grandfa->_col = RED; } else//parent在grandfa右侧，cur在parent左侧 { RotateR(parent); RotateL(grandfa); parent->_col = BLACK; grandfa->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return true; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } // 前序递归遍历检查 bool Check(Node* root, int blackNum, const int refNum) { if (root == nullptr) { // 前序遍历走到空时，意味着一条路径走完了 //cout << blackNum << endl; if (refNum != blackNum) { cout << "存在黑色结点的数量不相等的路径" << endl; return false; } return true; } // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了 if (root->_col == RED && root->_parent && root->_parent->_col == RED) { cout << root->_kv.first << "存在连续的红色结点" << endl; return false; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); } bool IsBalanceTree() { if (_root == nullptr) return true; if (_root->_col == RED) return false; // 参考值 int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refNum; } cur = cur->_left; } return Check(_root, 0, refNum); } private: Node* _root = nullptr; };

‍

完