C++ 伸展树与红黑树详解及核心实现

C++ 伸展树与红黑树详解及核心实现

在平衡二叉搜索树（BBST）的家族中，伸展树和红黑树是两种极具代表性的结构。它们各有侧重：伸展树利用局部性原理优化频繁访问的场景，而红黑树则通过颜色约束确保稳定的最坏时间复杂度，是 C++ STL 中 std::map、std::set 等容器的底层基石。

1. 伸展树介绍

伸展树（Splay Tree）是一种自调整的二叉搜索树，由 John Edward Hopcroft 和 Robert Endre Tarjan 于 1985 年提出。与 AVL 树不同，它不追求严格的平衡，而是通过'伸展'操作将最近访问的节点移动到根节点，从而让热点数据更容易被访问。

1.1 旋转策略

每次访问（搜索、插入或删除）一个节点时，都会执行一次'伸展'过程。这通常涉及三种旋转模式：

1. 单旋转 (Zig)：当被访问节点的父节点是根节点时执行。直接将该节点旋转到根位置。
2. 一字形旋转 (Zig-Zig)：当被访问节点与其父节点、祖父节点处于同侧（如左 -左或右 -右）时执行。先围绕父节点旋转，再围绕祖父节点旋转，将节点上移两层。
3. 之字形旋转 (Zig-Zag)：当被访问节点与其父节点、祖父节点形成折线（如左 -右或右 -左）时执行。先围绕父节点旋转，再围绕祖父节点旋转，同样将节点上移两层。

这种机制使得频繁访问的节点始终靠近根部，虽然单次操作可能耗时 O(n)，但在 m >= n 次操作的序列中，均摊时间复杂度为 O(log n)。

1.2 算法逻辑

// 伪代码示意：将节点 s 伸展至根
void splaying(Node* s) {
    while (s->parent != nullptr) {
        Node* p = s->parent;
        if (p->parent == nullptr) {
            // 情况 1: 单旋转
            rotate(p);
        } else {
            Node* g = p->parent;
            // 判断形状决定一字形或之字形
            if ((p->left == s && g->left == p) || (p->right == s && g->right == p)) {
                rotate(g); // 一字形双旋第一步
                rotate(p); // 一字形双旋第二步
            } else {
                rotate(p); // 之字形双旋第一步
                rotate(g); // 之字形双旋第二步
            }
        }
    }
}

2. 红黑树介绍

红黑树是一棵二叉搜索树，每个节点增加了一个存储位表示颜色（红色或黑色）。通过对路径颜色的约束，确保没有一条路径比其他路径长出一倍以上。

2.1 五大性质

1. 每个节点要么是红色，要么是黑色。
2. 根节点必须是黑色。
3. 所有叶子节点（NIL 节点）都是黑色。
4. 如果一个节点是红色，则它的两个子节点必须是黑色（即不能有两个连续的红色节点）。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（黑高度）。

2.2 为什么能保证平衡？

假设最短路径全是黑色节点，长度为 bh。由于不能有连续红色节点，最长路径最多是红黑交替，长度约为 2 * bh。因此，树的高度 h <= 2 * log₂(n+1)，保证了增删查改的最坏时间复杂度均为 O(log n)。

相比 AVL 树，红黑树对平衡的控制较宽松，插入删除时的旋转次数更少，更适合写多读少的场景。

3. 红黑树的实现

3.1 节点结构与基础操作

我们使用模板类来实现泛型支持，并引入哨兵节点（Sentinel Node）来简化边界处理（代替 NULL）。

#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) {
                    // 情况 1: 叔父为红，变色
                    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);
                    }
                    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;
    }

public:
    RBTree() {
        nil = new Node(K(), V(), BLACK);
        root = nil;
    }

    ~RBTree() {
        delete nil;
    }

    void 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 return; // 键已存在
        }

        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;

        if (new_node->color == RED) insert_fixup(new_node);
    }

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

    void inorder() const {
        inorder_traversal(root);
        cout << endl;
    }

private:
    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);
    }
};

3.2 删除操作简述

删除比插入复杂。若删除的是红色节点，不影响黑高度，无需修复。若删除的是黑色节点，会导致路径黑高度减少，需要引入'双重黑色'概念并通过旋转和变色消除。主要分四种情况讨论兄弟节点的颜色及其子节点状态，最终恢复红黑树性质。

4. 相关 OJ 题实战

掌握理论后，建议通过以下题目巩固理解：

4.1 二叉搜索树中的插入操作

这是最基础的 BST 插入，红黑树在此基础上增加了颜色维护。

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

4.2 将二叉搜索树变平衡

利用中序遍历得到有序数组，再递归构建平衡树。

class Solution {
private:
    void inorder(TreeNode* root, vector<int>& nums) {
        if (!root) 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 判断是否为平衡二叉树

检查左右子树高度差是否超过 1。

class Solution {
private:
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 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) 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 二叉树中的最大路径和

DFS 回溯，计算以当前节点为最高点的路径和。

class Solution {
private:
    int helper(TreeNode* node, int& maxSum) {
        if (!node) 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;
    }
};

以上涵盖了从理论推导到代码落地的完整流程。实际工程中，除非有特殊需求，建议优先使用 STL 提供的 std::map 或 std::set，但深入理解其底层实现对于面试和性能调优至关重要。