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

红黑树

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

在引入红黑树之前，咱们须要理解一下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/~… 或是《算法》