Created by potrace 1.14, written by Peter Selinger 2001-2017 Zorch's Blog

红黑树的基本概念与增删改查完整实现(c++)

 
Category： DSA
  • zorchp
  • 2023年 01月21日

写在前面

谈谈红黑树, 参考算法导论和easy-cs/红黑树杀人事件始末.md at main · allentofight/easy-cs (github.com); 文中的很多插图非常便于理解, 这里我就不放图了.

红黑树是维持二叉搜索树平衡的一种经典数据结构, STL中用来实现关联性容器set和map(有序集合, 有序映射), 但是其增删节点步骤较为复杂, 下面来看看.

代码:

dsa/Red_Black_Tree.cpp at main · Apocaly-pse/dsa (github.com);

红黑树的应用

  1. STL中用来实现关联性容器set和map
  2. IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查
  3. ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器
  4. 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块

与AVL树的区别

  1. 对于Treap、Splay Tree，绝大部分情况下，它们操作的效率都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现的概率不大，但是对于单次操作时间非常敏感的场景来说，它们并不适用。

  2. AVL 树是一种高度平衡的二叉树，所以查找的效率非常高。但是为了维持这种高度的平衡，每次插入、删除都要做调整，比较复杂耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。

    反之, 频繁的查找而插入删除操作较少的情况下用 AVL 也是不错的.

  3. 红黑树是近似平衡，并不严格平衡，在维护平衡的成本上，比 AVL 树要低。它的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

红黑树基本性质

红黑树除了具有BST的性质外, 还具有如下性质:

  1. 每个节点都有颜色, 红色或者黑色;
  2. 根节点是黑色的;
  3. 每一个叶结点都是黑色(NIL);
  4. 如果一个节点是红色, 则其子节点必定是黑色;
  5. 任意一个节点到该节点的每一个叶子结点的所有路径上包含相同数量的黑色节点.

性质5反映了红黑树结构的平衡, 因为:

  1. 该性质确保从任意一个节点出发到其叶结点的所有路径中, 最长路径的长度不会超过最短路径的两倍;
  2. 每个节点的左右子树中黑节点的层数是相等的. (说明黑节点完美平衡)

所以, 红黑树是相对接近平衡的二叉搜索树.

预备知识

一些定义

  1. 黑高(black-height): 从某节点x出发(不含该节点), 到达一个叶结点的任意一条简单路径上的黑色节点个数. 记为$bh(x)$.

    根据性质5, 黑高定义是明确的, 因为从该节点出发的所有到其叶节点的简单路径的黑节点个数都相同.

使红黑树平衡的方法

  1. 变色: 红->黑, 黑->红;

  2. 旋转: 左旋, 右旋.

    • 左旋: 以某个节点x作为支点(旋转节点), 其右子节点y变为旋转节点x的父节点, 右子节点y的左子结点β变为旋转节点x的右子节点, 左子结点γ保持不变.
    • 右旋: 以某个结点y作为支点(旋转节点), 其左子结点x变为旋转节点y的父节点, 左子结点x的右子节点β变为旋转节点y的左子结点, 右子节点α保持不变.
          |          Left-Rotate(x)        |
      y         <---------------       x
     / \                              / \
    x   γ       --------------->     α   y
   / \           Right-Rotate(y)        / \
  α   β                                β   γ

    由图可知, 左旋和右旋不改变中序遍历的顺序.

红黑树实现(基本方法篇)

这里与插入删除结点的操作分离开, 因为这两种操作相对复杂, 下面单独说.

节点类

红黑树的每一个结点包含如下的五个属性: (比BST多了一个颜色属性)

  1. color: false/true (red/black);
  2. val: int;
  3. left: RBTreeNode*;
  4. right: RBTreeNode*;
  5. parent: RBTreeNode*;

具体的C++实现:

struct RBTreeNode {
    int val;
    RBTreeNode* left;
    RBTreeNode* right;
    bool color; // true:black, false:red
    RBTreeNode* parent;

