红黑二叉树

在一棵含有N个结点的树种，我们希望树高为~lgN，这样我们就能保证所有查找都能在~lgN次比较内结束，就和二分查找一样。但是在动态插入种保证树的完美平衡代价太高了，于是引入了一种新的查找结构——红黑树。同时为了更好的理解红黑树，在讲解红黑树之前先了解另一种树结构2-3查找树。

1. 2-3查找树

2-3查找树有两种结点，一个键两个链接的结点称为2-结点，两个键三个链接的结点称为3-结点。2-结点和3-结点中的每条链接都对应着其中保存的键所分割的一个区间。一棵完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的，如下图所示。2-3查找树的查找过程与二叉搜索树类似，在此不再赘述。

1.1 插入

在插入操作时，我们始终要记住一点，为了保证2-3查找树的完美平衡性，要避免因插入操作而导致的子树高度的增长。

如果需要向2-结点插入新键，为了保持2-3查找树的完美平衡性，我们不会像二叉查找树一样，将节点挂在树的底部，而是选择将2-结点扩展成3-结点。

如果我们需要向3-结点中插入新键，我们先暂时使其扩展成一个4-结点，然后再让其中间的结点变成父节点，生成两个链接分别与较小值和较大值相连。这一操作使得子树高度+1，与我们理念相悖，为此，我们需要将该子树融合到它的父节点中。

如下左图所示，如果一个临时4-结点的父节点是一个2-结点，那么只需要把E结点插入到其父节点使其变成一个3-结点即可。如下右图所示，如果一个临时4-结点的父节点是一个3-结点，那么将其父节点变成一个临时4-结点继续向上融合，直到找到一个2-结点。

如果从插入结点到根节点全都是3-结点，根节点变成一个临时4-结点，此时我们将根节点分裂成三个结点构成的二叉树，此时2-3查找树实现了高度+1,。由此可见，2-3查找树的生长方向是根节点的方向。

2.红黑二叉查找树

对于2-3查找树，尽管我们可以用不同的数据类型表示2-结点和3-结点并写出所需代码，但是实际实现起来并不方便，为此我们用另一种方式实现2-3查找树——红黑二叉查找树。

红黑二叉查找树基本思想是用标准的二叉查找树和一些额外的信息（用来表示3-结点）来表示2-3树。我们将数中的连接分为两种类型：我们用一条左斜的红色连接相连的两个2-结点构成一个3-结点，用黑连接表示2-3树中的普通链接。一棵红黑二叉查找树和2-3树是一一对应的。

每个结点都有一个指向它的链接，我们将该链接的颜色保存在结点的一个布尔类型的成员变量color中，Node的数据结构如下所示。

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

private class Node
{
    Key key;
    Value value;
    Node left,right;
    int N;
    boolean color;
    
    Node(Key key, Value val, int N, boolean color)
    {
        this.key =key;
        this.val =val;
        this.N = N;
        this.color=color;
    }
}

private boolean isRed(Node x)

2.1 插入

切记，插入过程中都是用红链连接新键。为了保证红黑树只存在左斜红链，后续好需要做些调整，但这是后续步骤。

2.1.1 旋转操作

所谓的后续操作，都是旋转操作的组合，旋转操作有左旋和右旋之分。不管是左旋还是右旋，都会返回重置后的父节点。

左旋

Node rotateLeft(Node h){
    Node x=h.right;
    h.right=x.left;
    x.left=h;
    x.color=h.color;
    h.color=RED;
    x.N=h.N;
    h.N=1+size(h.left)+size(h.right);
    return x;
}

右旋

Node rotateRight(Node h){
    Node x=h.left;
    h.left=x.right;
    x.right=h;
    x.color=h.color;
    h.color=RED;
    x.N=h.N;
    h.N=1+size(h.left)+size(h.right);
    return x;
}

2.1.2 向2-结点插入新键

回忆2-3查找树插入过程，在2-3查找树中向2-结点插入元素，2-结点变成一个3-结点，同理，如果待插入的元素比2-结点元素小，则原2-结点产生一个左斜红链链接新元素；如果待插入元素比2-结点大，则原2-结点产生一个右斜红链链接，链接新元素。但是在红黑二叉树中，不允许有右斜红链接的存在，所以我们需要对其进行一步操作，左旋（具体实现稍后解释），如图所示。

