红黑树实现

概述

红黑树也是一种自平衡的二叉树。
相比于AVL数，红黑树插入删除的效率跟高，因为其插入和删除是需要的旋转的次数更少。

特性

1.所有的节点都有两种颜色红色，黑色
2.所有的null节点视为黑色
3.红色节点之间不能相邻
4.根节点是黑色
5.从根节点到任何一个叶子节点，路径中的黑色节点数一样

实现

节点

这里我们需要一个枚举类，用于表示节点的颜色
同时我们在这里的节点中提供了三个之后代码中经常需要用到的方法。
分别是判断一个节点是否是左孩子，找到一个节点的兄弟节点，找到一个节点的叔叔节点

enum Color {
        RED, BLACK;
    }
private static class Node {
        int key;
        Object value;
        Node left;
        Node right;
        Node parent;
        Color color = Color.RED;

        public Node() {
        }

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        //判断是否是左孩子
        boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        //找叔叔
        Node uncle() {
            //有爷爷才有叔叔
            if (parent == null || parent.parent == null) {
                return null;
            }
            if (parent.isLeftChild()) {
                return parent.parent.right;
            } else {
                return parent.parent.left;
            }
        }

        //找兄弟
        Node sibling() {
            if (parent == null) {
                return null;
            }
            if (this.isLeftChild()) {
                return parent.right;
            } else {
                return parent.left;
            }
        }

    }
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

判断节点颜色

//判断节点颜色
    boolean isRed(Node node) {
        return node != null && node.color == Color.RED;
    }

    boolean isBlack(Node node) {
        return !isRed(node);
    }
1
2
3
4
5
6
7
8

左旋，右旋方法

要注意，在这里的旋转的同时，我们不仅要维护孩子的关系，还要维护和父节点的关系

//右旋 处理parent  旋转后新根的父子关系
    private void rightRotate(Node pink) {
        Node parent = pink.parent;
        Node yellow = pink.left;
        Node green = yellow.right;
        if (green != null) {
            green.parent = pink;
        }
        yellow.right = pink;
        yellow.parent = parent;
        pink.left = green;
        pink.parent = yellow;
        if (parent == null) {
            root = yellow;
        } else if (parent.left == pink) {
            parent.left = yellow;
        } else {
            parent.right = yellow;
        }
    }

    //左旋
    private void leftRotate(Node pink) {
        Node parent = pink.parent;
        Node yellow = pink.right;
        Node green = yellow.left;
        if (green != null) {
            green.parent = pink;
        }
        yellow.left = pink;
        yellow.parent = parent;
        pink.right = green;
        pink.parent = yellow;
        if (parent == null) {
            root = yellow;
        } else if (parent.left == pink) {
            parent.left = yellow;
        } else {
            parent.right = yellow;
        }
    }
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

新增节点

因为新增节点默认为红色节点，因此，在新增是产生红色相邻的不平衡情况

这里将所有调整颜色和旋转的代码放在fixRedRed方法里

case1:插入节点是根节点，直接将根节点变黑
case2:插入节点的父节点如果为黑色，直接插入就可以

插入节点红红相邻
case3:插入节点的叔叔为红色
把父亲和叔叔都变成黑色，将祖父变成红色
祖父变红又可能继续触发红红相邻，继续递归调用处理方法就可以了

