C++伸展树介绍以及红黑树的实现

伸展树的插入操作与二叉搜索树相同，但结点一经插入之后立即展开到根结点。同样，从伸展树中删除一个结点的操作也与二叉搜索树相同，但需要把被删结点的父结点展开到根结点。伸展树与 AVL 树在操作上稍有不同。伸展树的调整与结点被访问（包括搜索、插入、删除）的频率有关，能够进行更合理的调整。而 AVL 树的结构调整只与插入、删除的顺序有关，与访问的频率无关。

2. 红黑树介绍

2.1 红黑树的概念

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

红黑树是这样的一棵二叉搜索树：树中的每一个结点的颜色不是黑色就是红色。可以把一棵红黑树视为一棵扩充二叉树，用外部结点表示空指针。

2.2 红黑树的性质

1. 根结点和所有外部结点的颜色是黑色。
2. 从根结点到外部结点的途中没有连续两个结点的颜色是红色。
3. 所有从根到外部结点的路径上都有相同数目的黑色结点。

从红黑树中任一结点 x 出发（不包括结点 x），到达一个外部结点的任一路径上的黑结点个数叫做结点 x 的黑高度，亦称为结点的阶记作 bh(x)。红黑树的黑高度定义为其根结点的黑高度。

另一种等价的定义是看结点指针的颜色。从父结点到黑色子女结点的指针为黑色的，从父结点到红色子女结点的指针为红色的。

1. 从内部结点指向外部结点的指针是黑色的。
2. 从根结点到外部结点的途中没有两个连续的红色指针。
3. 所有根到外部结点的路径上都有相同数目的黑色指针。

结论 1：设从根到外部结点的路径长度 (Path Length, PL) 为该路径上指针的个数，如果 P 与 Q 是红黑树中的两条从根到外部结点的路径，则有：PL(P) <= 2 * PL(Q)。

结论 2：设 h 是一棵红黑树的高度（不包括外部结点），n 是树中内部结点的个数，r 是根结点的黑高度，则以下关系式成立： (1) h <= 2r (2) n >= 2^r - 1 (3) h <= 2 * log2(n + 1)

由于红黑树的高度最大为 2 * log2(n + 1)，所以，搜索、插入、删除操作的时间复杂性为 O(log n)。注意，最差情况下的红黑树的高度大于最差情况下具有相同结点个数数的 AVL 树的高度，近似于 1.44 * log2(n + 2)。

红黑树继承了二叉搜索树的定义，一些数据成员和成员函数可以直接使用二叉搜索树的成员。

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

2.3 红黑树如何确保最长路径不超过最短路径的 2 倍的？

1. 从根到 NULL 结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就是全是黑色结点的路径，假设最短路径长度为 bh (black height)。
2. 由性质 2 和性质 3 可知，任意一条路径不会有连续的红⾊结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为 2*bh。
3. 综合红黑树的性质而言，理论上的全黑最短路径和一黑一红的长路径并不是在每棵红黑树都存在的。假设任意一条从根到 NULL 结点路径的长度为 x，那么 bh <= h <= 2*bh。

2.4 红黑树的效率

假设 N 是红黑树树中结点数量，h 最短路径的长度，那么，由此推出，也就是意味着红黑树增删查改最坏也就是走最长路径，那么 2h - 1 <= N < 2^(2*h) - 1。由此推出 h ≈ logN，也就是意味着红黑树增删查改最坏也就是走最长路径，那么时间复杂度还是 O(log N)。

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

3. 红黑树的实现

3.1 红黑树的结构

// RBTree.h
#pragma once
#include <utility>

enum Colour { RED, BLACK };

template<class K, class V>
struct RBTreeNode {
    std::pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;

    RBTreeNode(const std::pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};

template<class K, class V>
class RBTree {
    typedef RBTreeNode<K, V> Node;
public:
    bool Insert(const std::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; // Key exists
            }
        }

        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;
    }

    void InOrder() {
        _InOrder(_root);
        std::cout << std::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) {
                std::cout << "黑色节点的数量不相等" << std::endl;
                return false;
            }
            return true;
        }
        if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED) {
            std::cout << cur->_kv.first << "->" << "连续的红色节点" << std::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);
        std::cout << root->_kv.first << " ";
        _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>
#include <ctime>
using namespace std;
#include "RBTree.h"

void TestRBTree1() {
    RBTree<int, int> t;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) {
        t.Insert({ e, e });
    }
    t.InOrder();
    cout << t.IsBalance() << endl;
}

int main() {
    TestRBTree1();
    return 0;
}

3.2 红黑树的搜索

