红黑树

厶汀 2013-10-25

展开全文

概念
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
　　红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。

性质
　　红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
　　性质1. 节点是红色或黑色。
　　性质2. 根是黑色。
　　性质3. 所有叶子都是黑色（叶子是NIL节点）。
　　性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
　　性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
　　
　　这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
　　要知道为什么这些特性确保了这个结果，注意到属性4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据属性5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

一种红黑树的实现方法：

/**
* 红黑树的实现
**/
public class RBTreeTest<E extends Comparable<E>> {
    static enum Color {
        BLACK, RED
    }

    static class RBPrinter {
        public static void visitNode(RBNode node) {
            RBNode n = node;
            if (n != null)
                System.out.print(n.key + "("
                        + (n.color == Color.RED ? "RED" : "BLACK")
                        + "),");
        }
    }

static class RBNode<E extends Comparable<E>> {
E key;

RBNode<E> left, right;

RBNode<E> parent;

Color color;

        RBNode(RBNode<E> p, E key, Color color) {
            this.key = key;
            this.color = color;
            this.parent = p;
            this.left = null;
            this.right = null;
        }
    }

private RBNode<E> root;

    public RBTreeTest() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public E findMax() {
        if (isEmpty())
            return null;
        RBNode<E> node = root;
        while ((node.right) != null) {
            node = node.right;
        }
        return node.key;
    }

    public E findMin() {
        if (isEmpty())
            return null;
        RBNode<E> node = root;
        while ((node.left) != null) {
            node = node.left;
        }
        return node.key;
    }

    public final boolean contains(E ele) {
        RBNode<E> tmp = root;
        int cmp = -1;
        while (tmp != null) {
            cmp = ele.compareTo(tmp.key);
            if (cmp < 0) {
                tmp = tmp.left;
            } else if (cmp > 0) {
                tmp = tmp.right;
            } else {
                return true;
            }
        }
        return false;
    }

    public final boolean delete(E ele) {
        RBNode<E> cur;
        int cmp;
        if (root == null)
            return false;
        cur = root;
        while (cur != null && (cmp = ele.compareTo(cur.key)) != 0) {
            if (cmp < 0)
                cur = cur.left;
            else
                cur = cur.right;
        }
        if (cur == null) {
            return false;
        }
        if ((cur.left) != null && (cur.right) != null) {
            RBNode<E> prev = cur.left;
            while ((prev.right) != null) {
                prev = prev.right;
            }
            cur.key = prev.key;
            cur = prev;
        }
        if ((cur.left) != null) {
            if (cur == root) {
                root = cur.left;
                root.color = Color.BLACK;
                return true;
            }
            if (cur.parent.left == cur) {
                cur.parent.left = cur.left;
                cur.left.parent = cur.parent;
            } else {
                cur.parent.right = cur.left;
                cur.left.parent = cur.parent;
            }
            if (cur.color == Color.BLACK) {
                cur.left.color = Color.BLACK;
            }
        } else if ((cur.right) != null) {
            if (cur == root) {
                root = cur.right;
                root.color = Color.BLACK;
                return true;
            }
            if (cur.parent.left == cur) {
                cur.parent.left = cur.right;
                cur.right.parent = cur.parent;
            } else {
                cur.parent.right = cur.right;
                cur.right.parent = cur.parent;
            }
            if (cur.color == Color.BLACK) {
                cur.right.color = Color.BLACK;
            }
        } else {
            if (cur == root) {
                root = null;
                return true;
            }
            RBNode<E> todo;
            if (cur.parent.left == cur) {
                todo = null;
                cur.parent.left = todo;
            } else {
                todo = null;
                cur.parent.right = todo;
            }
            if (cur.color == Color.BLACK) {
                fixupDoubleBlack(todo);
            }
        }
        return true;
    }

    private final void fixupDoubleBlack(RBNode<E> cur) {
        RBNode<E> sibling;
        RBNode<E> p;

        while (cur != root) {
            p = cur.parent;
            if (p.left == cur) {
                sibling = p.right;
                if (sibling.color == Color.RED) {
                    rotateLeft(p);
                    p.color = Color.RED;
                    sibling.color = Color.BLACK;
                } else {
                    if (sibling.right.color == Color.RED) {
                        rotateLeft(p);
                        p.color = Color.BLACK;
                        sibling.right.color = Color.BLACK;
                        return;
                    } else if (sibling.left.color == Color.RED) {
                        rotateRight(sibling);
                        sibling.color = Color.RED;
                        sibling.parent.color = Color.BLACK;
                    } else {
                        sibling.color = Color.RED;
                        if (p.color == Color.BLACK) {
                            cur = p;
                        } else {
                            p.color = Color.BLACK;
                            return;
                        }
                    }
                }
            } else {
                sibling = p.left;
                if (sibling.color == Color.RED) {
                    rotateRight(p);
                    p.color = Color.RED;
                    sibling.color = Color.BLACK;
                } else {
                    if (sibling.left.color == Color.RED) {
                        rotateRight(p);
                        sibling.color = p.color;
                        p.color = Color.BLACK;
                        sibling.left.color = Color.BLACK;
                        return;
                    } else if (sibling.right.color == Color.RED) {
                        rotateLeft(sibling);
                        sibling.color = Color.RED;
                        sibling.parent.color = Color.BLACK;
                    } else {
                        sibling.color = Color.RED;
                        if (p.color == Color.BLACK) {
                            cur = p;
                        } else {
                            p.color = Color.BLACK;
                            return;
                        }
                    }
                }
            }
        }
    }

