Red-Black Tree

你必须非常努力,才能看起来毫不费力 ———TreeMap

查找

查找几乎是现在每时每刻都在用的东西，查找的速度决定了发展的速度。
常用查找如：

1. 顺序查找
2. 二分查找
3. 插值查找
4. 斐波那契查找
5. 树查找
6. 分块查找
7. 哈希查找

二叉树查找

算法思想：为了查找的方便和快捷，先把待查找的数据生成一棵二叉排序树，利用排序树进行查找

二叉排序树有几个性值：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 任意节点的左、右子树也分别为二叉查找树。

4. 二叉查找树性质：对二叉查找树进行中序遍历(左根右)，即可得到有序的数列。

时间复杂度分析：

1. 最优的情况是一个我们构建出一个完全二叉树,时间复杂度与二分查找相同,即树的高度，为O(logn)。
2. 最坏情况是构造出一个单支树,时间复杂度为O(n);

所以，想享受O(logn)的时间复杂度的代价就是，花大功夫构造出一个便于查找的二叉树树。

2-3查找树

2-3节点有下列三种可能：

1. 节点为空节点

2. 节点为2节点，2节点中有一个key,有两个2-3节点。左子所有key比2节点的key都小，右子所有key比2节点的key都大。

3. 节点为3节点，3节点中有两个key,有三个2-3节点，左子所有key比3节点小的key都小，中子所有key都介于3节点两个key之间,右子所有key比3节点大的key都大。

2-3查找树特性：

1. 在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。

时间复杂度分析：

1. 最坏情况是所有节点都是2节点，回归二叉树，而且二叉树最优情况完全二叉树，时间复杂度为O(log2n);
2. 最好情况是所有节点都是3节点，时间复杂度就是O(log3n),约等于O(0.631log2n)。

红黑树

红黑树是2-3查找树最简单的一种实现。
红黑树特性：

1. 每个节点或者是黑色，或者是红色。根节点是黑色。
2. 每个叶子节点（为空的）都是黑色。
3. 红色节点的子节点都是黑色
4. 一个节点到每个子孙节点（叶子节点），经过的黑色节点数都是相同的。

为什么说红黑树是2-3树的简单实现呢。
把每个节点看作是2节点。
规定红色节点与左子的链接为红色链接。
红色链接连接的两个节点看做是一个3节点,就转化成了2-3查找树

TreeMap源码解析（基于jdk1.7）

TreeMap是红黑树的实现,首先来看一下TreeMap的Entry

K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;

与树的Entry相比多了一个颜色标志位 color。

TreeMap的常用操作

1. get()
2. put()
3. remove()

get()

因为TreeMap是已经平衡过的树（因为每次对树的解构进行改动的时候都会重新调整一遍树的机构使其每次使用时都保持最佳状态，映照开头第一句话），所以get()操作就是对排序树的遍历查找，与根节点比较，从而判断下一步走向。如此循环，直至找到对应Entry，或者没有找到而结束。

get()方法调用getEntry方法实现遍历查找

final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

Offload comparator-based version for sake of performance(为了性能，卸载基于比较器的版本)

put()

put()方法则是先进行一遍get操作，通过K比较，将新Entry放在合适位置，如果是普通二叉树，插入操作到这里就结束了，但是这是红黑树。需要对数的结构进行负责。所以在找到合适位置，插入新Entry之后又对红黑树进行了整体调整。

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

remove()

remove()方法同样是需要先调用getEntry找到要删除的元素，然后调用deleteEntry删除该元素，删除元素之后同样需要再次对红黑树进行解构调整。

public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }

private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

private void fixAfterDeletion(Entry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {
            if (x == leftOf(parentOf(x))) {
                Entry<K,V> sib = rightOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }

                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else { // symmetric
                Entry<K,V> sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }

        setColor(x, BLACK);
    }

总结一下：