红黑树插入与删除算法的原理及实现

红黑树

在最坏状况下二叉查找树的性能非常蹩脚，咱们迫切需要一种可能所有操作都能在对数工夫内实现的数据结构。接下来咱们就来介绍一下一种十分罕用的动静保护的均衡二叉树——红黑树。

在引入红黑树之前，咱们须要理解一下 2 - 3 查找树。

2- 3 查找树

2- 3 查找树的介绍

上图是一个简略的 2 - 3 查找树。能够看出，比起一般的二叉查找树，2- 3 查找树多了一个 3 - 节点。3- 节点的性质也是相似于 2 - 节点的。因而，2- 3 查找树的查找算法与一般二叉查找树的查找算法也是相似的（只是要对 3 - 节点探讨）。

那么，2- 3 树的插入算法又要怎么实现呢？何时插入 2 - 节点，又要何时插入 3 - 节点呢？

发明者给出了答案：

2- 3 查找树的插入算法

依据插入元素的大小，查找到插入的地位：

• 如果插入的地位是一个 2 - 节点，那么就与该节点节点造成 3 - 节点，如下图：

• 如果插入的地位是一个 3 - 节点，那么就与该节点造成一个 4 - 节点，再从 4 - 节点 成长 出一个新的 2 - 节点

这个过程咱们能够看出 2 - 3 查找树的成长过程：

1. 向树的底部找到地位插入元素，如果插入的地位是 2 - 节点。2- 节点会与插入元素一起成长为 3 - 节点。如果是 3 - 节点，那么 3 - 节点会与插入元素造成 4 - 节点。
2. 4- 节点会向上成长，即两头的元素会与父节点联合。如果父节点是 2 - 节点，就会造成 3 - 节点。如果父节点是 3 - 节点，那么就会造成 4 - 节点持续成长。

2- 3 查找树的性质

• 部分变换：这是与 AVL 二叉均衡树最大的区别，2- 3 查找树只须要在部分实现 2 -3- 4 节点的变换即可。
• 全局有序，完满均衡：部分变换不会扭转 2 - 3 树的有序性与平衡性。这是因为在插入的过程保障有序。惟一一个扭转树高度的操作——4- 节点的向上成长，也是左右子树同时高度 +1。

在一个大小为 N 的 2 - 3 树中，查找和插入操作的拜访的节点必然不超过 lgN 个。

一颗含有 N 个节点的 2 - 3 树的高度在 $[lgN,log_3N]$ 之间。

红黑二叉查找树

前言：替换 3 - 节点

红黑二叉查找树的根本思维就是 用规范的二叉查找树（齐全由 2 - 节点形成）和一些额定的信息（替换 3 - 节点）来示意 2 - 3 树。由此咱们将树中的链接分为两个品种：红链接将两个 2 - 节点连接起来形成一个 3 - 节点，黑链接则是 2 - 3 树中的一般链接。简略来说：咱们将原来的 3 - 节点示意为一条左斜的红色链接。

基于 2 - 3 树的性质以及红黑树的根本思维，咱们能够给出红黑树的 定义：

• 红链接均为左链接；
• 没有任何一个节点同时和两条红链接相连，即不存在 4 - 节点；
• 该树是 完满彩色均衡 的，即任意 空链接 （即指向 null 的节点指针）到根节点的门路上的 黑链接数量雷同。

满足这些定义的红黑树和相应 2 - 3 树是一一对应的。如下图：

如上图：任意空链接到根节点的黑链接都是雷同的——2 条。

咱们在 Node 类（节点）中增加 color 属性，代表与父节点指向它的链接的色彩：

private static final boolean RED = true;
private static final boolean BLACK = false;
 
private Node root;
 
private class Node{
    Key key;            // 键
    Value val;          // 相关联的值
    Node left, right;   // 左右子树
    int N;              // 子树中的节点总数
    boolean color;      // 由其父节点指向它的链接的色彩
 
    public Node(Key key, Value val, int n, boolean color) {
        this.key = key;
        this.val = val;
        this.N = n;
        this.color = color;
    }
}
 
/**
 * 判断是否是 3 - 节点
 */
private boolean isRed(Node x){if (x == null) {return false;}
    return x.color == RED;
}

插入操作