    RBTreeNode(int val1, RBTreeNode* l1, RBTreeNode* r1, bool c1)
        : val(val1), left(l1), right(r1), color(c1) {}

    RBTreeNode() : RBTreeNode(0, nullptr, nullptr, true) {}
    RBTreeNode(int x) : RBTreeNode(x, nullptr, nullptr, true) {}
    RBTreeNode(int x, bool c1) : RBTreeNode(x, nullptr, nullptr, c1) {}
    RBTreeNode(int x, RBTreeNode* l1, RBTreeNode* r1)
        : RBTreeNode(x, l1, r1, true) {}
};

这里用委托构造实现了结点类.

红黑树类

class RedBlackTree {
public:
    RedBlackTree() : root(nullptr) {}
    ~RedBlackTree();
    // 遍历部分
    void breadth_travel();                       // bfs
    void print_tree(bool = false, bool = false); // bfs
    void in_order();                             // 顺序输出
    // rotate
    void left_rotate(RBTreeNode*);
    void right_rotate(RBTreeNode*);
    // 以结点x为根的树的最大节点,最小节点
    RBTreeNode* maximum(RBTreeNode*);
    RBTreeNode* minimum(RBTreeNode*);
    // 整个树的最大值最小值
    int MAX();
    int MIN();
    // 前驱节点,后继结点
    RBTreeNode* predecessor(RBTreeNode*);
    RBTreeNode* successor(RBTreeNode*);
    // 树结点的查找, 添加和删除
    RBTreeNode* search(int);
    void insert(int);
    void remove(RBTreeNode*);

private:
    RBTreeNode* root;
    static RBTreeNode* nil; // nil节点, 这里设置为静态, 只分配一次
    void insert_fixup(RBTreeNode*);
    void delete_fixup(RBTreeNode*);
    RBTreeNode* _search(RBTreeNode*, int);
    void transplant(RBTreeNode*, RBTreeNode*);
};
// 这个很重要, static变量类外初始化
RBTreeNode *RedBlackTree::nil = new RBTreeNode();

析构函数

这里与BST区别不大, 主要是注意nil节点的判断以及最后nil节点的内存释放.

RedBlackTree::~RedBlackTree() {
    function<void(RBTreeNode *)> f = [&](RBTreeNode *node) {
        if (!node || node == RedBlackTree::nil) return;
        RBTreeNode *Left_Tree = node->left;
        RBTreeNode *Right_Tree = node->right;
        cout << node->val << " ";
        delete node;
        if (Left_Tree) f(Left_Tree);
        if (Right_Tree) f(Right_Tree);
    };
    f(root);
    delete RedBlackTree::nil;
    cout << "nil deleted..\n";
}

中序遍历

这里和下面的广度遍历一样, 都是不打印nil节点的.

void RedBlackTree::in_order() {
    if (!root) return;
    vector<int> ret;
    stack<RBTreeNode *> st;
    auto cur = root;
    while (!st.empty() || cur) {
        if (cur) {
            st.push(cur);
            cur = cur->left;
        } else {
            cur = st.top();
            st.pop();
            if (cur != RedBlackTree::nil) ret.emplace_back(cur->val);
            cur = cur->right;
        }
    }
    cout << ret;
}

广度遍历

void RedBlackTree::breadth_travel() {
    if (!root || root == RedBlackTree::nil) return;
    queue<RBTreeNode *> que;
    que.push(root);
    vector<int> ret;
    while (!que.empty()) {
        RBTreeNode *cur = que.front();
        que.pop();
        if (cur != RedBlackTree::nil) ret.emplace_back(cur->val);

        if (cur->left) que.push(cur->left);
        if (cur->right) que.push(cur->right);
    }
    cout << ret;
}

打印树

这里改良一下打印函数, 设置了两个默认参数, 分别是:

  • 是否打印颜色(默认不打印)
  • 是否显示nil节点(默认不显示)