由于每一棵红黑树都是二叉搜索树，可以使用与搜索普通二叉搜索树时所使用的完全相同的算法进行搜索。在搜索过程中不需使用颜色信息。对普通二叉搜索树进行搜索的时间复杂性为 O(h)，对于红黑树则为 O(log n)。

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，继续往上更新。

• 情况 2：单旋 + 变色 c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑。需要旋转 + 变色。 如果 p 是 g 的左，c 是 p 的左，那么以 g 为旋转点进行右单旋，再把 p 变黑，g 变红即可。 如果 p 是 g 的右，c 是 p 的右，那么以 g 为旋转点进行左单旋，再把 p 变黑，g 变红即可。

• 情况 3：双旋 + 变色 c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑。 如果 p 是 g 的左，c 是 p 的右，那么先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，再把 c 变黑，g 变红即可。 如果 p 是 g 的右，c 是 p 的左，那么先以 p 为旋转点进行右单旋，再以 g 为旋转点进行左单旋，再把 c 变黑，g 变红即可。

3.4 红黑树的插入代码实现

bool Insert(const std::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 (parent == grandfather->_left) {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) {
                parent->_col = 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 = 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;
}

3.5 红黑树的查找

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) {
        if (refNum != blackNum) {
            std::cout << "存在黑色结点的数量不相等的路径" << std::endl;
            return false;
        }
        return true;
    }
    if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
        std::cout << root->_kv.first << "存在连续的红⾊结点" << std::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 染成红色，如图所示，就可消除结点 u 的双重黑色，恢复红黑树的性质。
  2. 结点 w 是黑色结点，还要看结点 w 的右兄弟结点 r。根据结点 r 的颜色，又要分两种情况：
     • 结点 r 是红色结点，可通过一次先左后右的双旋转，并将 g 染成黑色，就可消除结点 u 的双重黑色，恢复红黑树的特性。
     • 结点 r 是黑色结点，这时还要看结点 g 的颜色。如果 g 是红色结点，只要交换结点 g 和其子女结点 v 的颜色就能恢复红黑树的特性。如果 g 是黑色结点，可做一次右单旋转，将结点 v 上升并染成双重黑色，从而消除结点 u 的双重黑色，将双重黑色结点向根的方向转移。

• 情况 2：结点 v 是红色结点 考查 v 的右子女结点 r。根据红黑树的性质 2，r 一定是黑色结点。再看结点 r 的左子女结点 s。根据 s 的颜色，可以分为两种情况讨论。

  1. 结点 s 是红色结点。通过一次先左后右双旋转，让 r 上升，使包含 u 的路径的黑高度增 1，从而消除结点 u 的双重黑色，恢复红黑树的特性。
  2. 结点 s 是黑色结点，再看结点 s 的右兄弟结点 t。根据结点 t 的颜色又可分为两种情况进行讨论。
     • 若结点 t 为红色结点，先以 t 为旋转轴，做左单旋转，以 t 替补 r 的位置；然后再以 t 为旋转轴，做一次先左后右的双旋转，可消除结点 u 的双重黑色，恢复红黑树的特性。
     • 若结点 t 为黑色结点，以 v 为旋转轴，做一次右单旋转，并改变 v 和 r 的颜色，即可消除结点 u 的双重黑色，恢复红黑树的特色。

当结点 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;

    void left_rotate(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        if (y->left != nil) y->left->parent = x;
        y->parent = x->parent;
        if (x->parent == nil) root = y;
        else if (x == x->parent->left) x->parent->left = y;
        else x->parent->right = y;
        y->left = x;
        x->parent = y;
    }

    void right_rotate(Node* y) {
        Node* x = y->left;
        y->left = x->right;
        if (x->right != nil) x->right->parent = y;
        x->parent = y->parent;
        if (y->parent == nil) root = x;
        else if (y == y->parent->left) y->parent->left = x;
        else y->parent->right = x;
        x->right = y;
        y->parent = x;
    }

    void insert_fixup(Node* z) {
        while (z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                Node* uncle = z->parent->parent->right;
                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->right) {
                        z = z->parent;
                        left_rotate(z);
                    }
                    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;
    }

    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() {
    RBTree<int, string> rb_tree;
    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");

    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:
    void inorder(TreeNode* root, vector<int>& nums) {
        if (root == nullptr) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }

    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);
        return build(nums, 0, nums.size() - 1);
    }
};

4.3 判断是否为平衡二叉树

class Solution {
private:
    int getHeight(TreeNode* node) {
        if (node == nullptr) return 0;
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        if (abs(leftHeight - rightHeight) > 1) return -1;
        return max(leftHeight, rightHeight) + 1;
    }

public:
    bool isBalanced(TreeNode* root) {
        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;
        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;
    }
};