因为红黑树是二叉树构造的 2 - 3 树，因而插入操作实际上是与 2 - 3 树一样的。当看到这里时，天然就想到了两个问题：

1. 如前文所诉，2- 3 树的插入是随同着长期的 4 - 节点的产生的（在红黑树中体现为一个节点同时连贯着两条红链接），这时咱们应该如何解决？
2. 在插入中，插入的元素肯定与父节点成红链接（因为插入之后只有 3 - 节点与 4 - 节点两种状况），然而如果插入的元素比父节点的元素大，红链接就会在左边，这同样毁坏了红黑树的构造，这时咱们又该如何解决？

在说具体的插入操作之前，咱们先介绍两种非凡的操作：旋转 与色彩转换。

对于下面两个问题，咱们能够总结出三种根本的非凡构造：

其余的非凡构造均能够合成为如上三种，能够拿笔画图试一下

因而咱们给出三个办法用于解决这三个构造，如图：

Java 实现：

/*------------------- 旋转 ------------------*/
 
/**
     * 向左旋转
     * 当 h 节点的右链接为红而左链接为黑，须要向左旋转
     * 保障红黑树的有序性或者完满平衡性
     * @param h
     * @return
     */
Node rotateLeft(Node h){
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1+size(h.left)+size(h.right);
    return x;
}
 
/**
     * 如果节点的左链接为红，且左子节点的左链接也为红。进行右旋
     * @param h
     * @return
     */
Node rotateRight(Node h){
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1+size(h.left)+size(h.right);
    return x;
}
 
/**
     * 如果节点的左链接和右连贯都为红，则进行色彩转换
     */
void flipColors(Node h){
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}

插入算法的残缺实现：

/* ------------------- 插入操作 ---------------- */
 
/**
 * 插入键值
 * @param key
 * @param value
 */
public void put(Key key, Value value){root = put(root, key, value);
    root.color = BLACK;
}
 
private Node put(Node h, Key key, Value value) {
    // 当发现适合的地位，插入元素。将 2 - 节点转化为 3 - 节点。3- 节点转化为 4 - 节点
    if (h == null) {return new Node(key, value, 1, RED);
    }
 
    // 通过递归找到
    int cmp = key.compareTo(h.key);
    if (cmp < 0) {h.left = put(h.left, key, value);
    } else if (cmp > 0) {h.right = put(h.right, key, value);
    } else {h.val = value;}
 
    // 通过部分的左旋右旋与色彩转化，维系红黑树的完满平衡性
    // 左旋：当 h 节点的右链接为红而左链接为黑，须要向左旋转
    // 右旋：如果节点的左链接为红，且左子节点的左链接也为红。进行右旋
    // 色彩转换：如果节点的左链接和右连贯都为红，则进行色彩转换
    if (isRed(h.right) && !isRed(h.left)) {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;
}

删除操作

咱们首先模仿一下对底部元素的删除操作，容易发现 3 - 节点的删除是非常简单的。然而 2 - 节点会呈现问题，无论哪个 2 - 节点删除，红黑树都不会是完满彩色均衡。

这时咱们回到原来的 2 - 3 查找树，除根节点以外所有的 2 - 节点都是由 4 - 节点成长而来。如果删除掉的是 4 - 节点中的元素，也只是让 4 - 节点进化到 3 - 节点，而不影响红黑树的平衡性。

当初咱们的问题就变成了怎么将 2 - 节点和其余兄弟节点合并成 4 - 节点，且不扭转红黑树的构造.

回顾插入操作,4- 节点是由下向上成长的. 如果向让 2 - 节点从新变为 4 - 节点, 就相当于树的“进化”, 也就是从上到下将查找到的 2 - 节点变为 4 - 节点. 同插入操作, 进化成 4 - 节点是左右子树的高度同时减一, 不须要放心树的平衡性的扭转.

间接思考任意节点的删除还是很麻烦的, 咱们这里先对 最小键的删除 进行探讨:

最小键的删除

删除最小键, 咱们只须要保障树底没有 2 - 节点存在, 即可间接删除.

在沿着左链接向下的过程中, 会有以下三种状况:

• 以后节点的左子节点不是 2 - 节点, 持续遍历
• 以后节点的左子节点是 2 - 节点而它的亲兄弟节点不是 2 - 节点, 将左子节点的兄弟节点的一个节点挪动到左子节点中
• 以后节点的左子节点和它的亲兄弟节点都是 2 - 节点, 将 左子节点 , 父节点中的最小键 和左子节点最近的兄弟节点 合并成一个 4 - 节点.

最初在树底失去一个 3 - 节点或 4 - 节点.

Java 实现操作:

/**
  * 对 2 - 节点的左子节点进行变换
  * @param h
  * @return
  */
private Node moveRedLeft(Node h){// 将左子节点变为 3 - 节点, 即上图 2 的第一步变换(J 和 M 之间的连贯变为红链接)
    flipColors(h);
    // 如果左节点的兄弟节点是 3 - 节点，则通过旋转操作将兄弟节点的借一个元素过去
    if (isRed(h.right.left)){h.right = rotateRight(h.right);
        h = rotateLeft(h);
    }
    return h;
}
 
/**
 * 在回溯过程中，保护红黑树。放弃构造的残缺
 * @param h
 * @return
 */
private Node balance(Node h)
{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);
    }
    return h;
}

