C++ 伸展树与红黑树原理及实现

C++ 伸展树与红黑树原理及实现

1. 伸展树介绍

伸展树（Splay Tree）是一种自调整的二叉搜索树，由 John Edward Hopcroft 和 Robert Endre Tarjan 于 1985 年提出。与 AVL 树不同，伸展树不追求严格的平衡，而是利用'局部性原理'，将最近访问的节点通过旋转操作移至根节点。

这种策略使得频繁访问的数据始终靠近根部，从而在均摊意义上达到 O(log n) 的时间复杂度。虽然单次操作可能耗时 O(n)，但在 m >= n 次操作的序列中，总时间复杂度为 O(m log n)。伸展树非常适合缓存、热点数据查询等场景。

1.1 伸展操作

每当访问（搜索、插入或删除）一个节点 s 时，执行一次'伸展'过程，将其移至根节点。如果删除节点 s，则将其父节点伸展至根。伸展操作包含三种旋转类型：

1. 单旋转：当被访问节点的父节点是根节点时执行。保持二叉搜索树特性，s 成为新根。
2. 一字形旋转（Zig-Zig）：当 s 与其父节点 p、祖父节点 g 同构（如左 -左或右 -右）时执行。先围绕 p 旋转 g，再围绕 s 旋转 p。
3. 之字形旋转（Zig-Zag）：当 s 与 p、g 异构（如左 -右或右 -左）时执行。先围绕 s 旋转 p，再围绕 s 旋转 g。

之字形旋转有助于减少树的高度，而一字形旋转主要提升访问节点的位置。

// 伪代码逻辑示意
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)) {
                // 情况 2: 一字形双旋转
                rotate(g); rotate(p);
            } else {
                // 情况 3: 之字形双旋转
                rotate(s); rotate(g);
            }
        }
    }
}

2. 红黑树介绍

2.1 红黑树的概念

红黑树是一棵二叉搜索树，每个节点增加一个颜色位（红色或黑色）。通过对路径上节点颜色的约束，确保没有一条路径比其他路径长出一倍以上，从而实现近似平衡。

2.2 红黑树的性质

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

基于这些性质，可以推导出红黑树的高度 h 满足：h ≤ 2 log₂(n + 1)。这意味着增删查改的最坏时间复杂度稳定在 O(log n)。

2.3 为什么最长路径不超过最短路径的 2 倍？

• 最短路径：全为黑色节点，长度为黑高度 bh。
• 最长路径：红黑相间，长度为 2 * bh。
• 由于不存在连续红节点，任何路径长度都在 [bh, 2*bh] 之间。

2.4 红黑树的效率

相比 AVL 树，红黑树对平衡的控制较宽松，插入时的旋转次数更少，更适合写多读少的场景。AVL 树在纯搜索场景下略优，但两者整体效率处于同一档次。

3. 红黑树的实现

3.1 红黑树的结构

我们需要定义节点结构，包含键值对、左右子指针、父指针以及颜色属性。

#pragma once
#include <utility>

enum Color { RED, BLACK };

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

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

3.2 红黑树的搜索

搜索逻辑与普通二叉搜索树完全一致，无需关心颜色信息。

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.3 红黑树的插入

插入分为两步：按 BST 规则找到位置并插入，然后修复红黑树性质。

1. 空树：新节点设为黑色作为根。
2. 非空树：新节点设为红色。若父节点为黑色，无需调整；若父节点为红色，则违反性质，需根据叔叔节点颜色进行调整。

调整策略：

• 变色：叔叔节点存在且为红色 -> 父、叔变黑，祖父变红 -> 继续向上处理。
• 旋转：叔叔节点不存在或为黑色 -> 根据相对位置进行单旋或双旋，并配合变色。

3.4 红黑树的插入代码实现

以下是核心的插入与修复逻辑，包含了旋转函数和颜色调整。

// 右旋
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;
    }
}

bool Insert(const std::pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new RBTreeNode<K, V>(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 RBTreeNode<K, V>(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) {
                // 情况 1: 变色
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // 情况 2/3: 旋转 + 变色
                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;
}

3.5 红黑树的验证

验证需要检查三条性质：根为黑、无连续红、黑高度一致。

bool Check(Node* cur, int blackNum, const int blackNumRef) {
    if (cur == nullptr) {
        if (blackNum != blackNumRef) {
            return false;
        }
        return true;
    }
    if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED) {
        return false;
    }
    if (cur->_col == BLACK) ++blackNum;
    return Check(cur->_left, blackNum, blackNumRef) && 
           Check(cur->_right, blackNum, blackNumRef);
}

bool IsBalance() {
    if (_root == nullptr) return true;
    if (_root->_col == RED) return false;
    
    int refNum = 0;
    Node* leftMost = _root;
    while (leftMost) {
        if (leftMost->_col == BLACK) ++refNum;
        leftMost = leftMost->_left;
    }
    return Check(_root, 0, refNum);
}

3.6 红黑树的删除

删除逻辑较为复杂，涉及双重黑色的处理。若删除的是红色节点，直接移除即可；若删除的是黑色节点，会导致黑高度减少，需引入'额外黑色'概念并通过旋转和变色消除。

具体包括：

• 兄弟节点为红色：交换颜色并旋转。
• 兄弟节点为黑色：根据侄子节点颜色进行变色或旋转，将双重黑色向上传递或消除。

(注：删除实现篇幅较长，核心思路与插入类似，重点在于维护黑高度平衡)

4. 相关算法题实战

为了巩固理解，可以参考以下经典题目进行练习：

1. 二叉搜索树中的插入操作：考察基本的 BST 插入逻辑。
2. 将二叉搜索树变平衡：考察如何构建平衡树，通常使用中序遍历转数组再递归构建。
3. 判断是否为平衡二叉树：考察树的高度计算与平衡因子判断。
4. 二叉搜索树迭代器：考察中序遍历的非递归实现。
5. 二叉树中的最大路径和：考察树形 DP 与递归回溯。

这些题目涵盖了从基础插入到复杂平衡调整的各个层面，建议结合手写代码加深理解。