【数据结构】红黑树

文章目录 1, 红黑树的概念2. 红黑树的性质3. 红黑树节点的定义4. 红黑树的结构5. 红黑树的插入操作6. 红黑树的验证7. 红黑树与 AVL 树的比较8. 红黑树的应用

1, 红黑树的概念

红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。

2. 红黑树的性质 每个节点不是红色就是黑色；根节点是黑色的；如果一个节点是红色的，则它的两个孩子节点是黑色的；对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；每个叶子节点都是黑色的（此处的叶子节点指的是空节点）。

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

3. 红黑树节点的定义 // 节点的颜色 enum Color { RED, BLACK }; // 红黑树节点的定义 template<class ValueType> struct RBTreeNode { RBTreeNode(const ValueType& data = ValueType()，Color color = RED) : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr) , _data(data), _color(color) {} RBTreeNode<ValueType>* _pLeft; // 节点的左孩子 RBTreeNode<ValueType>* _pRight; // 节点的右孩子 RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段) ValueType _data; // 节点的值域 Color _color; // 节点的颜色 };

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？

4. 红黑树的结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头节点，因为根节点必须为黑色，为了与根节点进行区分，将头节点给成黑色，并且让头节点的 pParent 域指向红黑树的根节点，pLeft 域指向红黑树中最小的节点，pRight 域指向红黑树中最大的节点，如下：

5. 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

按照二叉搜索树的树规则插入新节点：

template<class ValueType> class RBTree { //…… bool Insert(const ValueType& data) { PNode& pRoot = GetRoot(); if (nullptr == pRoot) { pRoot = new Node(data, BLACK); // 根的双亲为头节点 pRoot->_pParent = _pHead; _pHead->_pParent = pRoot; } else { // 1. 按照二叉搜索的树方式插入新节点 // 2. 检测新节点插入后，红黑树的性质是否造到破坏， // 若满足直接退出，否则对红黑树进行旋转着色处理 } // 根节点的颜色可能被修改，将其改回黑色 pRoot->_color = BLACK; _pHead->_pLeft = LeftMost(); _pHead->_pRight = RightMost(); return true; } private: PNode& GetRoot() { return _pHead->_pParent; } // 获取红黑树中最小节点，即最左侧节点 PNode LeftMost(); // 获取红黑树中最大节点，即最右侧节点 PNode RightMost(); private: PNode _pHead; };

检测新节点插入后，红黑树的性质是否遭到破坏：

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三：不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点。

情况一：cur 为红，p 为红，g 为黑，u 存在且为红

cur 和 p 均为红，违反了性质三，此处能否将 p 直接改为黑？

解决方式：将 p，u 改为黑，g 改为红，然后把 g 当成 cur，继续向上调整。

情况二：cur 为红，p 为红，g 为黑，u 不存在 / u 存在且为黑

p 为 g 的左孩子，cur 为 p 的左孩子，则进行右单旋转；相反， p 为 g 的右孩子，cur 为 p 的右孩子，则进行左单旋转； p、g 变色 – p 变黑，g 变红。

情况三：cur 为红，p 为红，g 为黑，u 不存在 / u 存在且为黑

p 为 g 的左孩子，cur 为 p 的右孩子，则针对 p 做左单旋转；相反， p 为 g 的右孩子，cur 为 p 的左孩子，则针对 p 做右单旋转； 则转换成了情况 2。

针对每种情况进行相应的处理即可。

bool Insert(const ValueType& data) { // ... // 新节点插入后，如果其双亲节点的颜色为空色，则违反性质3：不能有连在一起的红色结点 while (pParent && RED == pParent->_color) { // 注意：grandFather一定存在 // 因为pParent存在，且不是黑色节点，则pParent一定不是根，则其一定有双亲 PNode grandFather = pParent->_pParent; // 先讨论左侧情况 if (pParent == grandFather->_pLeft) { PNode unclue = grandFather->_pRight; // 情况三：叔叔节点存在，且为红 if (unclue && RED == unclue->_color) { pParent->_color = BLACK; unclue->_color = BLACK; grandFather->_color = RED; pCur = grandFather; pParent = pCur->_pParent; } else { // 情况五：叔叔节点不存在，或者叔叔节点存在且为黑 if (pCur == pParent->_pRight) { _RotateLeft(pParent); swap(pParent, pCur); } // 情况五最后转化成情况四 grandFather->_color = RED; pParent->_color = BLACK; _RotateRight(grandFather); } } else { // 右侧请大家自己动手完成 } } // ... } 6. 红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树（中序遍历是否为有序序列）；检测其是否满足红黑树的性质。 bool IsValidRBTree() { PNode pRoot = GetRoot(); // 空树也是红黑树 if (nullptr == pRoot) return true; // 检测根节点是否满足情况 if (BLACK != pRoot->_color) { cout << "违反红黑树性质二：根节点必须为黑色" << endl; return false; } // 获取任意一条路径中黑色节点的个数 size_t blackCount = 0; PNode pCur = pRoot; while (pCur) { if (BLACK == pCur->_color) blackCount++; pCur = pCur->_pLeft; } // 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数 size_t k = 0; return _IsValidRBTree(pRoot, k, blackCount); } bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount) { //走到null之后，判断k和black是否相等 if (nullptr == pRoot) { if (k != blackCount) { cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl; return false; } return true; } // 统计黑色节点的个数 if (BLACK == pRoot->_color) k++; // 检测当前节点与其双亲是否都为红色 PNode pParent = pRoot->_pParent; if (pParent && RED == pParent->_color && RED == pRoot->_color) { cout << "违反性质三：没有连在一起的红色节点" << endl; return false; } return _IsValidRBTree(pRoot->_pLeft, k, blackCount) && _IsValidRBTree(pRoot->_pRight, k, blackCount); } 7. 红黑树与 AVL 树的比较

红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

8. 红黑树的应用 C++ STL 库 – map / set、multi_map / multi_set；Java 库；Linux 内核；其他一些库；…

---

END