void RedBlackTree::print_tree(bool iscolor, bool show_nil) {
    if (!root) return;
    queue<RBTreeNode *> q;
    q.push(root);
    int m = 0;
    while (!q.empty()) {
        int qs = q.size();
        for (auto i = 0; i < qs; i++) {
            auto cur = q.front();
            q.pop();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        m++;
    }
    int n = (1 << m) - 1;
    vector<vector<string>> ans(m, vector<string>(n, " "));
    vector<vector<string>> branch(m, vector<string>(n, " "));
    queue<tuple<int, int, RBTreeNode *, string>> bq;
    bq.push({0, (n - 1) / 2, root, ""s});
    while (!bq.empty()) {
        int bqs = bq.size();
        for (auto i = 0; i < bqs; i++) {
            auto &[r, c, cur, slash] = bq.front();
            bq.pop();
            if (!show_nil && !cur->val) continue; // 表示不打印nil节点
            // 打印值或颜色
            ans[r][c] = to_string(iscolor ? cur->color : cur->val);
            if (r == m - 1) {
                branch[r][c] = slash;
            } else {
                if (slash == "/"s)
                    branch[r][c + 1] = slash;
                else
                    branch[r][c - 1] = slash;
            }
            if (cur->left)
                bq.push({r + 1, c - pow(2, m - r - 2), cur->left, "/"s});
            if (cur->right)
                bq.push({r + 1, c + pow(2, m - r - 2), cur->right, "\\"s});
        }
    }
    for (int i = 0; i < m; i++) {
        for (auto &s : branch[i]) cout << s;
        cout << endl;
        for (auto &s : ans[i]) cout << s;
        cout << endl;
    }
}

最大值最小值

这里需要注意, 不应该用==nullptr, 而应该用==RedBlackTree::nil, 下同.

RBTreeNode *RedBlackTree::maximum(RBTreeNode *x) {
    while (x->right != RedBlackTree::nil) x = x->right;
    return x;
}

RBTreeNode *RedBlackTree::minimum(RBTreeNode *x) {
    while (x->left != RedBlackTree::nil) x = x->left;
    return x;
}

int RedBlackTree::MAX() { return maximum(root)->val; }
int RedBlackTree::MIN() { return minimum(root)->val; }

前驱后继结点

RBTreeNode *RedBlackTree::successor(RBTreeNode *x) {
    // 如果结点x的右子树非空, 则x后继结点就是其右子树的最左节点(minimum)
    if (x->right != RedBlackTree::nil) return minimum(x->right);
    RBTreeNode *y = x->parent;
    // 如果x右子树为空且其后继结点存在, 则其后继就是x的有左孩子的最底层祖先
    while (y != RedBlackTree::nil && x == y->right) x = y, y = y->parent;
    return y;
}

RBTreeNode *RedBlackTree::predecessor(RBTreeNode *x) {
    if (x->left != RedBlackTree::nil) return maximum(x->left);
    RBTreeNode *y = x->parent;
    while (y != RedBlackTree::nil && x == y->left) x = y, y = y->parent;
    return y;
}

查找节点

查找操作由于跟二叉搜索树相同, 这里就一笔带过了.

RBTreeNode *RedBlackTree::_search(RBTreeNode *x, int target) {
    /* if (!x || target == x->val) return x; */
    /* if (target < x->val) */
    /*     return _search(x->left, target); */
    /* else */
    /*     return _search(x->right, target); */
    while (x && target != x->val)
        if (target < x->val)
            x = x->left;
        else
            x = x->right;
    return x;
}

RBTreeNode *RedBlackTree::search(int target) { return _search(root, target); }

左旋右旋

这里要重点说一下, 因为调整红黑树的步骤中就用到了左旋和右旋操作, 对于右旋, 其代码就是左旋代码基础上降left和right互换, 所以这里只讨论左旋. 具体来说, 左旋有3个步骤, 每一个步骤有两个点, 所以分为6个小步骤.

思路

上面已经对旋转做了一个基本介绍, 这里再来看一下对树的旋转到底改变了什么:

      |          Left-Rotate(x)        |
      y         <---------------       x
     / \                              / \
    x   γ       --------------->     α   y
   / \           Right-Rotate(y)        / \
  α   β                                β   γ

这里是对树节点x进行左旋的示意图.

首先, 找到不变的量, 即x的左子树以及y的右子树, 这两部分是一直不变的.

然后是变动的部分:

  1. x的右子树变成y的左子树
  2. y的左子树变成x
  3. y的父节点变成x的父节点

针对变动的部分, 由于树节点之间存在双向的指针(父节点, 子节点), 那么变动的部分其实要修改六个地方. 这也就是上面说的6个小步骤的由来.

步骤

下面来详细说一下具体步骤:

  1. 记录x的右子树(为y), 然后将x的右子树变成y左子树;
  2. 如果y的左子树不为空, 那么y的左子树的父节点变成x;
  3. y的父节点变成x的父节点;
  4. 这里根据x父节点的情况, 做如下讨论:
    • 如果x父节点为nil, 那么令根节点为y;
    • 如果x是其父节点的左孩子, 那么x的父节点的左孩子置为y;
    • 如果x是其父节点的右孩子, 那么x的父节点的右孩子置为y;
  5. y的左子树置为x
  6. x父节点置为y

代码

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

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

插入节点

本质上就是不断把当前节点向上移动, 然后对每种可能的情况进行分析, 完成调整.

基本思路

  1. 找到待插入节点z的待插入位置(肯定是叶节点), 执行插入后将其着为红色.
  2. 确定待插入节点z被插入并着为红色后, 红黑树性质的保持和改变情况.
  3. 逐个讨论插入节点之后红黑树的节点性质的变化与操作. (修正, fixup)

下面就是针对每种情况的分析:

设当前节点为z(待插入节点)

case1: z是根节点,z插入后置为黑

由于一开始将待插入节点置为红, 这时候直接再将其置为黑即可. (代码中表示为最后一行)

case2: z的父节点为黑,z直接插入

插入后不需要操作.

case3: z的父节点为红

这时候要分为下面三种情况来讨论:

case3-1: z的父节点为红,z叔结点为红

分析

  • 当前节点和父节点都是红, 这就违背了红黑树性质4:红节点的子节点都为黑, 所以, 将父节点设置为黑解决了这个问题.

  • 但是父节点变黑会违背性质5:任一节点到叶结点的最短路径都包含相同数量的黑节点, 因为包含父节点的分支的黑节点数量增加了.

    解决这个问题的方法:

    1. 将祖父节点由黑色变成红色
    2. 将叔结点由红色变成黑色

    这样处理之后只有祖父节点不满足红黑树的性质, 所以设其为当前节点继续处理.

问题:

  1. 祖父节点为什么是黑色?

    因为父节点是红色, 根据性质4, 祖父节点必为黑.

  2. 为什么将祖父节点变红, 将叔结点变黑可以解决包含父节点的分支的黑节点数量增加1这个问题

    因为问题包含父节点的分支的黑节点数量增加1同时意味着包含祖父节点的分支的黑节点数量增加了1, 于是将祖父节点变红可以平衡黑节点增加带来的影响.

    但是这样操作之后, 包含叔结点的分支的黑节点总数会减少1, 所以还要改变叔结点的颜色为黑色.

    这样操作之后, 如果祖父节点为根节点, 那么红黑树性质都满足了; 若祖父节点不是根节点, 那么祖父节点可能会不满足性质4了, 这时候将其设置为当前节点, 然后转入其他情况的讨论.

操作

  1. 当前节点的父节点设为黑
  2. 当前节点的叔结点设为黑
  3. 当前节点的祖父节点设为红
  4. 当前节点的祖父节点设为新的当前节点(红)
  5. 继续判断..

case3-2:z的父节点为红,叔结点为黑,且z是其父节点的右孩子

分析

根据插入节点的基本思想, 要不断将当前要处理的节点上移/操作, 直到当前节点成为根节点, 这样就能直接置为黑完成fixup操作了.

那么由于这个情况的当前节点为父节点的右孩子, 此时就可以对父节点左旋, 完成父节点的上移.

为什么要设置当前节点为其父节点呢?

因为左旋之后, 父子节点已经完成了交换, 而针对节点的修正处理需要从下至上处理(由叶至根), 也就是说, 必须先解决孩子问题, 再解决父节点问题, 所以才要设置当前节点为父节点, 这样其实就是处理子节点了.

操作

  1. 将当前节点的父节点作为新的当前节点
  2. 对新的当前节点左旋
  3. 继续判断…

case3-3:z的父节点为红,叔结点为黑,且z是其父节点的左孩子

分析

由于当前节点和其父节点均为红, 这就违背了红黑树性质4, 将父节点变为黑就可以解决此问题, 但是却引起了新的问题, 即违背了性质5:经过父节点的分支的黑节点数量增加了1, 解决这个问题的方法就是将祖父节点变红, 然后对祖父节点右旋.

操作

  1. 父节点置为黑
  2. 祖父节点置为红
  3. 右旋祖父节点
  4. 继续判断..

代码

插入部分

void RedBlackTree::insert(int item) {
    auto y = RedBlackTree::nil, x = root;
    auto z = new RBTreeNode(item);
    while (x && x != RedBlackTree::nil) {
        y = x;
        if (item < x->val)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
    if (RedBlackTree::nil == y)
        root = z;
    else if (item < y->val)
        y->left = z;
    else
        y->right = z;
    // 比BST多了下面几步
    z->left = RedBlackTree::nil;
    z->right = RedBlackTree::nil;
    z->color = false;
    insert_fixup(z);
}

这里与BST的插入节点相比, 主要多了下面几步:

  1. 当前节点的左右子节点均设置为nil;
  2. 当前节点颜色设为red(false);
  3. 修正插入的节点.

修正部分

这部分的代码相当精妙, 参考了算法导论, 直接将上述提到的各种情况都揉在一个函数里面, 实在是妙.

这里其实是6种情况, 针对节点的父节点是祖父节点的左孩子还是右孩子来判断, 完全对称的代码, 这里只讨论当前节点的父节点是其祖父节点的左孩子的情况.

  • 针对case3-1, z的父节点和祖父节点的右孩子(y, 即叔结点)均为红色, 那么将z父节点设为黑色, y设为黑色, 祖父节点设为红色.
  • 对于case3-2, z的父节点为红色, 叔结点为黑色, 且z为其父节点的右孩子, 此时就将当前节点置为其父节点, 然后对当前节点左旋即可.
  • 对于case3-3, 其除了一开始就得到, 还有可能从case3-2经过操作得到, 所以这种情况不是独立的, 而要和case3-2共用(代码中会提到), 具体操作为: 父节点置为黑, 祖父节点置为红, 右旋祖父节点.
void RedBlackTree::insert_fixup(RBTreeNode *z) {
    // 插入节点修正
    // 只要z的父节点是红色就进行操作
    while (!z->parent->color) {
        // z的父节点是其祖父节点的左子结点
        if (z->parent == z->parent->parent->left) {
            // y是z祖父节点的右孩子, 叔结点
            auto y = z->parent->parent->right;
            if (!y->color) {
                // y 红色, case1
                z->parent->color = true;
                y->color = true;
                z->parent->parent->color = false;
                // 更新当前节点z, 变为其祖父节点
                z = z->parent->parent;
                continue;
            } else if (z == z->parent->right) {
                z = z->parent;
                left_rotate(z);
            }
            z->parent->color = true;
            z->parent->parent->color = false;
            right_rotate(z->parent->parent);
        } else {
            auto y = z->parent->parent->left;
            if (!y->color) {
                z->parent->color = true;
                y->color = true;
                z->parent->parent->color = false;
                z = z->parent->parent;
                continue;
            } else if (z == z->parent->left) {
                z = z->parent;
                right_rotate(z);
            }
            z->parent->color = true;
            z->parent->parent->color = false;
            left_rotate(z->parent->parent);
        }
    }
    root->color = true;
}

删除节点

这个操作比插入节点又复杂一点, 要考虑的情况变多了, 还是对照着BST的删除节点的操作进行分析.

基本思路

  1. 将红黑树当成二叉搜索树, 将该节点从二叉搜索树中删除.
    • 若为红色, 不会影响红黑树的5个性质.
    • 若待删除节点为黑色, 需要修正红黑树.
  2. 通过旋转变色等一系列操作fixup红黑树, 使其重新满足红黑树的性质.

至于为什么删除红节点不会影响红黑树的性质, 其原因是:

  1. 树中的黑高没有发生改变
  2. 不存在两个相邻的红节点, 因为y(z的后继结点)在树中占据了z的位置, 再考虑到z的颜色,树中y的新位置不可能有两个相邻的红节点, 另外, 如果y不是z的右孩子, 则y的原右孩子x代替y, 如果y是红色, 则x一定是黑色, 所以用x替代y之后不可能使两个红节点相邻.
  3. 如果y红色, 就不可能是根节点, 所以根节点仍为黑色.

如果结点y是黑色, 就会产生下面的三个问题:(这就需要fixup进行修正)

  1. 如果y是原来的根节点, 则y的一个红色孩子成为新的根节点, 这就违反了性质2(根节点为黑)
  2. 如果x和x父节点都是红色, 就违反了性质4(红节点的子节点必为黑节点)
  3. 在树中移动y将导致先前包含y的任何简单路径上黑节点的个数减少1

由此, y的任何祖先都不满足性质5(黑高性质).

下面的讨论都基于待修正节点(为与后面的代码一致, 设为x, 兄弟节点设为w)为黑色这种情况.

由于前面介绍BST删除节点的时候已经对四种情况(无子树,有左或右子树,有左和右子树)详细分析过了, 这里就主要介绍fixup这个操作的分类讨论与操作.

分析技巧: 双重颜色法

从被删除的节点的后继结点(被删除位置放置的新节点)位置开始调整, 并认为其具有额外一重黑色

这是一种假设的想法, 认为(待修正的)当前节点现在可以容纳两种颜色:

  • 如果它原来是红色, 那么现在就是红+黑
  • 如果原来是黑色, 那么就是黑+黑.

这样假设的好处就是可以让原来红黑树的性质5(黑高性质)保持不变, 反而去调整比较容易调整的性质1,2,4. 基本思想还是尽量向根节点方向移动, 并讨论所有可能出现的情况.

认为当前节点可以容纳两种颜色的想法, 其原理是:

删除当前节点之后, 后继结点会补上原来节点的位置, 既然删除当前节点(黑), 意味着减少了一个黑色节点, 那么再在该位置上增加一重颜色黑色即可.

这样, 当假设当前位置有另外一重黑色的时候, 就正好弥补了删除节点导致的黑节点减少(性质5不满足), 使性质5继续保持.

fixup后的结果为:

  1. 当前节点的子节点指向一个红+黑节点, 此时, 将该结点设为黑, 即可解决问题.
  2. 当前节点指向根节点, 此时设为黑节点即可.
  3. 其他情况. 具体分析如下:

case1: x的兄弟结点w为红色

因为w必须有黑色子节点, 所以可以改变w颜色为黑色, 改变x的父节点的颜色为红色, 然后对x的父节点左旋.

这样处理之后, x的新兄弟节点是旋转之前w的某个子节点, 其颜色为黑色, 于是, 情况1可以转为情况2,3,4.(w为黑色的情况)

case2: x的兄弟节点w为黑色,w的两子节点都为黑色

此时直接将兄弟节点w变为红色以平衡黑高, 并将当前节点上移(从下至上依次修正).

case3: x的兄弟节点w为黑色,w左孩子为红色,右孩子为黑色

交换w和其左子结点的颜色, 此时性质4满足, 然后右旋w, 这样操作之后的新兄弟节点w是一个有红色右孩子的黑色节点. 会直接转入case4.

case4: x兄弟节点w为黑色,右孩子为红色

当前节点的父节点颜色赋给当前节点的兄弟节点, 当前节点父节点设为黑, 当前节点的兄弟节点的右子节点设为黑, 并对x的父节点左旋, 可以去掉x的额外黑色, 使其变成单重黑色,

代码

移植

与BST类似, 定义了一个子函数来处理结点, 提高代码可重用性. 这里与BST的移植函数不同的是

  1. 不是判断nullptr而是nil.
  2. 不需要考虑v是否为空, 即使v指向nil, 也将其父节点指向u父节点.
void RedBlackTree::transplant(RBTreeNode *u, RBTreeNode *v) {
    // 用以v为根的子树替换以u为根的子树
    if (u->parent == RedBlackTree::nil)
        // 处理u是RBT根节点的情况
        root = v;
    else if (u == u->parent->left)
        // u是其父节点的左孩子
        u->parent->left = v;
    else
        // u是其父节点的右孩子
        u->parent->right = v;
    v->parent = u->parent;
}

删除

这里与BST相比, 仅添加了部分记录节点信息的代码:

其中,

  • x记录稍后要进行修正的节点
  • y_origin_color记录当前节点(会发生改变)的颜色(作为判断依据), 删除红节点不需要调整.

当想要删除结点 z, 且此时 z 的子结点少于 2 个时， z从树中删除，并让y成为z。当z有两个子结点时， y应该是z的后继，并且y将移至树中的z 位置。在结点被移除或者在树中移动之前，必须记住 y 的颜色，并且记录结点 x 的踪迹，将 x 移至树中 y的原来位置，因为结点 x也可能引起红黑性质的破坏。删除结点 z之后，对x进行fixup操作.

void RedBlackTree::remove(RBTreeNode *z) {
    RBTreeNode *x{}; // 用于记录执行fixup的节点
    bool y_origin_color = z->color;
    if (z->left == RedBlackTree::nil) { // 没有左子树, 右子树可有可无
        x = z->right;
        transplant(z, z->right);
    } else if (z->right == RedBlackTree::nil) { // 没有右子树, 有左子树
        x = z->left;
        transplant(z, z->left);
    } else { // 左右子树均存在且不为空
        // 查找z的后继
        /*因为z右子树非空, 所以后继一定是该子树的最小节点*/
        auto y = minimum(z->right);
        y_origin_color = y->color;
        x = y->right;
        if (y->parent == z)
            x->parent = y;
        else {
            transplant(y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    delete z;
    z = nullptr;
    // 待删除节点是黑节点才修正红黑树
    if (y_origin_color) delete_fixup(x);
}

修正

这部分才是重头戏, 也是删除操作中的难点. 可以发现有8种小的情况, 而后四种与前面四种存在对称.

void RedBlackTree::delete_fixup(RBTreeNode *x) {
    while (x != root && x->color) {
        if (x == x->parent->left) {
            auto w = x->parent->right; // 兄弟节点
            if (!w->color) {
                w->color = true;
                x->parent->color = false;
                left_rotate(x->parent);
                w = x->parent->right;
            }
            if (w->left->color && w->right->color) {
                w->color = false;
                x = x->parent;
            } else if (w->right->color) {
                w->left->color = true;
                w->color = false;
                right_rotate(w);
                w = x->parent->right;
            }
            w->color = x->parent->color;
            x->parent->color = true;
            w->right->color = true;
            left_rotate(x->parent);
            x = root;
        } else {
            //
            auto w = x->parent->left;
            if (!w->color) {
                w->color = true;
                x->parent->color = false;
                left_rotate(x->parent);
                w = x->parent->left;
            }
            if (w->right->color && w->left->color) {
                w->color = false;
                x = x->parent;
            } else if (w->left->color) {
                w->right->color = true;
                w->color = false;
                left_rotate(w);
                w = x->parent->left;
            }
            w->color = x->parent->color;
            x->parent->color = true;
            w->left->color = true;
            right_rotate(x->parent);
            x = root;
        }
    }
    x->color = true;
}

测试

search search_off backspace