红黑树实现(二)

Algorithms 4th RedBlackBST.java

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

查找、获取最小结点

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

删除结点

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

删除最小键

「2-3 树」中的情况

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

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

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

  1. 左子结点不是「2-结点」,跳过,递归访问左子结点。
  2. 左子结点是「2- 结点」,而右子结点不是「2- 结点」,则从右子结点「借」一个键给左子结点。
  3. 两个子结点均为「2- 结点」,则将这三个结点合并为一个「4- 结点」。

red-black-tree-removemin-23tree-case-1.png

Figure 1: removeMin case 1 2-3tree

red-black-tree-removemin-23tree-case-2.png

Figure 2: removeMin case 2 2-3 tree

红黑树中的情况及实现

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

red-black-tree-removemin-rbtree.png

Figure 3: removeMin red black tree

// 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;
}
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- 结点」。

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

删除最大键

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 的删除思路中,便得到了红黑树中删除结点的实现:

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