从TreeMap学习红黑树

红黑树是一种自平衡二叉查找树，常用于键值对存储，例如Java的TreeMap中就采用红黑树实现。它可以在O(logN)时间内查找、插入和删除

红黑树定义与性质

红黑树定义

1. 点是红色或者黑色

2. 根节点是黑色

3. 所有叶子节点是黑色（null节点）

4. 每个红色节点都必须要有两个黑色子节点

5. 从任一节点到叶子节点都包含同样数目的黑色节点

红黑树性质

根据红黑树的定义，从根到叶子的最长路径不多于最短的两倍。由于性质4每个红色节点均有两个黑色节点，性质5限制了黑色节点的数目，这样可以限制最短的路径为全是黑色节点的，而最长的路径为红黑节点交替的路径

TreeMap中红黑树

红黑树仍是一个二叉排序树，如果是二叉排序树那么

• 若左子树不空，则左子树上的值均小于它的根节点

• 若右子树不空，则右子树上的值均大于它的根节点

• 它的左右字数也分别为排序二叉树

那么，对一棵二叉排序树进行中序遍历就可以得到排序后的结果

中序排序后为 1，2，3，4，5，7

树的旋转

红黑树的旋转可以保持节点符合排序的规则，但是不一定能使其满足红黑树的红黑颜色规则，需要对其进行修复。其操作分为左旋，右旋

• 左旋

操作在旋转节点的右子树，将待旋转节点的右节点上升到父节点的位置上

private void rotateLeft(RedBlackNode<T> node) {
    if (node != null) {
        RedBlackNode<T> rChild = node.right;
        node.right = rChild.left;
        if (rChild.left != null)
            rChild.left.parent = node;
        rChild.parent = node.parent;
        if (node.parent == null)
            root = rChild;
        else if (node.parent.left == node)
            node.parent.left = rChild;
        else
            node.parent.right = rChild;
        rChild.left = node;
        node.parent = rChild;
    }
}

• 右旋

操作在旋转节点的左子树，将待旋转节点的左节点上升到父节点的位置上

private void rotateRight(RedBlackNode<T> node) {
    if (node != null) {
        RedBlackNode<T> lChild = node.left;
        node.left = lChild.right;
        if (lChild.right != null)
            lChild.parent = node;
        lChild.parent = node.parent;
        if (node.parent == null)
            root = lChild;
        else if (node.parent.left == node)
            node.parent.left = lChild;
        else
            node.parent.right = lChild;
        lChild.right = node;
        node.parent = lChild;
    }
}

红黑树的插入

红黑树的插入，首先确认插入的位置

private T insert(final RedBlackNode<T> newNode) {
    RedBlackNode<T> t = root;
    if (t == null) { // 如果为空树
        root = newNode;
        size = 1;
        return newNode.key;
    }
    RedBlackNode<T> parent;
    int cmp;
    do {
        parent = t;
        cmp = compare(newNode, t);
        if (cmp < 0) {
            t = t.left;
        } else if (cmp > 0) {
            t = t.right;
        } else {
            return t.key;
        }
    } while (t != null); // 查找到合适的位置

    newNode.parent = parent;
    if (cmp < 0) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    fixInsertion(newNode);
    size++;
    return null;
}

红黑树插入修复

插入之后需要对树进行修复，使其满足红黑树的性质

其中，

• 如果插入的是根节点，将新加入节点涂黑，对树没有影响，直接插入

• 如果插入的节点的父节点为黑色节点，对树没有影响

但是，当遇到

1. 当前节点的父节点是红色并且叔叔节点是红色

插入新节点为颜色为红色，不符合红黑树定义。需要进行调整

假如叔叔节点为祖父节点的右孩子。那么插入修复需要将当前节点的父亲节点和叔叔节点的颜色改为黑色，并将祖父节点变更为红色，当前节点指向祖父节点，继续进行修复

2. 当前节点的父节点为红色，叔叔节点为黑色，当前节点为父节点的右节点

同样不符合红黑树定义

如果当前节点的父节点为祖父节点的左孩子，则将当前节点指向当前节点的父节点，对新当前节点左旋

