红-黑 树的实现

从零开始自己实现一个红黑树

构造方法

红黑树的构造方法部分与二叉树相差不大，对于每一个节点额外用了一个 color 变量来表示节点的颜色。特别地，我们将新节点永远设置成红色节点，这样做的目的是为了在与2节点，三节点融合时标志出来，后续操作再根据实际情况设置颜色。

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 value;
        public Node left,right;
        public boolean color;

        public Node(K key, V value){
            this.key=key;
            this.value=value;
            left=null;
            right=null;
            color=RED;//2-3树插入一个节点,永远先去和叶子节点去融合
        }

        public Node(){
            this.key=null;
            this.value=null;
            left=null;
            right=null;
        }
    }

    private Node root;
    private  int size;

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

其他常用方法

红黑树额外多了一个 getColor 方法用来返回

private boolean getColor(Node node){
    if (node==null){
        return BLACK;
    }
    return  node.color;
}

下面几个方法与一般的二分搜索树一样，不做解释

public boolean contains(K key) {
    return contains(root ,key);
}

private boolean contains(Node node,K key){
    if (node==null){
        return false;
    }
    if (key.compareTo(node.key)==0){
        return true;
    }else if (key.compareTo(node.key)<0){
        return contains(node.left,key);
    }else {
        return contains(node.right,key);
    }
}


public V get(K key) {
    Node retNode=getNode(root,key);
    if (retNode!=null){
        return retNode.value;
    }else {
        return null;
        }
}

private Node getNode(Node node,K key) {
    if (node==null){
        return null;
    }
    if (key.compareTo(node.key)==0){
        return node;
    }else if (key.compareTo(node.key)<0){
        return getNode(node.left,key);
    }else {
        return getNode(node.right,key);
    }
}


public void set(K key, V newValue) {
    Node setNode=getNode(root,key);
    if (setNode!=null){
        setNode.value=newValue;
    }else{
        throw new IllegalArgumentException(key + "doesn't exist!");
    }
}


public int getSize() {
    return size;
}


public boolean isEmpty() {
    return size==0;
}

向 红-黑 树 中增加节点

上一节说过 红-黑 树 本质上就是 2-3 树的二叉树表现形式。向红黑树中增加节点本质上就是向2-3树中增加节点。那么根据新节点的插入位置可以分为以下5中情况：

1. 在二节点的左侧插入

2. 在二节点的右侧插入

3. 在三节点左侧插入

4. 在三节点中间插入

5. 在三节点右侧插入

在二节点左侧插入

这种情况最简单，直接与二节点进行合并形成一个三节点，在红黑树中只需要将新节点设置成红色即可。

特别的是，这里的 “37” 节点仍有左右子树，这是因为 “37” 节点可能是新加入的节点，也可能是下面节点向上进行融合的节点。这是不失一般性地表示。

在二节点的右侧插入

在二节点的右侧插入，需要与二节点融合成一个三节点。根据 红颜色 的节点定义，红节点是三节点左侧的节点，且红色节点是 2-3 树中的3节点的右边节点的左孩子。为此，需要对三节点的左侧节点进行左旋操作，然后再更改三节点中左右两个节点的颜色，将左侧设置为红色，将右侧设置为黑色。整个过程如下图所示:

特别的是，这里的 “42” 节点仍有左右子树，这是因为 “42” 节点可能是新加入的节点，也可能是下面节点向上进行融合的节点。这是不失一般性地表示。

左旋操作

private Node leftRotate(Node node){
        
    Node x=node.right;
    Node T1=node.left;
    Node T2=x.left;
    Node T3=x.right;

    x.left=node;
    node.right=T2;

    return x;
 }

在三节点的左侧插入

在三节点的左侧插入，融合成一个四节点。四节点的中间节点与两侧节点分离，两侧节点形成新的二节点，中间节点继续向上，与上面一层的节点进行融合。为此需要将中间节点设置为红色，两侧节点设置为黑色。在对应的红黑树中，需要对四节点的右侧节点进行右旋，然后进行颜色变换，将两侧节点设置为黑色，中间节点设置为红色，继续与上一层的节点进行融合。整个过程如下图所示:

右旋操作

private Node rightRotate(Node node){
    Node x=node.left;
    Node T1=x.right;
    Node T2=node.right;

    x.right=node;
    node.left=T1;

    return x;
}

在三节点中间插入

在三节点中间插入新节点，融合成一个四节点。四节点的中间节点与两侧节点分离，两侧节点形成新的二节点，中间节点继续向上，与上面一层的节点进行融合。为此需要将中间节点设置为红色，两侧节点设置为黑色。在对应的红黑树中，需要对四节点的左侧节点进行左旋，再对原四节点的右侧节点进行右旋。然后进行颜色变换，将两侧节点设置为黑色，中间节点设置为红色，继续与上一层的节点进行融合。整个过程如下图所示:

在三节点右侧插入

在三节点中间插入新节点，融合成一个四节点。四节点的中间节点与两侧节点分离，两侧节点形成新的二节点，中间节点继续向上，与上面一层的节点进行融合。为此需要将中间节点设置为红色，两侧节点设置为黑色。在红黑树中，直接进行颜色变换即可，无需额外操作。整个过程如下图所示:

至此增加节点的所有情况都已经分析完毕，我们将其整合到一起就是这样：

public void add(K key, V value) {
    root=add(root, key,value);
    root.color=BLACK;
}

//向以node为根的二分搜索树中加入e
//并且返回node
private Node add(Node node, K key, V value){
    if (node==null){
        size++;
        return new Node(key,value);
    }


    if (key.compareTo(node.key)==0){
        node.value=value;
    }else if (key.compareTo(node.key)<0 ){
        node.left=add(node.left,key,value);
    }else {
        node.right=add(node.right,key,value);
    }

    //node字树改变了,需要维护平衡

    //2节点左侧插入
    if (getColor(node.left)==RED  ){
            return node;
    }

    //2节点右侧 插入
    if (getColor(node)==BLACK && getColor(node.right)==RED){
        node=leftRotate(node);
        node.color=BLACK;
        node.left.color=BLACK;
    }

    //3节点左侧插入
    if (getColor(node.left)==RED  && getColor(node.left.left)==RED  ){
        node=rightRotate(node);
        //改变颜色
        node.color=RED;
        node.left.color=BLACK;
        node.right.color=BLACK;
        return node;
    }

    //3节点中间插入
    if (getColor(node)==BLACK && getColor(node.left)==RED && getColor(node.left.right)==RED){
        node.left=leftRotate(node.left);
        node=rightRotate(node);
        node.left.color=BLACK;
        node.right.color=BLACK;
        node.color= RED;
        return node;
    }

    //3节点右侧插入
    if (getColor(node)==BLACK && getColor(node.left)==RED && getColor(node.right)==RED){
        node.color=RED;
        node.left.color=BLACK;
        node.right.color=BLACK;
        return node;
    }

    //其他情况,说明当前节点的子树没有节点向上融合,直接return
    return  node;
}

我们可以看出，与二分搜索树相比，红黑树主要多出了23到63行代码， 用于维护树的黑平衡。特别的是，每当插入新节点时，都需要逐层检查，看下层是否有新节点对与当层节点进行融合。为此，我们在第26，31，38，48，58行进行检查，查看是否需要进行维护黑平衡。