C++伸展树介绍与红黑树实现

C++伸展树介绍与红黑树实现

1. 伸展树介绍

一种与 AVL 树类似的改进的二叉搜索树，称为 伸展树。是由 John Edward Hopcroft 和 Robert Endre Tarjan 于 1985 年共同发明的。与 AVL 树以及在并查集时的父指针表示的树的路径压缩一样，同属于自调整数据结构。

在讨论 AVL 树时，主要关注点在于保持树的高度平衡。然而，对于二叉搜索树来说，它主要用于内存中目录的编制，因此，快速插入、搜索、删除元素才是我们关心的问题，而不是树的形状。通过平衡树可以提高效率，但这不是唯一的方法。

伸展树就是另一种提高搜索效率的方法。它参照了以下两种想法：

1. 单一旋转：其目的是将经常访问的结点最终上移到靠近根的地方，使得以后的访问比以前更快。
2. 移动到根部：假设正在访问的结点将以很高的概率再次被访问，因此，对它反复进行子女—父结点旋转，直到被访问的结点位于根部为止。

每当访问 (包括搜索、插入或删除) 一个结点 s 时，伸展树就执行一次叫做'展开'的过程。'展开'将结点 s 移到二叉搜索树的根部。当删除结点 s 时，'展开'把结点 s 的父结点上移到根结点。就像 AVL 树，一次'展开'由一组旋转组成。旋转有三种类型：单旋转、一字形旋转和之字形旋转。

• 情况 1: 被访问结点 s 的父结点是根结点。此时执行单旋转，在保持二叉搜索树特性的情况下，结点 s 成为新的根。
• 情况 2: 同构的形状。结点 s 是其父结点 p 的左子女，结点 p 又是其父结点 g 的左子女；或者均为右子女。此时执行一字形旋转（双旋转）。
• 情况 3: 异构的形状。结点 s 是其父结点 p 的左子女，结点 p 又是其父结点 g 的右子女；或者反之。此时执行之字形旋转（双旋转）。

被访问结点 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₂n) 时间，从而使每次访问操作所花费的平均时间达到 O(log₂n)。

伸展树的插入操作与二叉搜索树相同，但结点一经插入之后立即展开到根结点。同样，从伸展树中删除一个结点的操作也与二叉搜索树相同，但需要把被删结点的父结点展开到根结点。

2. 红⿊树介绍

2.1 红⿊树的概念

红⿊树是⼀棵⼆叉搜索树，它的每个结点增加⼀个存储位来表示结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出 2 倍，因⽽是接近平衡的。

2.2 红⿊树的性质

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

结论 1: 设从根到外部结点的路径长度为 PL(P)，如果 P 与 Q 是红黑树中的两条从根到外部结点的路径，则有：PL(P) ⩽ 2PL(Q)。

结论 2: 设 h 是一棵红黑树的高度，n 是树中内部结点的个数，r 是根结点的黑高度，则以下关系式成立： (1) h ⩽ 2r (2) n ⩾ 2ʳ - 1 (3) h ⩽ 2log₂(n + 1)

由于红黑树的高度最大为 2log₂(n + 1)，所以，搜索、插入、删除操作的时间复杂性为 O(log₂n)。

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

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

2.4 红⿊树的效率

假设 N 是红⿊树树中结点数量，h 最短路径的⻓度，由此推出红⿊树增删查改最坏也就是⾛最⻓路径，那么 2h − 1 <= N < 2²∗h − 1。由此推出 h ≈ logN，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径，那么时间复杂度还是 O(logN)。

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

3. 红⿊树的实现

3.1 红⿊树的结构

// RBTree.h
#pragma once
enum Colour { RED, BLACK };

template<class K, class V>
struct RBTreeNode {
    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);
    void InOrder();
    bool IsBalance();
    int Height();
    int Size();
    Node* Find(const K& key);
private:
    // ... 辅助函数省略 ...
    Node* _root = nullptr;
};

3.2 红黑树的搜索

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

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 红⿊树的插⼊

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 存在且为黑。需要旋转 + 变色。
• 情况 3: 双旋 + 变色 c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑。需要旋转 + 变色。

3.4 红⿊树的插⼊代码实现

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 = 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(黑色结点数量)，走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值，依次比较即可。

bool Check(Node* root, int blackNum, const int refNum) {
    if(root == nullptr) {
        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 是红色的，删去它不存在问题。如果被删结点 p 是黑色的，一旦删去它，红黑树将不满足性质 3 的要求。为此，可以将结点 u 看成具有额外的一重黑色，这样，任意包含结点 u 的路径上的黑高度仍保持删除前的值，就能恢复红黑树的特性。

根据 v 的颜色（v 是 u 的左兄弟），分以下两种情况讨论：

• 情况 1: 结点 v 是黑色结点。若设结点 v 的左子女结点为 w。根据 w 的颜色又需分两种情况讨论。
  • (1) 结点 w 是红色结点，此时作一次右单旋转，将 w、g 染成黑色，v 染成红色。
  • (2) 结点 w 是黑色结点，还要看结点 w 的右兄弟结点 r。根据结点 r 的颜色，又要分两种情况。
• 情况 2: 结点 v 是红色结点。考查 v 的右子女结点 r。根据红黑树的性质 2，r 一定是黑色结点。再看结点 r 的左子女结点 s。根据 s 的颜色，可以分为两种情况讨论。

当结点 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 二叉搜索树中的插入操作

LeetCode 链接

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 将二叉搜索树变平衡

LeetCode 链接

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 判断是否为平衡二叉树

LeetCode 链接

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 二叉搜索树迭代器

LeetCode 链接

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 二叉树中的最大路径和

LeetCode 链接

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