case4:叔叔为黑色
1.父亲为左孩子，插入节点也是左孩子，此时为LL不平衡
首先把父亲变为黑色，之后为了是黑色数量平衡，还需要将祖父变成红色
但是，这样的叔叔节点这条路就回少一个黑色，这是我们只要把祖父挂在父亲的右边，这样相当于增加了父亲这个黑色的节点，能够保持黑色节点数量的品很。相当于我们需要对祖父节点进行一个右旋
2.父亲为左孩子，插入节点是右孩子，此时为LR不平衡
如果右孩子为红色，还是之前的调整的方式的话，相当于会把插入节点挂在祖父节点左边，还是红红相邻的情况，因此我们应该先对父亲节点进行一个左旋，这样就能变成1的情况了。
3.父亲为右孩子，插入节点是右孩子，此时为RR不平衡
对祖父进行一个左旋即可
4.父亲为右孩子，插入节点是左孩子，此时为RL不平衡
先对父亲右旋，在对祖父左旋

 public void put(int key, Object value) {
        Node p = root;
        Node parent = null;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (key > p.key) {
                p = p.right;
            } else {
                p.value = value;
                return;
            }
        }
        Node inserted = new Node(key, value);
        if (parent == null) {
            root = inserted;
        } else if (key < parent.key) {
            parent.left = inserted;
            inserted.parent = parent;
        } else {
            parent.right = inserted;
            inserted.parent = parent;
        }
        fixRedRed(inserted);
    }


    private void fixRedRed(Node x) {
        //case1:插入节点是根节点
        if (x == root) {
            x.color = Color.BLACK;
            return;
        }
        //case2:插入节点父亲是黑色
        if (isBlack(x.parent)) {
            return;
        }
        /*case3:红红相邻，叔叔为红时
         * 需要将父亲，叔叔变黑，祖父变红，然后对祖父进行递归操作
         * */
        Node parent = x.parent;
        Node uncle = x.uncle();
        Node grandparent = parent.parent;
        if (isRed(uncle)) {
            parent.color = Color.BLACK;
            uncle.color = Color.BLACK;
            grandparent.color = Color.RED;
            fixRedRed(grandparent);
            return;
        }


        if (parent.isLeftChild() && x.isLeftChild()) {//case4:左左不平衡
            parent.color = Color.BLACK;
            grandparent.color = Color.RED;
            rightRotate(grandparent);
        } else if (parent.isLeftChild()) {//case4:左右不平衡
            leftRotate(parent);
            x.color = Color.BLACK;
            grandparent.color = Color.RED;
            rightRotate(grandparent);
        } else if (!x.isLeftChild()) {//case4:右右不平衡
            parent.color = Color.BLACK;
            grandparent.color = Color.RED;
            leftRotate(grandparent);
        } else {
            rightRotate(parent);
            x.color = Color.BLACK;
            parent.color = Color.BLACK;
            leftRotate(grandparent);
        }
    }
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

删除节点

首先，我们先写出，两个要用到的方法，找到要删除的节点，找到替换删除节点的节点

找删除节点很简单一个迭代
找替换节点就需要分类讨论了，如果删除节点没有孩子，那么返回空；如果有一个孩子，返回这个孩子；如果有两个孩子，返回后继节点

之后写我们的删除逻辑，同样是按照上面的三种情况进行分类。

首先我们先考虑删除的节点有两个孩子，对于这种情况，我们可以这样思考，直接把这个节点的key，value和后继节点的key，vuale交换，这样，相当于删除后继节点位置的节点。我们只要继续往下递归就可以了。

之后思考一个如果删除的节点是根节点的情况，如果是根节点，它就只有没有孩子和只有一个红孩子的情况。没有孩子，直接把根节点变成null。有孩子，直接把孩子的key，value给根节点，根节点删除孩子。

之后我们还知道，如果删除的节点是红色无孩子节点，那么不会破坏平衡，我们只需要考虑删除黑节点的情况。

对于删除黑节点后，剩下的节点是红色的情况，只需要把这个红节点改成黑色就可以维持平衡

剩下的情况，我们把它叫做双黑，因为剩下的情况，都会导致有两个黑色节点相邻，并且删除节点的支路回少一个黑色节点。

双黑处理：
case1:被调整的兄弟节点为红，两个侄子一定为黑
删除节点是左孩子，父节点左旋
删除节点是右孩子，父节点右旋
父亲和兄弟节点需要变色
转成case2，case3的情况进行处理

case2:被调整的节点的兄弟为黑，两个侄子都是黑色
将兄弟变红，让兄弟节点的高度减少
如果父亲为红，将父亲变红，此时黑色节点数目恢复平衡
如果父亲为黑，说明还是双黑的情况，让父节点集训递归下去

case3:被调整的节点的兄弟为黑，有一个侄子是红色

如果兄弟是左孩子，左侄子是红，LL不平衡
右旋下去的父节点变黑，左侄子要变黑，兄弟变成父亲的颜色