情况2修复完成之后，需要继续进行情况3的修复

3. 当前节点的父节点为红色，叔叔节点为黑色，当前节点为父节点左节点

如果当前节点的父节点是祖父节点的左孩子，则将父节点变为黑色，祖父节点变为红色，并且以祖父节点为支点右旋

private void fixInsertion(RedBlackNode<T> node) {
    node.color = RED;

    while (node != null && node != root && colorOf(parentOf(node)) == RED {
        if (parentOf(node) == leftOf(ancestorOf(node))) {
            // 当前的父节点是祖父节点的左孩子
            RedBlackNode<T> uncle = rightOf(ancestorOf(node));
            if (colorOf(uncle) == RED) {
                setColor(parentOf(node), BLACK);
                setColor(uncle, BLACK);
                setColor(ancestorOf(node), RED);
                node = ancestorOf(node);
            } else {
                if (node == rightOf(parentOf(node))) {
                    node = parentOf(node);
                    rotateLeft(node);
                }
                setColor(parentOf(node), BLACK);
                setColor(ancestorOf(node), RED);
                rotateRight(ancestorOf(node));
            }
        } else {
            RedBlackNode<T> uncle = leftOf(ancestorOf(node));
            if (colorOf(uncle) == RED) {
                setColor(parentOf(node), BLACK);
                setColor(uncle, BLACK);
                setColor(ancestorOf(node), RED);
                node = ancestorOf(node);
            } else {
                if (node == leftOf(parentOf(node))) {
                    node = parentOf(node);
                    rotateRight(node);
                }
                setColor(parentOf(node), BLACK);
                setColor(ancestorOf(node), RED);
                rotateLeft(ancestorOf(node));
            }
        }
    }
    root.color = BLACK;
}

插入的修复过程是不断向走向根节点的，然后把整棵树修复

红黑树的删除

删除红黑树中的节点之后，需要对树进行维护使得红黑树仍符合红黑树的定义

1. 如果被删除的节点是叶结点，没有孩子，直接从其父节点中删除此节点即可

2. 如果只有一个孩子，则直接将父节点的对应的孩子指向这个孩子即可

3. 如果有两个孩子，情况会复杂点。首先需要保证符合排序二叉树的性质。删除此结点之后，可以选择其左子树的最大结点或者右子树的最小结点替换。TreeMap中是寻找了被删除的结点的中序遍历的后继结点，也就是选择了右子树的最小结点来替换这个结点。

private void deleteNode(RedBlackNode<T> node) {
    size--;
    if (node.left != null && node.right != null) {
        // 中序后继节点替代
        RedBlackNode<T> next = successor(node);
        // 注意此时替换了key值
        node.key = next.key;
        // 仅仅替换了引用
        node = next;
    }
    // 对替换的结点 与 被删除的结点进行替换
    RedBlackNode<T> replacement = (node.left != null ? node.left : node.right);

    // 对替换的结点的孩子进行连接，并脱离被替换节点
    if (replacement != null) {
        replacement.parent = node.parent;
        if (node.parent == null)
            root = replacement;
        else if (node == node.parent.left)
            node.parent.left = replacement;
        else node.parent.right = replacement;

        node.left = node.right = node.parent = null;

        if (node.color == BLACK)
            fixDeletion(replacement);
    } else if (node.parent == null) {
        // 当前删除的节点是根节点
        root = null;
    } else {
        if (node.color == BLACK)
            fixDeletion(node);

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

红黑树删除修复

如果被删除的结点是红色，则不需要做任何修复即可

如果被是删除结点是黑色，则有可能会造成红黑树性质被破坏

• 如果删除的黑色不是红黑树的唯一结点，那么从被删除结点的分支的黑色结点数必然会不正确，性质5被破坏
• 如果被删除结点的唯一非空子结点是红色，且父结点也是红色，违反性质4
• 如果被删除结点为根节点，且其替换结点为红色，违反性质2

针对以上的情况，分以下解决（讨论当前结点为父结点左孩子）

“下面我们用一个分析技巧：我们从被删结点后来顶替它的那个结点开始调整，并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢，我们不是把红黑树的结点加上除红与黑的另一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父结点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色，那么现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这重额外的黑色，原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了，做法还是尽量向根移动和穷举所有可能性。”–saturnman

1. 当前结点（被替换的结点）为黑色+黑色，且兄弟结点为红色

此时父结点为黑色，并且兄弟的孩子结点也都为黑色，那么把父结点染红，兄弟结点染黑，之后以父结点为点左旋，更新下兄弟节点。这样转化问题为兄弟节点为黑色的问题。这时替换结点上仍有一重黑色，继续进入算法

if (colorOf(sibling) == RED) {
    setColor(sibling, BLACK);
    setColor(parentOf(node), RED);
    rotateLeft(parentOf(node));
    sibling = rightOf(parentOf(node));
}

2. 当前为黑+黑，兄弟节点为黑色，且兄弟节点的孩子也为黑色

这时候需要将当前结点和兄弟节点中剥离出来一层黑色给他们的父结点。那么当前为黑+黑，因此还是黑色，而兄弟结点只有一层黑色，因此变为红色，如果父结点为红色，则算法结束，否则继续以父结点为当前结点继续进行算法

if (colorOf(leftOf(sibling)) == BLACK &&
        colorOf(rightOf(sibling)) == BLACK) {
    setColor(sibling, RED);
    node = parentOf(node);
}

3. 当前为黑+黑，兄弟结点为黑色，且兄弟结点的左孩子为红色，右孩子为黑色

这种情况需要转化为情况4，因此将兄弟结点染红，兄弟的左子染黑，之后右旋，更新兄弟结点

if (colorOf(rightOf(sibling)) == BLACK) {
    setColor(leftOf(sibling), RED);
    setColor(sibling, RED);
    rotateRight(sibling);
    sibling = rightOf(parentOf(node));
}

4. 当前结点为黑+黑，兄弟结点为黑色，且兄弟结点的右孩子为红色，左孩子为任意颜色

将兄弟结点染成父结点颜色，父结点染成黑色，兄弟结点右孩子染黑，以父结点为支点左旋。当前结点设为根节点，调整结束

setColor(sibling, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(rightOf(sibling), BLACK);
rotateLeft(parentOf(node));
node = root;

其实这个修复删除的过程就是调整替代结点的多加的这层黑色，使其能够补偿到被删除的黑色结点，这样就可以在保持红黑树的性质。

参考

• 红黑树深入剖析及Java实现

• 教你透彻了解红黑树

实现

package me.learn.datastruct;

import java.util.LinkedList;
import java.util.Queue;

public class RedBlackTree<T extends Comparable<T>> {

    private transient RedBlackNode<T> root;
    private transient int size = 0;

    public void add(T key) {
        RedBlackNode<T> node = new RedBlackNode<>(key);
        insert(node);
    }

    public void remove(T key) {
        RedBlackNode<T> node = getNode(key);
        if (node == null)
            return;
        deleteNode(node);
    }

    private void deleteNode(RedBlackNode<T> node) {
        size--;
        if (node.left != null && node.right != null) {
            // 中序后继节点替代
            RedBlackNode<T> next = successor(node);
            node.key = next.key;
            node = next;
        }
        RedBlackNode<T> replacement = (node.left != null ? node.left : node.right);

        if (replacement != null) {
            replacement.parent = node.parent;
            if (node.parent == null)
                root = replacement;
            else if (node == node.parent.left)
                node.parent.left = replacement;
            else node.parent.right = replacement;

            node.left = node.right = node.parent = null;

            if (node.color == BLACK)
                fixDeletion(replacement);
        } else if (node.parent == null) {
            // 当前删除的节点是根节点
            root = null;
        } else {
            if (node.color == BLACK)
                fixDeletion(node);

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

    private void fixDeletion(RedBlackNode<T> node) {
        while (node != root && colorOf(node) == BLACK) {
            if (node == leftOf(parentOf(node))) {
                RedBlackNode<T> sibling = rightOf(parentOf(node));

                if (colorOf(sibling) == RED) {
                    setColor(sibling, BLACK);
                    setColor(parentOf(node), RED);
                    rotateLeft(parentOf(node));
                    sibling = rightOf(parentOf(node));
                }

                if (colorOf(leftOf(sibling)) == BLACK &&
                        colorOf(rightOf(sibling)) == BLACK) {
                    setColor(sibling, RED);
                    node = parentOf(node);
                } else {
                    if (colorOf(rightOf(sibling)) == BLACK) {
                        setColor(leftOf(sibling), RED);
                        setColor(sibling, RED);
                        rotateRight(sibling);
                        sibling = rightOf(parentOf(node));
                    }
                    setColor(sibling, colorOf(parentOf(node)));
                    setColor(parentOf(node), BLACK);
                    setColor(rightOf(sibling), BLACK);
                    rotateLeft(parentOf(node));
                    node = root;
                }
            } else {
                RedBlackNode<T> sibling = leftOf(parentOf(node));

                if (colorOf(sibling) == RED) {
                    setColor(sibling, BLACK);
                    setColor(parentOf(node), RED);
                    rotateRight(parentOf(node));
                    sibling = leftOf(parentOf(node));
                }

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

        setColor(node, BLACK);
    }

    /**
     * node 中序的后继节点
     * @param node
     * @return
     */
    private RedBlackNode<T> successor(RedBlackNode<T> node) {
        if (node == null)
            return null;
        if (node.right != null) {
            RedBlackNode<T> t = node.right;
            while (t.left != null)
                t = t.left;
            return t;
        } else {
            RedBlackNode<T> p = node.parent;
            RedBlackNode<T> child = node;
            while (p != null && child == p.right) {
                child = p;
                p = p.parent;
            }
            return p;
        }
    }

    private RedBlackNode<T> getNode(T key) {
        if (key == null)
            throw new NullPointerException();
        RedBlackNode<T> node = root;
        while (node != null) {
            int cmp = key.compareTo(node.key);
            if (cmp < 0)
                node = node.left;
            else if (cmp > 0)
                node = node.right;
            else
                return node;
        }
        return null;
    }

    private T insert(final RedBlackNode<T> newNode) {
        RedBlackNode<T> t = root;
        if (t == null) {
            root = newNode;
            size = 1;
            return newNode.key;
        }
        RedBlackNode<T> parent;
        int cmp;
        do {
            parent = t;
            cmp = compare(newNode, t);
            if (cmp < 0) {
                t = t.left;
            } else if (cmp > 0) {
                t = t.right;
            } else {
                return t.key;
            }
        } while (t != null);

        newNode.parent = parent;
        if (cmp < 0) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        fixInsertion(newNode);
        size++;
        return null;
    }

    private void fixInsertion(RedBlackNode<T> node) {
        node.color = RED;

        while (node != null && node != root && colorOf(parentOf(node)) == RED) {
            if (parentOf(node) == leftOf(ancestorOf(node))) {
                // 当前的父节点是祖父节点的左孩子
                RedBlackNode<T> uncle = rightOf(ancestorOf(node));
                if (colorOf(uncle) == RED) {
                    setColor(parentOf(node), BLACK);
                    setColor(uncle, BLACK);
                    setColor(ancestorOf(node), RED);
                    node = ancestorOf(node);
                } else {
                    if (node == rightOf(parentOf(node))) {
                        node = parentOf(node);
                        rotateLeft(node);
                    }
                    setColor(parentOf(node), BLACK);
                    setColor(ancestorOf(node), RED);
                    rotateRight(ancestorOf(node));
                }
            } else {
                RedBlackNode<T> uncle = leftOf(ancestorOf(node));
                if (colorOf(uncle) == RED) {
                    setColor(parentOf(node), BLACK);
                    setColor(uncle, BLACK);
                    setColor(ancestorOf(node), RED);
                    node = ancestorOf(node);
                } else {
                    if (node == leftOf(parentOf(node))) {
                        node = parentOf(node);
                        rotateRight(node);
                    }
                    setColor(parentOf(node), BLACK);
                    setColor(ancestorOf(node), RED);
                    rotateLeft(ancestorOf(node));
                }
            }
        }
        root.color = BLACK;
    }

    private void rotateLeft(RedBlackNode<T> node) {
        if (node != null) {
            RedBlackNode<T> rChild = node.right;
            node.right = rChild.left;
            if (rChild.left != null)
                rChild.left.parent = node;
            rChild.parent = node.parent;
            if (node.parent == null)
                root = rChild;
            else if (node.parent.left == node)
                node.parent.left = rChild;
            else
                node.parent.right = rChild;
            rChild.left = node;
            node.parent = rChild;
        }
    }

    private void rotateRight(RedBlackNode<T> node) {
        if (node != null) {
            RedBlackNode<T> lChild = node.left;
            node.left = lChild.right;
            if (lChild.right != null)
                lChild.parent = node;
            lChild.parent = node.parent;
            if (node.parent == null)
                root = lChild;
            else if (node.parent.left == node)
                node.parent.left = lChild;
            else
                node.parent.right = lChild;
            lChild.right = node;
            node.parent = lChild;
        }
    }

    private void setColor(RedBlackNode<T> node, boolean color) {
        if (node != null) node.color = color;
    }

    private boolean colorOf(RedBlackNode<T> node) {
        return node == null ? BLACK : node.color;
    }

    private RedBlackNode<T> ancestorOf(RedBlackNode<T> node) {
        return parentOf(parentOf(node));
    }

    private RedBlackNode<T> parentOf(RedBlackNode<T> node) {
        return node.parent;
    }

    private RedBlackNode<T> leftOf(RedBlackNode<T> node) {
        return node.left;
    }

    private RedBlackNode<T> rightOf(RedBlackNode<T> node) {
        return node.right;
    }

    private int compare(RedBlackNode<T> t1, RedBlackNode<T> t2) {
        return t1.key.compareTo(t2.key);
    }

    private static final boolean BLACK = true;
    private static final boolean RED = false;

    static final class RedBlackNode<T extends Comparable<T>> {
        T key;
        RedBlackNode<T> left;
        RedBlackNode<T> right;
        RedBlackNode<T> parent;
        boolean color = BLACK;

        public RedBlackNode() {
        }

        public RedBlackNode(T key) {
            this.key = key;
        }

        public RedBlackNode(T key, RedBlackNode<T> parent) {
            this.key = key;
            this.parent = parent;
        }

        @Override
        public String toString() {
            String result = "";
            return color == RED && parent != null ?
                    String.format("[Red][parent[%s]][key[%s]]", parent.key, key)
                    : color == BLACK && parent != null ?
                    String.format("[BLK][parent[%s]][key[%s]]", parent.key, key)
                    : String.format("ROOT[key[%s]]", key);
        }
    }

    private void printTree() {
        RedBlackNode<T> rootData = root;
        Queue<RedBlackNode<T>> queue = new LinkedList<>();
        Queue<RedBlackNode<T>> queue1 = new LinkedList<>();
        queue.offer(rootData);
        boolean isDefaultQueue = true;

        while (!queue.isEmpty() || !queue1.isEmpty()) {
            Queue<RedBlackNode<T>> mQueue = isDefaultQueue ? queue : queue1;
            RedBlackNode<T> node = mQueue.poll();
            if (node != null) {
                String nodeInfo = "";
                if (node.parent != null) {
                    if (node == node.parent.left)
                        nodeInfo = "[LE]";
                    else
                        nodeInfo = "[RH]";
                }
                if (node.left != null) {
                    (isDefaultQueue ? queue1 : queue).offer(node.left);
                }
                if (node.right != null) {
                    (isDefaultQueue ? queue1 : queue).offer(node.right);
                }
                System.out.print(nodeInfo + node + "\t");
            } else {
                System.out.println();
                isDefaultQueue = !isDefaultQueue;
            }
        }
    }

    public static void main(String[] argv) {
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        tree.add(5);
        tree.add(10);
        tree.printTree();
        System.out.println("\n===============================");
        tree.remove(4);
        tree.printTree();
    }
}