    public final void insert(E ele) {
        if (root == null) { // 添加根节点
            root = new RBNode<E>(null, ele, Color.BLACK);
            return;
        } else { // 将该节点添加到合适的叶子节点的位置
            RBNode<E> parent = null;
            RBNode<E> cur = root;
            int cmp = -1;
            while (cur != null && (cmp = ele.compareTo(cur.key)) != 0) {
                parent = cur;
                if (cmp < 0)
                    cur = cur.left;
                else
                    cur = cur.right;
            }
            if (cmp == 0) { // 不能添加相同的元素
                throw new IllegalArgumentException(
                        "can't insert duplicate key!");
            }
            cur = new RBNode<E>(parent, ele, Color.RED);
            if (cmp < 0) { // 添加为左孩子
                parent.left = cur;
            } else { // 添加为右孩子
                parent.right = cur;
            }

            insertFixup(cur); // 调整各个节点
        }
    }

    private final void insertFixup(RBNode<E> cur) {
        RBNode<E> p, g;
        while (cur != root && cur.color == Color.RED) {
            p = cur.parent;
            if (p.color == Color.BLACK) {
                return;
            }
            g = p.parent;
            if (p == g.left) { // p是g的左子树
                RBNode<E> uncle = g.right;
                if (uncle != null && uncle.color == Color.RED) {
                    g.color = Color.RED;
                    uncle.color = p.color = Color.BLACK;
                    cur = g;
                } else {
                    if (cur == p.right) {
                        cur = rotateLeft(p);
                        cur = cur.left;
                    }
                    cur = rotateRight(g);
                    cur.color = Color.BLACK;
                    cur.left.color = cur.right.color = Color.RED;
                }
            } else { // p是g的右子树
                RBNode<E> uncle = g.left;
                if (uncle != null && uncle.color == Color.RED) {
                    g.color = Color.RED;
                    uncle.color = p.color = Color.BLACK;
                    cur = g;
                } else {
                    if (cur == p.left) {
                        cur = rotateRight(p);
                        cur = cur.right;
                    }
                    cur = rotateLeft(g);
                    cur.color = Color.BLACK;
                    cur.left.color = cur.right.color = Color.RED;
                }
            }
        }
        root.color = Color.BLACK;
    }

    /*
     *      gr           gr           gr
     *     /            /              /
     *    p                            ch
     *   / \   =>    p ch   =>   / \         ch绕着父节点p左旋（即将父节点p和它的右孩子转换角色）
     * 1 ch       /       \         p    3
     *     / \     1   2    3      / \
     *   2    3                   1    2
     */
    private final RBNode<E> rotateLeft(RBNode<E> p) {
        RBNode<E> gr = p.parent;//grandfather
        RBNode<E> ch = p.right;    //children
        p.right = ch.left;
        if (ch.left != null) {
            ch.left.parent = p;
        }
        ch.left = p;
        p.parent = ch;

        if (gr != null) {    //p不是root节点
            if (gr.left == p)    //如果p是gr的左孩子
                gr.left = ch;
            else                //p是gr的右孩子
                gr.right = ch;
        } else {            //p是root节点
            root = ch;
        }
        ch.parent = gr;
        return ch;
    }

   /*
     *       gr           gr            gr
     *      /             /               /
     *     p                           ch
     *    / \   =>   ch p   =>   / \         ch绕着父节点p右旋（即将父节点p和它的左孩子转换角色）
     *   ch 3      /       \        1   p
     *   / \         1   2    3           / \
     * 1    2                         2   3
     */
    private final RBNode<E> rotateRight(RBNode<E> p) {
        RBNode<E> gr = p.parent;
        RBNode<E> ch = p.left;
        p.left = ch.right;
        if (ch.right != null) {
            ch.right.parent = p;
        }
        ch.right = p;
        p.parent = ch;
        if (gr != null) {
            if (gr.left == p)
                gr.left = ch;
            else
                gr.right = ch;
        } else {
            root = ch;
        }
        ch.parent = gr;
        return ch;
    }

    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(RBNode<E> cur) {
        if(cur != null){
            inOrder(cur.left);
            RBPrinter.visitNode(cur);
            inOrder(cur.right);
        }
    }

    public static void main(String[] args) {
        java.util.Random ran = new java.util.Random();
        RBTreeTest<Integer> rbt = new RBTreeTest<Integer>();
        int tmp = 0;
        for(int i=0;i<15;i++){
            tmp = ran.nextInt(1000);
            try{
                rbt.insert(tmp);
            } catch (IllegalArgumentException e){
                do{
                    tmp = ran.nextInt(1000);
                }while(rbt.contains(tmp));
                rbt.insert(tmp);
            }
            System.out.println(tmp);
        }

        System.out.print("\nInorder begin:\n");
        rbt.inOrder();
        System.out.print("\nInorder end\n");

        rbt.delete(tmp);

        System.out.print("\nInorder begin:\n");
        rbt.inOrder();
        System.out.print("\nInorder end\n");
    }
}