数据结构-红黑树-java实现红黑树

什么是红黑树？

红黑树为一种特殊的二叉查找树，但相较于二叉查找树，红黑树自平衡的二叉查找树。

红黑树和二叉平衡树的区别
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。
所以红黑树有着比二叉平衡树更好的性能。

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。（指为空的叶子节点）
性质4：红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

红黑树示意图：

红黑树类

public class RBTree {
    private Object data;
    private RBTree left;
    private RBTree right;
    private RBTree parent;
    public static Boolean BLACK = false;
    public static Boolean RED = true;
    private boolean color = BLACK;

    public boolean isRedColor() {
        return color;
    }

    public void setColor(boolean color) {
        this.color = color;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public RBTree getLeft() {
        return left;
    }

    public void setLeft(RBTree left) {
        this.left = left;
    }

    public RBTree getRight() {
        return right;
    }

    public void setRight(RBTree right) {
        this.right = right;
    }

    public RBTree getParent() {
        return parent;
    }

    public void setParent(RBTree parent) {
        this.parent = parent;
    }

    public RBTree (){}
    public RBTree(Object data) {
        this.data = data;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

红黑树的基本操作

红黑树的基本操作是插入、删除、旋转和变色。在对红黑树进行添加或删除后，会用到旋转方法。
添加和删除和二叉排序树的添加删除方法一样，但是添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。这时通过旋转和变色，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

左旋、右旋和变色。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

public void left_rotate(RBTree x){
        RBTree y = x.getRight();
        x.setRight(y.getLeft());
        if(y.getLeft()!=null){
            y.getLeft().setParent(x);
        }
        y.setParent(x.getParent());
        if(x.getParent() == null){
            this.root = y;
        }else {
            if (x.getParent().getLeft()==x)
                x.getParent().setLeft(y);
            else
                x.getParent().setRight(y);
        }
        y.setLeft(x);
        x.setParent(y);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

public void right_rotate(RBTree y){
        RBTree x = y.getLeft();
        y.setLeft(x.getRight());
        if(x.getRight()!=null)
            x.getRight().setParent(y);
        x.setParent(y.getParent());
        if(y.getParent()==null){
            this.root = x;
        }else {
            if(y==y.getParent().getLeft())
                y.getParent().setLeft(x);
            else
                y.getParent().setRight(x);
        }
        x.setRight(y);
        y.setParent(x);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

变色：结点的颜色由红变黑或由黑变红。

这里和二叉平衡树的旋转方法相同

红黑树的插入

第一步: 将红黑树当作一颗二叉查找树，将节点插入。

第二步：将插入的节点着色为"红色"。

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

调整情况的分类

先不考虑key相同的情况

这样看来只有情况4相对复杂，但情景4.2和情景4.3只是方向反转而已，懂得了一种情景就能推出另外一种情景，由此也可以看出其实添加算法并不难理解。

情景1和3比较简单，直接来看情景4
首先进行情景4.1

处理前

处理：
将parent和uncel设置为黑色
将gparent设置为红色
把gparent设置为当前插入结点

处理后

gparent变为当前插入节点，循环往上判断。如果gparent的父结点是红色，根据性质4，此时红黑树已不平衡了，所以还需要把gparent当作新的插入结点，继续做插入操作自平衡处理，直到平衡为止。

情景4.2
叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点。
4.2.1插入节点时父节点的左节点

处理前

处理：
将parent设为黑色
将gparent设为红色
对gparent进行右旋

处理后

左边两个红结点，右边不存在，那么一边一个刚刚好，并且因为为红色，肯定不会破坏树的平衡。

4.2.2插入节点是父节点的右节点

处理前

处理：
对parent进行左旋
把parent设置为插入结点，得到情景4.2.1
进行情景4.2.1的处理

处理后

情景4.3为情景4.2的对称情况
叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点
（1）插入结点是其父结点的右子结点

（2）插入结点是其父结点的右子结点

以上就是插入操作的所有情况，最后末尾要加上把根节点设为黑色

插入

public void insert(Object data){   //node为插入节点
        RBTree node = new RBTree(data);
        RBTree x = this.root;
        RBTree y = null;
        Comparable curNode =null;
        while(x!=null){
            y = x;
            curNode = (Comparable) x.getData();
            if(curNode.compareTo(data)==1)
                x = x.getLeft();
            else 
                x = x.getRight();
        }
        
        node.setParent(y);
        if(y != null){
            Comparable yy = (Comparable) y.getData();
            if(yy.compareTo(data)==1)
                y.setLeft(node);
            else 
                y.setRight(node);
        }else 
            this.root = node;
        node.setColor(RBTree.RED);
        insertFixUp(node);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

插入修复

private void insertFixUp(RBTree node) {
        RBTree parent,gparent;
        parent = parentOf(node);
        while(parent!=null&&parent.isRedColor()){
            gparent = parentOf(parent);
            if(parent == gparent.getLeft()){ //若“父节点”是“祖父节点的左孩子”
                RBTree uncle = gparent.getRight();
                if((uncle!=null)&&uncle.isRedColor()){  //叔叔节点是红色
                    uncle.setColor(RBTree.BLACK);
                    parent.setColor(RBTree.BLACK);
                    gparent.setColor(RBTree.RED);
                    node = gparent;
                    parent = parentOf(node);
                    continue;
                }
                if (parent.getRight() == node){    //叔叔节点是黑色且当前节点是右孩子
                    RBTree temp;
                    left_rotate(parent);
                    temp = parent;
                    parent = node;
                    node = temp;
                }
                parent.setColor(RBTree.BLACK);    //叔叔节点是黑色且当前节点是左孩子
                gparent.setColor(RBTree.RED);
                right_rotate(gparent);
                parent = parentOf(node);
            }else{  //父节点是爷节点的右孩子
                RBTree uncle = gparent.getLeft();
                if((uncle!=null)&&uncle.isRedColor()){  //叔叔节点是红色
                    gparent.setColor(RBTree.RED);
                    uncle.setColor(RBTree.BLACK);
                    parent.setColor(RBTree.BLACK);
                    node = gparent;
                    parent = parentOf(node) ;
                    continue ;
                }
                if (parent.getLeft() == node){    //叔叔节点是黑色且当前节点是左孩子
                    RBTree temp;
                    right_rotate(parent);
                    temp = parent;
                    parent = node;
                    node = temp;
                }
                parent.setColor(RBTree.BLACK);    //叔叔节点是黑色且当前节点是左孩子
                gparent.setColor(RBTree.RED);
                left_rotate(gparent);
                parent = parentOf(node);
            }
        }
        this.root.setColor(RBTree.BLACK);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

红黑树的删除

将红黑树内的某一个节点删除。需要执行的操作依次是：

第一步：将红黑树当作一颗二叉查找树，将节点删除。

这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。

通过①②③三步找到删除节点，如果有替代节点就将替代节点当作删除节点

第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。

调整前准备

第一步中如果有替代节点，则将替代节点当作删除的节点（以下统称为删除节点）。

1、如果删除节点为红色则不需要调整。

如图删除10或者70时，删除节点均为红色（70时将80作为替代节点删除）此时不需要进行调整。

2、删除节点为黑色
设置一个child，和parent节点用于记录删除情况。child为删除节点的一个右孩子（它一定没有左孩子），如果没有则为空。parent为删除节点的parent。

举例子说明child和parent节点。

情景1

这时可以看到删除节点为35，且两个孩子节点都存在，找到后继节点为36，这时就相当于删除36节点，此时的child为38，parent为39。

当然还有一种常见情况38为空节点，此时child为null

情景2

要删除55，55没有子节点，所以此时直接删除55。child为null，parent为39。

情景3

此时寻找替代节点36，相当于删除36，此时child为40，parent为20

情景4

此时相当于删除了60节点，而60节点为红色，所以不用调整。

以上基本包含了删除后如何找到child和parent节点。
总结一下：①删除节点有两个孩子节点，此时找到后继结点，相当于删除了后继节点。此时child为替代节点的孩子节点，parent为替代节点的父节点。②当删除节点有一个孩子时将这个孩子当作后继结点，并相当于删除了后继节点。同样child为替代节点的孩子节点，parent为替代节点的父节点。③当删除节点没有孩子节点时child为null，parent为删除节点的父节点；

红黑树的删除
下面为将红黑树当作二叉搜索树，将节点删除，并记录child和parent节点

public void remove(Object data){
        RBTree x = this.root;
        RBTree node = null;
        while(x!=null){           //找到删除节点
            Comparable curNode = (Comparable) x.getData();
            if(curNode.compareTo(data)==1)
                x=x.getLeft();
            else if(curNode.compareTo(data)==-1)
                x=x.getRight();
            else{
                node = x;
                break;
            }

        }
        if (node == null){
            System.out.println("没有此节点");
            return;
        }

        RBTree child, parent;
        boolean color;
        if(node.getLeft()!=null&&node.getRight()!=null){//找到一个比这个节点大1位的节点
            RBTree replace = node;
            replace = replace.getRight();
            while(replace.getLeft()!=null)    //找到取代节点  ，右子树的最深左子树
                replace = replace.getLeft();

            if (parentOf(node)!=null){     //如果删除节点的父节点位空说明此节点为根节点
                if(parentOf(node).getLeft()==node)
                    parentOf(node).setLeft(replace);
                else
                    parentOf(node).setRight(replace);
            }else
                this.root = replace;

            child = replace.getRight();          //替代节点的右孩子  它一定没有左孩子
            parent = parentOf(replace);          //替代节点的父节点
            color = replace.isRedColor();        //替代节点的颜色
            if(parent==node)     //如果删除节点为替代节点的父节点
                parent=replace;
            else {
                if (child!=null)         //替代节点有孩子  将此孩子挂在替代节点的父节点上
                    child.setParent(parent);
                parent.setLeft(child);
                replace.setRight(node.getRight());  //删除节点的右孩子设为替代节点的右孩子
                node.getRight().setParent(replace);
            }

            replace.setParent(node.getParent());   //替代节点输入删除节点的信息
            replace.setColor(node.isRedColor());
            replace.setLeft(node.getLeft());
            node.getLeft().setParent(replace);   //删除节点的左孩子设为替代节点的左孩子
            if(color == RBTree.BLACK)           //当替代节点的颜色为黑是需要修复
                removeFixUp(child,parent);
            node = null;
            return;
        }
        if (node.getLeft()!=null)       //说明删除节点左右孩子有可能不存在
            child = node.getLeft();
        else
            child = node.getRight();
        parent = node.getParent();
        color = node.isRedColor();
        if(child!=null)                //左右孩子有一个存在
            child.setParent(parent);

        if (parent!=null){
            if (parent.getLeft() == node)
                parent.setLeft(child);
            else
                parent.setRight(child);
        }else
            this.root = child;

        if (color == RBTree.BLACK)         //当删除节点颜色为黑色时需要修复
            removeFixUp(child,parent);
        node = null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

终于快完成了QAQ，以下时remove后的调整

通过child和parent节点自底向上调整红黑树

情况1、child节点是红色的或者child是根节点
处理方法：将child变成黑色，结束

情况2、child是黑色的（null也是黑色）而且child不是root
这时分两种情况。2.1child为parent的左孩子，2.2child为parent的右孩子。其实只需要知道2.1的情况即可，2.2为2.1的镜像，调整方法的一样的。
2.1child为parent的左孩子
首先要取得parent的右节点，即child的兄弟节点。
2.1.1兄弟节点other为红色的
（1）兄弟节点设为黑色，把parent节点设为红色。
（2）左转parent。
（3）兄弟节点变为parent节点的右孩子
（4）进行2.1.2、2.1.3、2.1.4的判断
示例

2.1.2other为黑色，而且other的两个孩子也是黑色
处理：
（1）此时把other设为红色
（2）child节点指向parent节点
（3）parent节点指向child的父节点
（4）返回情况1继续判断

2.1.3other为黑色，ohter右孩子为红色，左孩子任意
处理：
（1）other节点设为parent节点的颜色，parent节点设为黑色，other右节点设为黑色，左转parent节点
（2）child指向根节点，调整完成
示例

调整结果

2.1.4other为黑色，other左孩子为红色，右孩子为黑色
处理：
（1）将other的左节点谁为黑色，将other节点设为红色
（2）右转other节点，other节点变为other节点的左节点
（3）此时的得到的图形和情况2.1.3一样，之后只需要和2.1.3一样调整就行了

示例
最终

最后还需要将child节点设为黑色

2.2child为parent节点的右节点
与2.1相同，只不过方向是反的

附上一张大佬的总结图。（删除算法是根据我自己的思路进行的，所以情景编号不一样）

这图总结的非常完整，包含了所有的删除情况。

移除后修正代码

private void removeFixUp(RBTree child, RBTree parent) {
        RBTree other;  //child的兄弟节点
        while((child==null||!child.isRedColor())&&(child!=this.root)){
            if (parent.getLeft() == child){     //child为parent的左孩子
                other = parent.getRight();
                if (other!=null&&other.isRedColor()){  // case1 child的兄弟是红色
                    other.setColor(RBTree.BLACK);
                    parent.setColor(RBTree.RED);
                    left_rotate(parent);
                    other  = parent.getRight();
                }

                if ((other.getLeft()==null||!other.getLeft().isRedColor())
                    &&(other.getRight()==null||!other.getRight().isRedColor())){
                    // case2 child的兄弟是黑色，且兄弟的两个孩子也是黑色
                    other.setColor(RBTree.RED);
                    child = parent;
                    parent = parentOf(child);
                }else {
                    if (other.getRight()==null||!other.getRight().isRedColor()){
                        //case3 child的兄弟是黑色，且兄弟的左孩子是红色，右孩子是黑色
                        other.getLeft().setColor(RBTree.BLACK);
                        other.setColor(RBTree.RED);
                        right_rotate(other);
                        other = parent.getRight();
                    }
                    //case4  x的兄弟是黑色，且兄弟的右孩子是红色，左孩子是任意颜色

                    other.setColor(parent.isRedColor());
                    parent.setColor(RBTree.BLACK);
                    if (other.getRight()!=null)
                        other.getRight().setColor(RBTree.BLACK);
                    left_rotate(parent);
                    child = this.root;
                    break;
                }
            }else {   //child为parent的右孩子
                other = parent.getLeft();
                if (other!=null&&other.isRedColor()){  //case1 child的兄弟是红色的
                    other.setColor(RBTree.BLACK);
                    parent.setColor(RBTree.RED);
                    right_rotate(parent);
                    other = parent.getLeft();
                }
                if ((other.getLeft()==null||!other.getLeft().isRedColor())
                    &&(other.getRight()==null||!other.getRight().isRedColor())){
                    //case2 child的兄弟是黑色的，且兄弟的两个孩子也是黑色的
                    other.setColor(RBTree.RED);
                    child = parent;
                    parent = parentOf(child);
                }else {
                    if (other.getLeft()==null||!other.getLeft().isRedColor()){
                        //case3 child的兄弟是黑色，且兄弟的左孩子为黑色，右孩子为红色
                        other.getRight().setColor(RBTree.BLACK);
                        other.setColor(RBTree.RED);
                        left_rotate(other);
                        other = parent.getLeft();
                    }

                    //case4 x的兄弟是黑色且兄弟的左孩子是红色，右孩子任意
                    other.setColor(parent.isRedColor());
                    parent.setColor(RBTree.BLACK);
                    if (other.getLeft()!=null)
                        other.getLeft().setColor(RBTree.BLACK);
                    right_rotate(parent);
                    child = this.root;
                    break;
                }
            }
        }
        if (child!=null)
            child.setColor(RBTree.BLACK);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

以上就是全部的红黑树的操作

红黑树的测试

这里写一个中序遍历

public void inorder(RBTree node){
        if(node == null) return;
        inorder(node.getLeft());
        System.out.println(node.getData()+":"+node.isRedColor()+":"+(node.getParent()==null?
                null:node.getParent().getData()));
        inorder(node.getRight());
    }
1
2
3
4
5
6
7

随机产生100个0-10000的数，添加到红黑树中，然后将添加顺序打乱，即随机删除25个节点。再进行遍历

public static void main(String args[]){
        RedAndBlackTree rbt = new RedAndBlackTree();
        Random r = new Random();
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i=0;i<100;i++){
            list.add(r.nextInt(10001));
            rbt.insert(list.get(i));
        }
        Collections.shuffle(list);
        for (int i = 0;i<25;i++){
            rbt.remove(list.get(i));
        }
        rbt.inorder(rbt.getRoot());
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

部分输出结果，节点：颜色：父节点。

完整代码
https://github.com/yhq915540781/javaPra/blob/master/src/Algorithm/dataStructure/RedAndBlackTree.java

参考文章
https://www.cnblogs.com/skywang12345/p/3624343.html
https://www.jianshu.com/p/e136ec79235c