最小键删除的实现:

public void deleteMin() {root = deleteMin(root);
    // 将根节点的色彩从新变为彩色
    if (isEmpty()) {root.color = BLACK;}
}
 
private Node deleteMin(Node h) {if (h.left==null) {return null;}
    // 如果左子节点不是 3 - 节点, 则进行变换
    if (!isRed(h.left) && !isRed(h.left.left)){h = moveRedLeft(h);
    }
    h.left = deleteMin(h.left);
    return balance(h);
}
 
private boolean isEmpty() {return root != null;}

最大键删除

最大键的删除原理与最小键类似，只是查找与旋转的方向不同

private Node moveRedRight(Node h){flipColors(h);
    if (isRed(h.left.left)){h = rotateRight(h);
    }
    return h;
}
 
public void deleteMax() {if (!isRed(root.left) && !isRed(root.right)) {root.color = RED;}
    root = deleteMax(root);
    if (isEmpty()) {root.color = BLACK;}
}
 
private Node deleteMax(Node h) {if (h.left==null) {h = rotateRight(h);
    }
    if (h.right == null) {return null;}
    if (!isRed(h.right) && !isRed(h.right.left)){h = moveRedRight(h);
    }
    deleteMax(h.right);
    return balance(h);
}

任意节点的删除

首先同最小键的删除一样，在查找门路上进行 2 -3- 4 树的变换，保障以后节点不是 2 - 节点。如果查找到的键在数的底部，则能够间接删除。如果不在，咱们须要将它与后继节点（在整个二叉树中正好比他大的，即右子树的最小键）替换，相似于二叉查找树。

因为以后节点必然不是 2 - 节点，问题曾经转化为在一颗根节点不是 2 - 节点的子树中删除最小的键，咱们能够在这颗子树中应用前文所述的删除最小键算法。

private Node delete(Node h, Key key) {
    // 如果删除节点小于以后节点，查找并保护左子树
    if (key.compareTo(h.key) < 0){if (!isRed(h.left) && !isRed(h.left.left)) {h = moveRedLeft(h);
        }
        h.left = delete(h.left, key);
    } else {if (isRed(h.left)) {h = rotateRight(h);
        }
        // 找到节点地位，如果在树的底部，间接删除即可
        if (key.compareTo(h.key)==0 && h.right==null) {return null;}
        // 如果以后节点是 2 - 节点，向右边的兄弟节点借元素，使节点变为 3 - 节点或 4 - 节点
        if (!isRed(h.right) && !isRed(h.right.left)) {h = moveRedRight(h);
        }
        // 找到节点地位，遍历失去右子树的最小值
        if (key.compareTo(h.key)==0) {h.val = get(h.right, min(h.right).key);
            h.key = min(h.right).key;
            h.right = deleteMin(h.right);
        } else {h.right = delete(h.right, key);
        }
    }
    return balance(h);
}

红黑树的性质

所有基于红黑树的符号表的实现都能保障操作的运行工夫为对数级别（范畴查找除外，它所需的额定工夫和返回的键的数量成正比）

红黑树的实现仅仅只有 插入与删除 较简单。而其余办法因为不波及节点色彩，与二叉查找树基本相同，因而应用十分宽泛。

各种符号表的性能总结

更多具体的信息能够查看 http://www.cs.princeton.edu/~… 或是《算法》