红黑树笔记

0、2-3树

• 满足二分搜索树的基本性质
• 节点可以存放一个元素或者两个元素，分别称为2节点和3节点
• 2-3树绝对平衡
• 2-3树的插入：假设依次插入42，37，12，则首先创建一个节点42，37来之后会和42节点合并形成一个3节点，12来后会先暂时和42,37形成节点[12,37,42]，然后进行分裂，37为根，12为左子树，42为右子树

红黑树和2-3树的等价性：

所有红色节点向左倾斜

1、红黑树特性

• 红黑树是一颗二叉搜索树
• 根节点是黑色(2-3树中两种节点显然易得)
• 叶子节点(空节点)是黑色
• 红色节点的孩子是黑色的，黑色节点的孩子有红有黑（2-3树性质得到）
• 从任意一个节点到空叶子节点，经过的黑节点数目一样（2-3树的绝对平衡）
• 由上一条定义可以得到：从根节点到叶子节点的最长路径最多是最短路径的2倍
• 由上一条性质可以得到，红黑树最大高度为$O(2logn)$，极端情况下有一条路径，每个黑色节点对应一个红色节点

2、插入元素

默认添加红节点

情形一：树为空时

添加红色节点，并将此节点变为黑色，以满足定义。

情形二：保持根节点颜色为黑色

当插入元素后，树的根节点可能会发生变化，此时我们需要维护根节点颜色始终为黑色

情形三：插入一个元素在某个节点的左边，直接插入，不用旋转

情形四：插入一个元素在某个节点的右边，此时不满足红节点左倾，需要左旋转

左旋转：左旋转后并不一定满足红黑树性质，还需要配合后续操作

/*
    node                         x
   /    \         左旋转        /  \
  T1     x      --------->   node  T3
        / \                 /   \
       T2 T3               T1   T2
 */
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;
}

情形四：向红黑树的"3节点"中添加一个节点

这种情况即为插入的元素位置在红黑树3节点左或右，对应的结构就是一个黑节点的左边有个红节点，这样的结构中插入一个元素。如图，将66插入到3节点(42和37联合组成)中：

如果插入的节点大于根节点42，则将此节点作为根节点右孩子插入，并将两个孩子的颜色变为黑色，同时，将根节点变为红色。
如果插入的节点大小小于12，则先插入到37的左孩子中，并转化为以37为根，12为左孩子，42为右孩子的子树。这一步需要对42进行右旋转。

/*
    node                        x
   /    \        右旋转        /  \
  x     T2      --------->   y  node
 / \                            /  \
y  T1                          T1   T2
*/
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;
}

如果插入的节点大小介于37与42之间，例如插入节点40，首先将此节点插入到37的右孩子，之后对37进行左旋转，形成根节点为42，42左孩子为40，40左孩子为37的情形，此时适用于上一条情形：对42进行右旋转即可，最后颜色翻转。
对3节点插入一个元素，上述三种情况，可以用一张图表示：

红黑树插入元素

public class RBTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private class Node{
        public K key;
        public V val;
        public Node left, right;
        public boolean color;
        public Node(K key, V val){
            this.key = key;
            this.val = val;
            this.left = this.right = null;
            this.color = RED;  // 默认创建红色节点
        }
    }
    private Node root;
    private int size;
    public RBTree(){
        root = null;
        size = 0;
    }
    public int getSize(){ return size; }
    public boolean isEmpty(){ return size == 0; }
    public boolean isRed(Node node){
        if(node == null) return false;  // 空节点为黑色
        return true;
    }
    /*
        node                         x
       /    \         左旋转        /  \
      T1     x      --------->   node  T3
            / \                 /   \
           T2 T3               T1   T2
     */
    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;
    }

    /*
        node                        x
       /    \        右旋转        /  \
      x     T2      --------->   y  node
     / \                            /  \
    y  T1                          T1   T2
    */
    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 void flipColors(Node node){
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }
    // 向红黑树中添加元素(key, val)
    public void add(K key, V val){
        root = add(root, key, val);
        root.color = BLACK;  // 保持根节点元素为黑色
    }
    // 向以node为根的红黑树中插入元素(key, val)，递归算法
    // 返回插入新节点后的红黑树的根
    public Node add(Node node, K key, V val){
        if(node == null){
            size ++ ;
            return new Node(key, val);  // 默认插入红节点
        }
        if(key.compareTo(node.key) < 0)
            node.left = add(node.left, key, val);
        else if(key.compareTo(node.key) > 0)
            node.right = add(node.right, key, val);
        else node.val = val;
        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;
    }

    public static void main(String[] args) {
        RBTree<Integer, Integer> map = new RBTree<>();
        map.add(1, 2);
        map.add(2, 2);
        map.add(1, 2);
    }
}