2.1.3 向3-结点插入新键

在2-3树中向3-结点插入元素，3-结点先变成一个临时的4-结点，然后分裂成一个棵二叉树，该二叉树的根节点与原3-结点的父节点进行融合。在红黑树中的插入过程也要实现这一过程。我们先不考虑融合这一过程，只讨论如何将4-结点变成一个棵二叉树。我们将其分为3种情况：

新键最大：用一根右斜红链直接与新键链接
新键最小：用一根左斜红链连接到最左边的结点上，此时出现两条连续的左斜红链，只需对上层红链进行右旋处理
新键介于两者之间：见图，先左旋，再右旋

接下来我们再来考虑如何实现2-3树中的“融合”这一操作。首先，先生成的二叉树左右两个链接一定是黑色的；同时，为了将新二叉树的中结点送入父节点，我们需要将中结点到父节点的连接变红，实现过程由flipColors（）完成（flipColors在后面还有其他作用，这里给出最终形式）。这意味着在父节点中继续插入一个新键，我们继续把它当做在一结点中插入新键操作，可见这是一个递归操作。

void flipColors(Node h){
    h.color=!h.color;
    h.left.color=!h.left.color;
    h.right.color=!h.right.color;
}

将以上总结起来考虑，在沿着插入点到根节点的路径向上移动时在所经过的每个结点中顺序完成以下操作，我们就能完成插入操作：

如果右子结点是红色的而左子结点是黑色的，进行左旋转
如果左子结点是红色的且它的左子节点也是红色，进行右旋转
如果左右子结点均为红色，进行颜色转换（红色结点变黑色，黑色边红色）

实现如下：

public class RedBlackBST<Key extends Comparable<Key>, Value>{
    private Node root;
    private class Node; //语法不严谨，表示定义一个内部类
    
    private boolean isRed(Node h);
    private Node rotateLeft(Node h);
    private Node rotateRight(Node h);
    private void flipColors(Node h);
    
    private int size();
    
    public void put(Key key,Value val){
        root=put(root,key,val);
        root.color=BLACK;
    }
    
    private Node put(Node h, Key key, Value val){
        if(h == null)
            return new Node(key, val, 1, RED);
        
        int cmp=key.compareTo(h.key);
        if(cmp<0)
            h.left=put(h.left,key,val);
        else if(cmp>0)
            h.right=put(h.right,key,val);
        else
            h.val=val;
        
        if(isRed(h.right)&&(!isRed(h.left)))
            h=rotateLeft(h);
        if(isRed(h.left)&&(isRed(h.left.left)))
            h=rotateRight(h);
        if(isRed(h.left)&&isRed(h.right))
            flipColors(h);
        
        h.N=size(h.left)+size(h.right)+1;
        return h;
    }
}

2.2 删除

删除操作相比插入操作还要复杂，我们可以思考一下，如果我们要删除的结点是一个2-结点，那么删除这个结点的时候就会破坏红黑树的平衡性。为了避免这一情况，我们需要在自顶向下寻找待删除的结点时，将2-结点进行一定转换，变成3-结点或者4-结点，这样就可以保证我们需要删除的结点在一个3-结点中；然后，我们还需要自下向上，将我们产生的临时4-结点分解。

在自顶向下的过程中，如何对2-结点进行变换呢？这里分两种情况：

直系兄弟结点不是2-结点，通过父节点从兄弟结点传递一个结点到本结点（如下图，c被移动到了父节点，父节点中的b移动到了当前结点），此时变成一个3-结点
直系兄弟也是一个2-结点，则与父节点和直系兄弟结点一同生成一个4-结点（问：只从父节点借一个结点形成一个3-结点行不行？答：不行，如下图，只借用b，c往哪里挂？）

删除最小键

