红黑树实现(二)

Algorithms 4th RedBlackBST.java

红黑树介绍及其实现:删除结点实现

查找、获取最小结点

红黑树中查找(get)、获取最小结点(min)等基本读取操作与 BST 中完全一样,因为接下来的删除操作会用到这些函数,这里提一下,不赘述了。

删除结点

维基百科上的红黑树删除实现是先删除找到的结点,再考虑各种情况重新维护红黑树的平衡,这种方法不利于理解,而且容易出现错漏。'Algorithms 4th' 一书中根据红黑树与「2-3 树」一一对应的原理,讨论了「2-3 树」删除结点的情况,再类比到红黑树中实现。

删除最小键

  1. 「2-3 树」中的情况

    最小键位于树最左端的结点,显然在树的底部。从树底部删除「3- 结点」很简单,而删除「2- 结点」时会留下一个空链接,从而破坏树的平衡性。于是为了保证不会删除一个「2- 结点」,需要完成以下两步:

    1. 沿着左链接向下一路变换,以确保当前结点不是「2- 结点」。
    2. 在变换的过程中,会产生一些临时的「4- 结点」,需要在删除后回头一路分解它们。

    变换过程分为以下几种情况:

    1. 左子结点不是「2-结点」,跳过,递归访问左子结点。
    2. 左子结点是「2- 结点」,而右子结点不是「2- 结点」,则从右子结点「借」一个键给左子结点。
    3. 两个子结点均为「2- 结点」,则将这三个结点合并为一个「4- 结点」。
    removeMin case 1 2-3tree
    removeMin case 2 2-3 tree
  2. 红黑树中的情况及实现

    在红黑树中我们要做的,就是利用「旋转」和「颜色反转」模拟「2-3 树」中的变换,保证当前结点不是「2- 结点」。在实现中体现为:在保证了当前结点不是「2- 结点」的基础上,通过变化使下一个访问的结点不是「2- 结点」,再递归访问。

    removeMin red black tree
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    // Assuming that h is red and both h.left and h.left.left
    // are black, make h.left or one of its children red.
    Node* moveRedLeft(Node* h) {
    // case 3: merge 3 2-nodes into a 4-node
    flipColors(h);

    /* case2: node->right is not a 2-node, lend a key from left child to right child.
    * Merge left key of node into key of node->left,
    * merge left key of node->right into keys of node
    * Based on transformation of case 3
    */
    if(isRed(h->right->left)) {
    h->right = rotateRight(h->right);
    h= rotateLeft(h);
    /* Not shown in the code of Algorithms 4th
    * will be done by function 'balance' if not do here
    */
    flipColors(h);
    }
    return h;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void removeMin() {
    if(!isRed(root->left) && !isRed(root->right))
    root->color = RED;
    root = removeMin(root);
    if(!isEmpty()) root->color = BLACK;
    }

    Node* removeMin(Node* node) {
    if(node->left == NULL) {
    // if node->left == NULL, then node->right == NULL is true as well
    delete node;
    return NULL;
    }
    // case 1 not satisfied: node->left is a 2-node
    if(!isRed(node->left) && !isRed(node->left->left))
    node = moveRedLeft(node);
    node->left = removeMin(node->left);
    return balance(node);
    }

    删除结点后,退出调用栈的过程中,一步一步分解之前产生的「4- 结点」。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // restore red-black tree invariant
    Node* balance(Node* h) {
    assert(h!= NULL);

    if(isRed(h->right)) h= rotateLeft(h);
    if(isRed(h->left) && isRed(h->left->left)) h= rotateRight(h);
    if(isRed(h->left) && isRed(h->right)) flipColors(h);

    h->n = size(h->left) + size(h->right) + 1;
    return h;
    }

删除最大键

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void removeMax() {
if(!isRed(root->left) && !isRed(root->right))
root->color = RED;
root = removeMax(root);
if(!isEmpty()) root->color = BLACK;
}

Node* removeMax(Node* node) {
if(isRed(node->left)) node = rotateRight(node);
if(node->right == NULL) {
delete node;
return NULL;
}
if(!isRed(node->right) && !isRed(node->right->left))
node = moveRedRight(node);
node->right = removeMax(node);
return balance(node);
}

删除结点

把以上两种方法融合到 BST 的删除思路中,便得到了红黑树中删除结点的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// combine removeMin and removeMax
void remove(K key) {
if(!contains(key)) return;
if(!isRed(root->left) && !isRed(root->right))
root->color = RED;
root = remove(root, key);
if(!isEmpty()) root->color = BLACK;
}

Node* remove(Node* node, K key) {
if(key < node->key) {
if(!isRed(node->left) && !isRed(node->left->left))
node = moveRedLeft(node);
node->left = remove(node->left, key);
} else {
if(isRed(node->left))
node = rotateRight(node);
if(key == node->key && node->right == NULL) {
delete node;
return NULL;
}
if(!isRed(node->right) && !isRed(node->right->left))
node = moveRedRight(node);
if(key == node->key) {
Node* minNodeFromRight = min(node->right);
node->val = minNodeFromRight->val;
node->key = minNodeFromRight->key;
node->right = removeMin(node->right);
} else {
node->right = remove(node->right, key);
}
}
return balance(node);
}