红黑树

特点

• 每个节点或者是红色的或者是黑色的
• 根结点都是黑色的
• 每一个叶子节点（最后的空节点）是黑色的
• 如果一个节点是红色的，那么他的孩子节点都是黑色的
• 从任意一个节点到叶子节点，经过的黑色节点是一样的

所有红色节点都是向左倾斜的。

红黑树是保持黑平衡的二叉树,严格意义上讲，不是平衡的二叉树，最大的高度是2logn,查询的时间复杂度是O(logn)

实现

public class RBTree<K extends Comparable<K>, V> {
    private static boolean RED = true;
    private static boolean BLACK = false;
    
    private class Node {
        public K key;
        public V value;
        public Node left, right;
        private boolean color;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            // TODO 为何初始化为红色
            color = RED;
        }
    }

    private Node root;
    private int size;

    public RBTree() {
        root = null;
        size = 0;
    }

    // 添加元素
    public void add(K key, V value) {
        root = add(root, key, value);
        root.color = BLACK;// 最终根节点是黑色节点
    }

    private Node add(Node node, K key, V value) {
        if (node == null) {
            size++;
            return new Node(key, value);
        }
        if (node.key.compareTo(key) < 0) {
            node.left = add(node.left, key,value);
        } else if (node.key.compareTo(key) > 0) {
            node.right = add(node.right, key, value);
        } else {
            node.value = value;
        }

        if (isRed(node.right) && !isRed(node.left)) {
            node = leftRotate(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rightRotate(node);
        }
        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node);
        }
        return node;
    }

    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    private Node rightRotate(Node node) {
        Node x = node.left;
        // 右旋转
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }

    private Node leftRotate(Node node) {
        Node x = node.right;
        // 左旋转
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }

    private boolean isRed(Node node) {
        return node.color;
    }
}