private Node moveRedLeft(Node h){
	//当前节点的左右子节点都是2-节点，左右节点需要从父节点中借一个节点
    //如果该节点的右节点的左节点是红色节点，说明兄弟节点不是2-节点，可以从兄弟节点中借一个
        moveflipColors(h);     // 从父节点中借一个
    
        if(isRed(h.right.left)){    // 判断兄弟节点，如果是红节点，从兄弟节点中借一个
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
            moveflipColors(h);  //  在从兄弟节点借了一个以后，我们就需要还一个节点给父节点了，因为一开始从父节点那里借了一个(其实是结点的传递)
        }
        return h;
    }
    
    public void deleteMin(){
        if(!isRed(root.left) && !isRed(root.right)){
            root.color = Red;   //考虑根节点+左右分支都是黑链这一情况
            
        }
        root = deleteMin(root);
        root.color = Black;  // 借完以后，我们将根节点的颜色复原
        
    }
    
    private Node deleteMin(Node x){
        if(x.left == null) return null;
        if(!isRed(x.left) && !isRed(x.left.left))    // 判断x的左节点是不是2-节点
            
            x = moveRedLeft(x);
        x.left = deleteMin(x.left);
        return balance(x);  //   解除临时组成的4-节点
        
    }
    
    private Node balance(Node h){
        if (isRed(h.right) && !isRed(h.left)) h=rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h=rotateRight(h);
        if (isRed(h.left) && isRed(h.right))    flipColors(h);
        h.total = size(h.left)+size(h.right)+1;
        return h;
    }

删除最大键

  private Node moveRedRight(Node h){
        moveflipColors(h);
        if(isRed(h.left.left)){         // 在这里对于兄弟节点的判断都是.left，因为红色节点只会出现在左边  
            h=rotateRight(h);
            moveflipColors(h);
        }
        return h;
    }
    public void deleteMax(){
        if(!isRed(root.left) && isRed(root.right)){
            root.color = Red;
        }
        root = deleteMax(root);
        root.color = Black;
    }
    
    private Node deleteMax(Node h){
        if(isRed(h.left)){             
        /* 考虑下面这种情况，如果没有这一步右旋会发生什么？ （当需要从父结点借结点时，会被父结点“拉上去”而导致不平衡） 
         *          5,6
         *      1,2     9       
        */                                         
            h = rotateRight(h);
        }
        if(h.right == null){
            return null;
        }
        if(!isRed(h.right) && !isRed(h.right.left)){
            h = moveRedRight(h);
        }
        h.right = deleteMax(h.right);
        return balance(h);
    }

删除

 public void delete(int key){
        if(!isRed(root.left)&& !isRed(root.right)){
            root.color = Red;
        }
        root = delete(root,key);
        root.color = Black;
 } 
    
    private Node delete(Node h, int key){
        if(key<h.key){          // 当目标键小于当前键的时候，我们做类似于寻找最小是的操作，向树左边移动，合并父子结点来消除2-结点
            if(h.left == null){
                return null;
            }
            if(isRed(h.left) && !isRed(h.left.left)){
                h = moveRedLeft(h);
            }
            h.left = delete(h.left,key);
        }else{  // 当目标键大于当前键的时候，我们向右移动，并做与deleteMax相同的操作，如果相同的话，我们使用和二叉树的删除一样的操作，获取当前键的右子树的最小健，然后交换，并将目标键删除
            if(isRed(h.left)){
                h = rotateRight(h);
            }
            if(key.compareTo(h.key) == h.key && h.right == null){    // 找到目标
                
                return null;
            }
            if(!isRed(h.right) && isRed(h.right.left)){
                h = moveRedRight(h);
            }
            if(key == h.key){
                h.val = get(h.right,min(h.right).key);
                h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            }
            else h.right = delete(h.right,key);
        }
        return balance(h);
    }

3. 总结

红黑树几乎是完全平衡的，但是我们在查找的时候完全没有用到颜色这个性质，那么所谓的红黑到底有什么作用？颜色是起到动态调整的作用的，在二叉树中最极端的情况是以有序的方式插入元素，，最后得到的树高就等于插入的元素个数N，但是这在红黑树中不会发生。一棵大小为N的红黑树的高度不会找过2lgN，简单地推理一下，红黑树的最坏情况是它所对应的2-3树中构成最左边的路径结点全部都是3-结点，该长度为只包含2-结点的路径长度（~lgN）的2倍。