红黑树

定义

红黑树是一个平衡的二叉树，其满足如下性质：

1. 节点是红色或者是黑色
2. 根节点是黑色
3. 每个叶节点是黑色
4. 每个红色节点的两个子节点都是黑色的
5. 从根节点到任何叶子节点经过的黑色几点数相同

保持平衡的操作

1. 左旋
   比如对A左旋，则操作如下：

• 将A的右节点赋值为C，更新C的父节点为A
• 将B的父节点赋值为A的父节点，更新A的父节点的孩子为B
• 将B的左节点赋值为A，更新A的父节点为B

image.png

2. 右旋
   比如对A右旋，则操作如下：

• 将A的左子节点赋值为C，更新C的父节点为A
• 将B的父节点赋值为A的父节点，更新A的父节点的孩子为B

• 将B的右子节点赋值为A，更新A的父节点为B

  
  image.png

保持平衡情况分析

1. 插入

• 当前节点的父节点是祖父节点的左孩子，叔叔节点是红色，则叔叔节点、父节点设置为黑，祖父节点设置为红，当前节点设置为祖父节点

• 当前节点的父节点是祖父节点的左孩子，叔叔节点是黑色，当前节点为右孩子则以父节点左旋，当前节点设置为父节点

• 当前节点的父节点是祖父节点的左孩子，叔叔节点是黑色，当前节点为左孩子则将父节点设置为黑，祖父节点设置为红，以祖父节点右旋

• 当前节点的父节点是祖父节点的右孩子，叔叔节点是红色，则叔叔节点、父节点设置为黑，祖父节点设置为红，当前节点设置为祖父节点

• 当前节点的父节点是祖父节点的右孩子，叔叔节点是黑色，当前节点为左孩子则以父节点右旋，当前节点设置为父节点

• 当前节点的父节点是祖父节点的右孩子，叔叔节点是黑色，当前节点为右孩子则将父节点设置为黑，祖父节点设置为红，以祖父节点左旋

代码实现参考TreeMap的实现

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) {//如果y为null，则视为BLACK
                setColor(parentOf(x), BLACK);              // 情况1
                setColor(y, BLACK);                        // 情况1
                setColor(parentOf(parentOf(x)), RED);      // 情况1
                x = parentOf(parentOf(x));                 // 情况1
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);                       // 情况2
                    rotateLeft(x);                         // 情况2
                }
                setColor(parentOf(x), BLACK);              // 情况3
                setColor(parentOf(parentOf(x)), RED);      // 情况3
                rotateRight(parentOf(parentOf(x)));        // 情况3
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);              // 情况4
                setColor(y, BLACK);                        // 情况4
                setColor(parentOf(parentOf(x)), RED);      // 情况4
                x = parentOf(parentOf(x));                 // 情况4
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);                       // 情况5
                    rotateRight(x);                        // 情况5
                }
                setColor(parentOf(x), BLACK);              // 情况6
                setColor(parentOf(parentOf(x)), RED);      // 情况6
                rotateLeft(parentOf(parentOf(x)));         // 情况6
            }
        }
    }
    root.color = BLACK;
}

应用以及 性能

linux的虚拟内存管理以及java中的treeset和treemap，其时间复杂度在O(lgn),此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。