如果兄弟是左孩子，右侄子是红，LR不平衡
先左旋兄弟节点，在右旋父亲节点
右侄子变成父节点的颜色，父节点变黑

如果兄弟是右孩子，右侄子是红，RR不平衡
左旋下去的父节点变黑，右侄子要变黑，兄弟变成父亲的颜色

如果兄弟是右孩子，左侄子是红，RL不平衡
先右旋兄弟节点，在左旋父亲节点
左侄子变成父节点的颜色，父节点变黑

    public void remove(int key) {
        Node delete = find(key);
        if (delete == null) {
            return;
        }
        doRemove(delete);
    }

    private void doRemove(Node delete) {
        Node replaced = findReplaced(delete);
        Node parent = delete.parent;
        //没有孩子
        if (replaced == null) {
            if (delete == root) {
                root = null;
            } else {
                if (isBlack(delete)) {
                    //需要进行调整
                    fixDoubleBlack(delete);
                } else {
                    //删除红色节点，无需任何操作
                }
                if (delete.isLeftChild()) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
                //有利于垃圾回收
                delete.parent = null;
            }
            return;
        }
        //有一个孩子
        if (delete.left == null || delete.right == null) {
            if (delete == root) {
                root.key = replaced.key;
                root.value = replaced.value;
                root.left = root.right = null;
                replaced.parent = null;
            } else {
                if (delete.isLeftChild()) {
                    parent.left = replaced;
                } else {
                    parent.right = replaced;
                }
                replaced.parent = parent;
                //垃圾回收
                delete.parent = delete.left = delete.right = null;
                if (isBlack(delete) && isBlack(replaced)) {
                    //这种情况不会出现，不存在单独的一个黑色叶子
                    //需要进行复杂处理
                    fixDoubleBlack(replaced);
                } else {
                    replaced.color = Color.BLACK;
                }
            }
            return;
        }
        //有两个孩子
        int t = delete.key;
        delete.key = replaced.key;
        replaced.key = t;

        Object v = delete.value;
        delete.value = replaced.value;
        replaced.value = v;
        doRemove(replaced);
    }

    //处理双黑
    private void fixDoubleBlack(Node x) {
        if (x == root) {
            return;
        }
        Node parent = x.parent;
        Node sibling = x.sibling();
        //case3:被调整节点的兄弟为红色
        if (isRed(sibling)) {
            if (x.isLeftChild()) {
                leftRotate(parent);
            } else {
                rightRotate(parent);
            }
            parent.color = Color.RED;
            sibling.color = Color.BLACK;
            fixDoubleBlack(x);
            return;
        }
        //case4:兄弟是黑色，并且两个侄子都是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            sibling.color = Color.RED;
            if (parent.color == Color.RED) {
                parent.color = Color.BLACK;
            } else {
                fixDoubleBlack(parent);
            }
        }
        //case5:兄弟是黑色，侄子有红色
        else {
            //LL
            if (sibling.isLeftChild() && isRed(sibling.left)) {
                rightRotate(parent);
                sibling.color = parent.color;
                sibling.left.color = Color.BLACK;
            }
            //LR
            else if (sibling.isLeftChild() && isRed(sibling.right)) {
                sibling.right.color = parent.color;
                leftRotate(sibling);
                rightRotate(parent);
            }
            //RR
            else if (!sibling.isLeftChild() && isRed(sibling.right)) {
                leftRotate(parent);
                sibling.color = parent.color;
                sibling.right.color = Color.BLACK;
            } else if (!sibling.isLeftChild() && isRed(sibling.left)) {
                sibling.left.color = parent.color;
                rightRotate(sibling);
                leftRotate(parent);
            }
            parent.color = Color.BLACK;
        }
    }


    //查找删除节点
    private Node find(int key) {
        Node p = root;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (key > p.key) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    //查找被删除节点替换成的节点
    private Node findReplaced(Node deleted) {
        if (deleted.left == null && deleted.right == null) {
            return null;
        }
        if (deleted.left == null) {
            return deleted.right;
        }
        if (deleted.right == null) {
            return deleted.left;
        }
        Node s = deleted.right;
        while (s.left != null) {
            s = s.left;
        }
        return s;
    }
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158