C++ 伸展树与红黑树是二叉搜索树的改进版本。伸展树利用局部性原理，通过旋转将频繁访问节点移至根部，适合缓存场景。红黑树通过颜色约束确保路径长度不超过两倍，保证最坏情况下的对数时间复杂度，常用于 STL 容器。本文详细阐述两者概念、性质及操作逻辑，提供完整的 C++ 代码实现，包括插入、查找、删除、验证及旋转算法，并辅以典型 OJ 题目解析。
伸展树是一种自调整二叉搜索树，由 John Edward Hopcroft 和 Robert Endre Tarjan 于 1985 年发明。与 AVL 树不同，伸展树不追求严格的平衡，而是通过'伸展'操作将最近访问的节点移至根节点，利用局部性原理优化频繁访问的场景。
每次访问（搜索、插入或删除）一个结点时，执行'展开'过程，包含三种旋转：
void splaying(Node* g, Node* p, Node* s) {
// g 是 p 的父结点，p 是 s 的父结点。算法将 s 移到根结点位置
while (s != root) {
if (p == root) {
rotateSingle(s); // 单旋转
} else if (isSameDirection(p, g)) {
rotateZigzag(s); // 一字形双旋转
} else {
rotateZigZag(s); // 之字形双旋转
}
}
}
对于 n 个结点的树执行 m 次操作，总时间复杂度为 O(m log n)，均摊时间复杂度为 O(log n)。适合缓存、热点数据查询等场景。
红黑树是一棵二叉搜索树，每个结点增加颜色属性（红色或黑色）。通过对路径上结点颜色的约束，确保没有一条路径比其他路径长出两倍，从而实现近似平衡。
最短路径为全黑路径（长度 bh），最长路径为一黑一红间隔（长度 2bh）。因此任意路径长度满足 bh <= h <= 2bh。
红黑树高度最大为 2 log₂(n+1)，增删查改最坏时间复杂度为 O(log n)。相比 AVL 树，红黑树在插入时旋转次数更少，维护成本更低，常用于 C++ STL 容器。
enum Color { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
pair<K, V> _kv;
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};
与普通二叉搜索树相同，无需使用颜色信息，时间复杂度 O(log n)。
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) {
RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;
} else {
RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;
}
break;
}
} else {
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;
cur = grandfather; parent = cur->_parent;
} else {
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;
}
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;
}
检查根是否为黑、无连续红结点、每条路径黑结点数量相等。
删除黑色结点可能破坏黑高度平衡，需引入双重黑色结点并通过旋转和变色消除。具体逻辑较复杂，涉及兄弟结点颜色判断及多种旋转组合。
完整类实现包含左旋、右旋、插入修复、中序遍历等功能，确保红黑树性质维持。
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
TreeNode* cur = root;
while (cur) {
if (val < cur->val) {
if (!cur->left) { cur->left = new TreeNode(val); break; }
cur = cur->left;
} else {
if (!cur->right) { cur->right = new TreeNode(val); break; }
cur = cur->right;
}
}
return root;
}
};
通过中序遍历转为有序数组，再递归构建平衡树。
递归计算高度，若子树不平衡返回 -1。
使用中序遍历结果数组模拟迭代器行为。
DFS 回溯，计算当前节点作为最高点的路径和，更新全局最大值。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online