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

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