1.伸展树介绍
一种与 AVL 树类似的改进的二叉搜索树，称为伸展树.是由 John Edward Hopcroft 和 Robert Endre Tarjan 于 1985 年共同发明的。与 AVL 树以及在并查集时的父指针表示的树的路径压缩一样，同属于自调整数据结构。在讨论 AVL 树时，主要关注点在于保持树的高度平衡，不要倾斜向一方，理想情况下使叶结点只出现在最低的一层或两层上。因此，如果一个新插入的结点破坏了树的平衡，就需要通过平衡旋转来加以调整。然而，是否这种重新调整总是必要的呢？对于二叉搜索树来说，它主要用于内存中目录的编制，因此，快速插入、搜索、删除元素才是我们关心的问题，而不是树的形状。通过平衡树可以提高效率，但这不是唯一的方法。
伸展树就是另一种提高搜索效率的方法。它参照了以下两种想法： ⑴单一旋转：其目的是将经常访问的结点最终上移到靠近根的地方，使得以后的访问比以前更快。为此，除根结点外，只要访问子女结点，就将它围绕它的父结点进行旋转。 ⑵移动到根部：假设正在访问的结点将以很高的概率再次被访问，因此，对它反复进行子女—父结点旋转，直到被访问的结点位于根部为止。这样，即使下一次没有访问此结点，它仍然还在靠近根部的地方。
伸展树发展了上述想法，它提出了一组改进二叉搜索树性能的一组规则，每当执行搜索、插入、删除等操作时，就要依据这些规则调整二叉搜索树，从而保证操作的时间代价。 每当访问 (包括搜索、插入或删除) 一个结点 s 时，伸展树就执行一次叫做'展开'的过程。'展开'将结点 s 移到二叉搜索树的根部。当删除结点 s 时，'展开'把结点 s 的父结点上移到根结点。就像 AVL 树，一次'展开'由一组旋转组成。旋转有三种类型：单旋转、一字形旋转和之字形旋转。一次旋转的目的是通过调整结点 s 与它的父结点 p 和祖父结点 g 之间位置，把它上移到树的更高层。下面分情况讨论。 ①情况 1:被访问结点 s 的父结点是根结点。此时执行单旋转，如图 7.26 所示。在保持二叉搜索树特性的情况下，结点 s 成为新的根，原来的根 p 成为它的子女结点。 ②情况 2:同构的形状。结点 s 是其父结点 p 的左子女，结点 p 又是其父结点 g 的左子女 (/)。或者结点 s 是其父结点 p 的右子女，结点 p 又是其父结点 g 的右子女 ()。此时执行一字形旋转，如图 7.27 所示。这是一个双旋转：首先围绕 p 旋转 g，再围绕 s 旋转 p。旋转发生后，当前刚访问的结点 s 调整到祖父结点的位置，同时仍保持了二叉搜索树的特性。 ③情况 3:异构的形状。结点 s 是其父结点 p 的左子女，结点 p 又是其父结点 g 的右子女 (>)。或者结点 s 是其父结点 p 的右子女，结点 p 又是其父结点 g 的左子女 (<=)。此时执行之字形旋转，如图 7.28 所示。因为刚访问的结点 s 与其父结点 p 和祖父结点 g 形成折线，需要做与 AVL 树一样的双旋转，首先围绕 s 旋转 p，再围绕 s 旋转 g，把结点 s 上升到祖父结点的位置，并保持二叉搜索树的特性。
之字形旋转使得树结构趋向于平衡化，它将子树β和γ上升一层，并把子树δ下降一层，结果常常使树结构的高度减少 1。而一字形旋转一般不会降低树结构的高度，它只是把刚访问的结点向根结点上移。 被访问结点 s'展开'过程的算法描述如下面程序所示，它包括了一系列双旋转，提升结点 s 直到它到达根结点或根结点的一个子女结点。必要的话，再执行一次单旋转将 s 上升到根结点位置。'展开'的结果使得访问最频繁的结点靠近树结构的根部，从而减少访问代价。
splaying(g, p, s){ //g 是 p 的父结点，p 是 s 的父结点。算法将 s 移到根结点位置
while(s 不是树的根结点)
if(s 的父结点是根结点) 进行单旋转，将 s 调整为根结点
else if(s 与它的前驱 p,g 是同构形状) 进行一字形双旋转，将 s 上移
else //s 与它的前驱 p,g 是异构形状 进行之字形双旋转，将 s 上移
};
伸展树并不要求每一个操作都是高效的，但是对于一个有 n 个结点的树结构，并执行 m 次操作的情形，可能一次插入或搜索操作需要花费 O(n) 时间，当 m>=n 时，所有 m 个操作总共需要 O(m log_2 n) 时间，从而使每次访问操作所花费的平均时间达到 O(log_2 n) 从整体上保持较高的时间性能。证明伸展树实能够保证达到 O(m log_2 n) 的时间复杂性已经超出小编所知道的范围，详细的讨论请参考 Adam Drozdek 的 Data Structures and Algorithms in C++ (Second Edition)。 图 7.29 描述了伸展树是如何通过'展开'实现自调整的。首先在伸展树中搜索 70，搜索过程与二叉搜索树完全一样，一旦搜索成功，就执行'展开'过程将该结点上移到根结点位置。
伸展树的插入操作与二叉搜索树相同，但结点一经插入之后立即展开到根结点。同样，从伸展树中删除一个结点的操作也与二叉搜索树相同，但需要把被删结点的父结点展开到根结点。伸展树与 AVL 树在操作上稍有不同。伸展树的调整与结点被访问 (包括搜索、插入、删除) 的频率有关，能够进行更合理的调整。而 AVL 树的结构调整只与插入、删除的顺序有关，与访问的频率无关。
2.红⿊树介绍
2.1 红⿊树的概念
红⿊树是⼀棵⼆叉搜索树，它的每个结点增加⼀个存储位来表示结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出 2 倍，因⽽是接近平衡的。红黑树是这样的一棵二叉搜索树：树中的每一个结点的颜色不是黑色就是红色。可以把一棵红黑树视为一棵扩充二叉树，用外部结点表示空指针。
2.2 红⿊树的性质
①根结点和所有外部结点的颜色是黑色。 ②从根结点到外部结点的途中没有连续两个结点的颜色是红色。 ③所有从根到外部结点的路径上都有相同数目的黑色结点。
从红黑树中任一结点 x 出发 (不包括结点 x)，到达一个外部结点的任一路径上的黑结点个数叫做结点 x 的黑高度，亦称为结点的阶记作 bh(x)。红黑树的黑高度定义为其根结点的黑高度。 图 7.30 所示的二叉搜索树就是一棵红黑树。结点旁边的数字为该结点的黑高度。
另一种等价的定义是看结点指针的颜色。从父结点到黑色子女结点的指针为黑色的，从父结点到红色子女结点的指针为红色的。 ⓵从内部结点指向外部结点的指针是黑色的。 ⓶从根结点到外部结点的途中没有两个连续的红色指针。 ⓷所有根到外部结点的路径上都有相同数目的黑色指针。 如果知道指针的颜色，就能推断结点的颜色，反之亦然。图 7.31 给出用指针颜色表示的红黑树，它与图 7.30 所示红黑树等价。树中的粗线是黑色指针，细线是红色指针。从指针的颜色和特性 1 可知，结点 20、40、70 是红色的，因为指向它们的指针是红色的，其余的结点都是黑色的。此外，从根到外部结点的每条路径上都有 2 个黑色指针和 3 个黑色结点 (包括根与外部结点)，不存在含有两个连续红色结点或指针的路径。
结论 1:设从根到外部结点的路径长度 (Path Length, PL) 为该路径上指针的个数，如果 P 与 Q 是红黑树中的两条从根到外部结点的路径，则有: PL(P) ⩽ 2PL(Q) 证明：考查任意一棵红黑树。假设根结点的黑高度 bh(root)=r。由特性 1' 可知，每条从根结点到外部结点的路径中最后一个指针为黑色;从特性 2' 可知，不存在有连续两个红色指针的路径。因此，每个红色指针后面都会跟随一个黑色指针，从而每条从根到外部结点的路径上都有 r ~ 2r 个指针，综上所述，有 PL(P) ⩽ 2PL(Q)。参看图 7.31，从根到 40 左下的外部结点的路径长度 PL(40)=4，从根到 70 右下的外部结点的路径长度 PL(70)=3，因此 PL(40) ⩽ PL(70) 或者 PL(70) ⩽ PL(40)。
结论 2:设 h 是一棵红黑树的高度 (不包括外部结点), n 是树中内部结点的个数，r 是根结点的黑高度，则以下关系式成立: (1) h ⩽ 2r (2) n ⩾ 2^r - 1 (3) h ⩽ 2log_2(n+1)
证明： (1)从结论 1 的证明可知，从根到任一外部结点的路径长度不超过 2r，同时从树的定义可知，树的高度即为根结点的高度，等于从根到离根最远的外部结点的路径的长度，因此有 h ⩽ 2r。例如，在图 7.31 中红黑树的高度 (不计外部结点) 为 2r = 4。 (2)因为红黑树的黑高度为 r，则从树的第 1 层到第 r 层没有外部结点，因而在这些层中有 2^r - 1 个内部结点，就是说，内部结点的总数至少为 2^r - 1。例如，在图 7.31 所示的红黑树中，树的黑高度为 r=2，第 1 层和第 2 层共有 2^2 - 1 = 3 个内部结点，而在第 3 层和第 4 层还有 4 个内部结点，则有 n ⩾ 2^r - 1。 (3)由 (2) 可得 r ⩽ log_2(n+1)，结合 (1)，有 h ⩽ 2log_2(n+1)。
由于红黑树的高度最大为 2log_2(n+1)，所以，搜索、插入、删除操作的时间复杂性为 O(log_2 n)。注意，最差情况下的红黑树的高度大于最差情况下具有相同结点个数的 AVL 树的高度) 近似于 1.44log_2(n+2)。 红黑树继承了二叉搜索树的定义，一些数据成员和成员函数可以直接使用二叉搜索树的成员。 《算法导论》等书籍上补充了⼀条每个叶⼦结点 (NIL) 都是⿊⾊的规则。它这⾥所指的叶⼦结点不是传统的意义上的叶⼦结点，⽽是我们说的空结点，有些书籍上也把 NIL 叫做外部结点。NIL 是为了⽅便准确的标识出所有路径，《算法导论》在后续实现的细节中也忽略了 NIL 结点，所以我们知道⼀下这个概念即可。我们通过图片形象理解一下
2.3 红⿊树如何确保最⻓路径不超过最短路径的 2 倍的？
1️⃣从根到 NULL 结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就就是全是⿊⾊结点的路径，假设最短路径⻓度为 bh(black height)。 2️⃣由性质 2 和性质 3 可知，任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀⿊⼀红间隔组成，那么最⻓路径的⻓度为 2bh。 3️⃣综合红⿊树的性质⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到 NULL 结点路径的⻓度为 x，那么 bh <= h <= 2bh。
2.4 红⿊树的效率
假设 N 是红⿊树树中结点数量，h 最短路径的⻓度，那么，由此推出，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径，那么 2h − 1 <= N < 2^(2*h) − 1。由此推出 h ≈ logN 也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径，那么时间复杂度还是 O(logN)。 红⿊树的表达相对 AVL 树要抽象⼀些，AVL 树通过⾼度差直观的控制了平衡。红⿊树通过性质的颜⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为它对平衡的控制没那么严格。
3.红⿊树的实现
3.1 红⿊树的结构
// RBTree.h
#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:
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) {
parent->_right = cur;
} else {
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
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 // 叔叔不存在，或者叔叔存在且为黑->旋转 + 变色
{
if (cur == parent->_left) {
// g
// p u
// c
// 右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// g
// p u
// c
// 左右单旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else // grandfather->_right == parent
{
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔存在且为红，-》变色即可
if (uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
} else // 叔叔不存在，或者存在且为黑
{
// 情况二：叔叔不存在或者存在且为黑
// 旋转 + 变色
// g
// u p
// c
if (cur == parent->_right) {
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void InOrder() {
_InOrder(_root);
cout << endl;
}
bool IsBalance() {
if (_root == nullptr) return true;
if (_root->_col == RED) return false;
// 黑色节点数量参考值
Node* leftMost = _root;
int blackRef = 0;
while (leftMost) {
if (leftMost->_col == BLACK) ++blackRef;
leftMost = leftMost->_left;
}
return Check(_root, 0, blackRef);
}
int Height() {
return _Height(_root);
}
int Size() {
return _Size(_root);
}
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first < key) {
cur = cur->_right;
} else if (cur->_kv.first > key) {
cur = cur->_left;
} else {
return cur;
}
}
return nullptr;
}
private:
int _Size(Node* root) {
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}
int _Height(Node* root) {
if (root == nullptr) return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool Check(Node* cur, int blackNum, const int blackNumRef) {
if (cur == nullptr) {
if (blackNum != blackNumRef) {
cout << "黑色节点的数量不相等" << endl;
return false;
}
return true;
}
if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED) {
cout << cur->_kv.first << "->" << "连续的红色节点" << endl;
return false;
}
if (cur->_col == BLACK) ++blackNum;
return Check(cur->_left, blackNum, blackNumRef) && Check(cur->_right, blackNum, blackNumRef);
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
//cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root) {
_root = subL;
subL->_parent = nullptr;
} else {
if (parentParent->_left == parent) {
parentParent->_left = subL;
} else {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
} else {
if (parentParent->_left == parent) {
parentParent->_left = subR;
} else {
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
private:
Node* _root = nullptr;
};
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
#include "RBTree.h"
void TestRBTree1() {
RBTree<int, int> t;
// 常规的测试用例
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试用例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a) {
if (e == 14) {
int x = 0;
}
t.Insert({ e, e });
//t.InOrder();
//cout << "Insert:" << e << "->" << t.IsBalanceTree() << endl;
}
t.InOrder();
cout << t.IsBalance() << endl;
}
// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestRBTree2() {
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++) {
v.push_back(rand() + i);
}
size_t begin2 = clock();
RBTree<int, int> t;
for (auto e : v) {
t.Insert(make_pair(e, e));
}
size_t end2 = clock();
cout << "Insert:" << end2 - begin2 << endl;
cout << t.IsBalance() << endl;
cout << "Height:" << t.Height() << endl;
cout << "Size:" << t.Size() << endl;
size_t begin1 = clock();
// 确定在的值
/*for (auto e : v) { t.Find(e); }*/
// 随机值
for (size_t i = 0; i < N; i++) {
t.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
}
int main() {
TestRBTree2();
return 0;
}
3.2 红黑树的搜索
由于每一棵红黑树都是二叉搜索树，可以使用与搜索普通二叉搜索树时所使用的完全相同的算法进行搜索。在搜索过程中不需使用颜色信息。对普通二叉搜索树进行搜索的时间复杂性为 O(h)，对于红黑树则为 O(log_2 n) 因为在搜索普通二叉搜索树、AVL 树和红黑树时使用了相同的代码，并且在最差情况下 AVL 树的高度最小，因此，在那些以搜索操作为主的应用程序中，最差情况下 AVL 树能获得最优的时间复杂性。
3.3 红⿊树的插⼊
1️⃣插⼊⼀个值按⼆叉搜索树规则进⾏插⼊，插⼊后我们只需要观察是否符合红⿊树的性质。 2️⃣如果是空树插⼊，新增结点是⿊⾊结点。如果是⾮空树插⼊，新增结点必须红⾊结点，因为⾮空树插⼊，新增⿊⾊结点就破坏了性质是很难维护的。 3️⃣⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是⿊⾊的，则没有违反任何性质，插⼊结束。 4️⃣⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是红⾊的，则违反性质。进⼀步分析，c 是红⾊，p 为红，g 必为⿊，这三个颜⾊都固定了，关键的变化看 u 的情况，需要根据 u 分为以下⼏种情况分别处理。
说明：下图中假设我们把新增结点标识为 c (cur)，c 的⽗亲标识为 p (parent)，p 的⽗亲标识为 g (grandfather)，p 的兄弟标识为 u (uncle)。
①情况 1:变⾊ c 为红，p 为红，g 为⿊，u 存在且为红，则将 p 和 u 变⿊，g 变红。在把 g 当做新的 c，继续往上更新。 分析：因为 p 和 u 都是红⾊，g 是⿊⾊，把 p 和 u 变⿊，左边⼦树路径各增加⼀个⿊⾊结点，g 再变红，相当于保持 g 所在⼦树的⿊⾊结点的数量不变，同时解决了 c 和 p 连续红⾊结点的问题，需要继续往上更新是因为，g 是红⾊，如果 g 的⽗亲还是红⾊，那么就还需要继续处理;如果 g 的⽗亲是⿊⾊，则处理结束了;如果 g 就是整棵树的根，再把 g 变回⿊⾊。情况 1 只变⾊，不旋转。所以⽆论 c 是 p 的左还是右，p 是 g 的左还是右，都是上⾯的变⾊处理⽅式。
❶跟 AVL 树类似，图 0 展示了⼀种具体情况，但是实际中需要这样处理的有很多种情况。 ❷图 1 将以上类似的处理进⾏了抽象表达，d/e/f 代表每条路径拥有 hb 个⿊⾊结点的⼦树，a/b 代表每条路径拥有 hb-1 个⿊⾊结点的根为红的⼦树，hb>=0。 ❸图 2/图 3/图 4，分别展示了 hb = 0/hb = 1/hb= 2 的具体情况组合分析，当 hb 等于 2 时，这⾥组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理⽅式⼀样的，变⾊再继续往上处理即可，所以我们只需要看抽象图即可。
②情况 2:单旋 + 变⾊ c 为红，p 为红，g 为⿊，u 不存在或者 u 存在且为⿊，u 不存在，则 c ⼀定是新增结点，u 存在且为⿊，则 c ⼀定不是新增，c 之前是⿊⾊的，是在 c 的⼦树中插⼊，符合情况 1，变⾊将 c 从⿊⾊变成红⾊，更新上来的。 分析：p 必须变⿊，才能解决，连续红⾊结点的问题，u 不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转 + 变⾊。
如果 p 是 g 的左，c 是 p 的左，那么以 g 为旋转点进⾏右单旋，再把 p 变⿊，g 变红即可。p 变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为 p 的⽗亲是⿊⾊还是红⾊或者空都不违反性质。
如果 p 是 g 的右，c 是 p 的右，那么以 g 为旋转点进⾏左单旋，再把 p 变⿊，g 变红即可。p 变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为 p 的⽗亲是⿊⾊还是红⾊或者空都不违反性质。
③情况 3:双旋 + 变⾊ c 为红，p 为红，g 为⿊，u 不存在或者 u 存在且为⿊，u 不存在，则 c ⼀定是新增结点，u 存在且为⿊，则 c ⼀定不是新增，c 之前是⿊⾊的，是在 c 的⼦树中插⼊，符合情况 1，变⾊将 c 从⿊⾊变成红⾊，更新上来的。 分析：p 必须变⿊，才能解决，连续红⾊结点的问题，u 不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转 + 变⾊。
如果 p 是 g 的左，c 是 p 的右，那么先以 p 为旋转点进⾏左单旋，再以 g 为旋转点进⾏右单旋，再把 c 变⿊，g 变红即可。c 变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为 c 的⽗亲是⿊⾊还是红⾊或者空都不违反性质。
如果 p 是 g 的右，c 是 p 的左，那么先以 p 为旋转点进⾏右单旋，再以 g 为旋转点进⾏左单旋，再把 c 变⿊，g 变红即可。c 变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为 c 的⽗亲是⿊⾊还是红⾊或者空都不违反性质。
3.4 红⿊树的插⼊代码实现
// 旋转代码的实现跟 AVL 树是⼀样的，只是不需要更新平衡因⼦
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) {
parent->_right = cur;
} else {
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
// g
// p u
if (parent == grandfather->_left) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
// u 存在且为红 -》变⾊再继续往上处理
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} else {
// u 存在且为⿊或不存在 -》旋转 + 变⾊
if (cur == parent->_left) {
// g
// p u
// c
// 单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// g
// p u
// c
// 双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else {
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔存在且为红，-》变⾊即可
if (uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
} else // 叔叔不存在，或者存在且为⿊
{
// 情况⼆：叔叔不存在或者存在且为⿊
// 旋转 + 变⾊
// g
// u p
// c
if (cur == parent->_right) {
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
3.5 红⿊树的查找
//按⼆叉搜索树逻辑实现即可，搜索效率为 O(logN)
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first < key) {
cur = cur->_right;
} else if (cur->_kv.first > key) {
cur = cur->_left;
} else {
return cur;
}
}
return nullptr;
}
3.6 红⿊树的验证
这⾥获取最⻓路径和最短路径，检查最⻓路径不超过最短路径的 2 倍是不可⾏的，因为就算满⾜这个条 件，红⿊树也可能颜⾊不满⾜性质，当前暂时没出问题，后续继续插⼊还是会出问题的。所以我们还 是去检查性质，满⾜这些性质，⼀定能保证最⻓路径不超过最短路径的 2 倍。 1️⃣枚举颜⾊类型，天然实现保证了颜⾊不是⿊⾊就是红⾊。 2️⃣直接检查根即可。 3️⃣前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲的颜⾊就⽅便多了。 4️⃣前序遍历，遍历过程中⽤形参记录跟到当前结点的 blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可。
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->_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 IsBalance() {
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);
}
3.7 红⿊树的删除
红黑树的删除算法与二叉搜索树的删除算法类似，不同之处在于，在红黑树中执行一次二叉搜索树的删除运算，可能会破坏红黑树的特性，需要重新平衡。 在红黑树中真正删除的结点应是叶结点或只有一个子女的结点。若设被删除为 p，其唯一的子女为 s。结点 p 被删除后，结点 s 取代了它的位置。 如果被删结点 p 是红色的，删去它不存在问题。因为树中各结点的黑高度都没有改变，也不会出现连续两个红色结点，红黑树的特性仍然保持，不需执行重新平衡过程。 如果被删结点 p 是黑色的，一旦删去它，红黑树将不满足性质 3 的要求，因为在这条路径上黑色结点少了一个，从根到外部结点的黑高度将会降低。为此，可以将结点 u 看成具有额外的一重黑色，这样，任意包含结点 u 的路径上的黑高度仍保持删除前的值，就能恢复红黑树的特性。问题是在红黑树的定义中没有包括双重黑色的结点，因此必须通过旋转变换和改变结点的颜色，消除双重黑色结点，恢复红黑树的特性。 设 u 是被删结点 p 的唯一的子女结点。如果 u 是红色结点，可以把结点 u 染成黑色，从而恢复红黑树的特性。如果被删结点 p 是黑色结点，它的唯一的子女结点 u 也是黑色结点，就必须先将结点 p 摘下，将结点 u 链到其祖父结点 g 的下面。假设结点 u 成为结点 g 的右子女，v 是 u 的左兄弟。根据 v 的颜色，分以下两种情况讨论: 情况 1:结点 v 是黑色结点，若设结点 v 的左子女结点为 w。根据 w 的颜色又需分两种情况讨论: (1) 结点 w 是红色结点，此时作一次右单旋转，将 w、g 染成黑色，v 染成红色，如图 7.35 所示，就可消除结点 u 的双重黑色，恢复红黑树的性质。 (2) 结点 w 是黑色结点，还要看结点 w 的右兄弟结点 r。根据结点 r 的颜色，又要分两种情况: ① 结点 r 是红色结点，可通过一次先左后右的双旋转，并将 g 染成黑色，就可消除结点 u 的双重黑色，恢复红黑树的特性，参看图 7.36。 ② 结点 r 是黑色结点，这时还要看结点 g 的颜色。如果 g 是红色结点，只要交换结点 g 和其子女结点 v 的颜色就能恢复红黑树的特性，参看图 7.37(a)。如果 g 是黑色结点，可做一次右单旋转，将结点 v 上升并染成双重黑色，从而消除结点 u 的双重黑色，将双重黑色结点向根的方向转移，如图 7.37(b) 所示。 情况 2:结点 v 是红色结点。考查 v 的右子女结点 r。根据红黑树的性质 2，r 一定是黑色结点。再看结点 r 的左子女结点 s。根据 s 的颜色，可以分为两种情况讨论。 (1) 结点 s 是红色结点。通过一次先左后右双旋转，让 r 上升，使包含 u 的路径的黑高度增 1，从而消除结点 u 的双重黑色，恢复红黑树的特性。参看图 7.38。 (2) 结点 s 是黑色结点，再看结点 s 的右兄弟结点 t。根据结点 t 的颜色又可分为两种情况进行讨论。 ① 若结点 t 为红色结点，先以 t 为旋转轴，做左单旋转，以 t 替补 r 的位置;然后再以 t 为旋转轴，做一次先左后右的双旋转，可消除结点 u 的双重黑色，恢复红黑树的特性，如图 7.39 所示。 ② 若结点 t 为黑色结点，以 v 为旋转轴，做一次右单旋转，并改变 v 和 r 的颜色，即可消除结点 u 的双重黑色，恢复红黑树的特色。参看图 7.40。 当结点 u 是结点 g 的左子女的情况与上面讨论的情况是镜像的，只要左、右指针互换就可以了。
3.8 红黑树模拟实现
#include <iostream>
#include <algorithm>
using namespace std;
// 颜色枚举
enum Color { RED, BLACK };
// 红黑树节点结构
template<typename K, typename V>
struct RBNode {
K key; // 键（用于排序）
V value; // 值
Color color; // 节点颜色
RBNode* parent; // 父节点
RBNode* left; // 左孩子
RBNode* right; // 右孩子
// 构造函数
RBNode(const K& k, const V& v, Color c = RED) :key(k), value(v), color(c), parent(nullptr), left(nullptr), right(nullptr) {}
};
// 红黑树类
template<typename K, typename V>
class RBTree {
private:
using Node = RBNode<K, V>;
Node* root; // 根节点
Node* nil; // 哨兵节点（代替 NULL，简化边界处理）
// 左旋
void left_rotate(Node* x) {
Node* y = x->right; // y 是 x 的右孩子
x->right = y->left; // 将 y 的左子树挂到 x 的右子树
if (y->left != nil) {
y->left->parent = x; // y 左子树的父节点改为 x
}
y->parent = x->parent; // y 的父节点继承 x 的父节点
if (x->parent == nil) { // x 是根节点
root = y;
} else if (x == x->parent->left) { // x 是父节点的左孩子
x->parent->left = y;
} else { // x 是父节点的右孩子
x->parent->right = y;
}
y->left = x; // x 成为 y 的左孩子
x->parent = y; // x 的父节点改为 y
}
// 右旋
void right_rotate(Node* y) {
Node* x = y->left; // x 是 y 的左孩子
y->left = x->right; // 将 x 的右子树挂到 y 的左子树
if (x->right != nil) {
x->right->parent = y; // x 右子树的父节点改为 y
}
x->parent = y->parent; // x 的父节点继承 y 的父节点
if (y->parent == nil) { // y 是根节点
root = x;
} else if (y == y->parent->left) { // y 是父节点的左孩子
y->parent->left = x;
} else { // y 是父节点的右孩子
y->parent->right = x;
}
x->right = y; // y 成为 x 的右孩子
y->parent = x; // y 的父节点改为 x
}
// 插入后修复红黑树性质
void insert_fixup(Node* z) {
// 当父节点是红色时，才需要修复（违反'无连续红节点'）
while (z->parent->color == RED) {
if (z->parent == z->parent->parent->left) { // 父节点是祖父的左孩子
Node* uncle = z->parent->parent->right; // 叔父节点（祖父的右孩子）
// 情况 1：叔父节点是红色 → 仅需变色
if (uncle->color == RED) {
z->parent->color = BLACK; // 父节点变黑
uncle->color = BLACK; // 叔父节点变黑
z->parent->parent->color = RED; // 祖父节点变红
z = z->parent->parent; // 向上继续检查
} else {
// 情况 2：叔父是黑色，且当前节点是父节点的右孩子 → 先左旋转为情况 3
if (z == z->parent->right) {
z = z->parent;
left_rotate(z);
}
// 情况 3：叔父是黑色，且当前节点是父节点的左孩子 → 右旋 + 变色
z->parent->color = BLACK;
z->parent->parent->color = RED;
right_rotate(z->parent->parent);
}
} else { // 父节点是祖父的右孩子（对称逻辑）
Node* uncle = z->parent->parent->left;
if (uncle->color == RED) {
z->parent->color = BLACK;
uncle->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
right_rotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
left_rotate(z->parent->parent);
}
}
}
root->color = BLACK; // 确保根节点始终是黑色
}
// 二叉搜索树插入逻辑（纯 BST 插入）
Node* bst_insert(const K& key, const V& value) {
Node* parent = nil;
Node* curr = root; // 找到插入位置
while (curr != nil) {
parent = curr;
if (key < curr->key) {
curr = curr->left;
} else if (key > curr->key) {
curr = curr->right;
} else { // 键已存在，更新值并返回原节点
curr->value = value;
return curr;
}
}
// 创建新节点（默认红色)
Node* new_node = new Node(key, value, RED);
new_node->parent = parent;
new_node->left = nil;
new_node->right = nil;
// 挂到父节点的对应位置
if (parent == nil) {
root = new_node; // 空树，新节点为根
} else if (key < parent->key) {
parent->left = new_node;
} else {
parent->right = new_node;
}
return new_node;
}
// 中序遍历
void inorder_traversal(Node* node) const {
if (node == nil) return;
inorder_traversal(node->left);
cout << "[" << node->key << ":" << node->value << "," << (node->color == RED ? "红" : "黑") << "] ";
inorder_traversal(node->right);
}
public:
// 构造函数：初始化哨兵节点和根节点
RBTree() {
nil = new Node(K(), V(), BLACK); // 哨兵节点固定为黑色
root = nil;
}
// 析构函数
~RBTree() {
// 此处可补充递归删除所有节点的逻辑，避免内存泄漏
delete nil;
}
// 插入接口
void insert(const K& key, const V& value) {
Node* new_node = bst_insert(key, value);
if (new_node->color == RED) { // 仅新节点是红色时需要修复
insert_fixup(new_node);
}
}
// 中序遍历接口
void inorder() const {
inorder_traversal(root);
cout << endl;
}
// 查找节点
Node* find(const K& key) const {
Node* curr = root;
while (curr != nil) {
if (key < curr->key) {
curr = curr->left;
} else if (key > curr->key) {
curr = curr->right;
} else {
return curr;
}
}
return nullptr; // 未找到
}
};
int main() {
// 1. 创建红黑树
RBTree<int, string> rb_tree;
// 2. 插入测试数据
rb_tree.insert(10, "A");
rb_tree.insert(20, "B");
rb_tree.insert(30, "C");
rb_tree.insert(15, "D");
rb_tree.insert(25, "E");
rb_tree.insert(5, "F");
// 3. 中序遍历（验证有序 + 颜色）
cout << "红黑树中序遍历（键值：颜色）：" << endl;
rb_tree.inorder();
auto node = rb_tree.find(15);
if (node) {
cout << "\n查找键 15：值=" << node->value << "，颜色=" << (node->color == RED ? "红" : "黑") << endl;
}
return 0;
}
4.相关 OJ 题
4.1 二叉搜索树中的插入操作
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
// 若根节点为空，直接返回新节点
if (root == nullptr) {
return new TreeNode(val);
}
TreeNode* cur = root;
while (cur != nullptr) {
if (val < cur->val) { // 左子树为空，直接插入新节点
if (cur->left == nullptr) {
cur->left = new TreeNode(val);
break;
}
// 否则继续遍历左子树
else {
cur = cur->left;
}
} else { // 右子树为空，直接插入新节点
if (cur->right == nullptr) {
cur->right = new TreeNode(val);
break;
}
// 否则继续遍历右子树
else {
cur = cur->right;
}
}
}
return root;
}
};
4.2 将二叉搜索树变平衡
class Solution {
private:
// 中序遍历，将 BST 转换为升序数组
void inorder(TreeNode* root, vector<int>& nums) {
if (root == nullptr) return;
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
}
// 从有序数组的 [start, end] 区间构建平衡 BST
TreeNode* build(const vector<int>& nums, int start, int end) {
if (start > end) return nullptr;
// 选择中间元素作为根，避免栈溢出
int mid = start + (end - start) / 2;
TreeNode* node = new TreeNode(nums[mid]);
// 递归构建左右子树
node->left = build(nums, start, mid - 1);
node->right = build(nums, mid + 1, end);
return node;
}
public:
TreeNode* balanceBST(TreeNode* root) {
vector<int> nums;
inorder(root, nums);
// 步骤 1：中序遍历得到有序数组
return build(nums, 0, nums.size() - 1);
// 步骤 2：重构平衡 BST
}
};
4.3 判断是否为平衡二叉树
class Solution {
private:
// 辅助函数：返回以当前节点为根的子树高度，若子树不平衡则返回 -1
int getHeight(TreeNode* node) {
if (node == nullptr) {
return 0; // 空节点高度为 0
}
// 递归计算左子树高度，若左子树不平衡，直接返回 -1
int leftHeight = getHeight(node->left);
if (leftHeight == -1) {
return -1;
}
// 递归计算右子树高度，若右子树不平衡，直接返回 -1
int rightHeight = getHeight(node->right);
if (rightHeight == -1) {
return -1;
}
// 若当前节点左右子树高度差 > 1，说明不平衡，返回 -1
if (abs(leftHeight - rightHeight) > 1) {
return -1;
}
// 否则返回当前节点的高度（左右子树最大高度 +1）
return max(leftHeight, rightHeight) + 1;
}
public:
bool isBalanced(TreeNode* root) {
// 若辅助函数返回值不为 -1，说明树是平衡的
return getHeight(root) != -1;
}
};
4.4 二叉搜索树迭代器
class BSTIterator {
private:
vector<int> inorderList;
int idx;
// 中序遍历，将节点值存入数组
void inorder(TreeNode* node) {
if (node == nullptr) return;
inorder(node->left);
inorderList.push_back(node->val);
inorder(node->right);
}
public:
BSTIterator(TreeNode* root) {
inorder(root);
idx = 0; // 指针初始化为数组起始位置
}
int next() {
return inorderList[idx++];
}
bool hasNext() {
return idx < inorderList.size();
}
};
4.5 二叉树中的最大路径和
class Solution {
private:
// 辅助函数：返回当前节点能向父节点提供的最大贡献，同时更新全局最大路径和
int helper(TreeNode* node, int& maxSum) {
if (node == nullptr) {
return 0; // 空节点贡献为 0
}
// 计算左右子树的最大贡献，若为负则取 0（剪枝）
int leftContribution = max(helper(node->left, maxSum), 0);
int rightContribution = max(helper(node->right, maxSum), 0);
// 以当前节点为最高点的路径和，更新全局最大值
int currentPathSum = node->val + leftContribution + rightContribution;
maxSum = max(maxSum, currentPathSum);
// 返回当前节点向父节点的最大贡献（只能选左或右子树）
return node->val + max(leftContribution, rightContribution);
}
public:
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN; // 初始化为极小值，应对全负数的情况
helper(root, maxSum);
return maxSum;
}
};