平衡二叉树-红黑树

发表于 更新于 分类于 ， ， 阅读次数： 本文字数： 4.2k 阅读时长 ≈ 4 分钟
引言：数据结构——平衡二叉树红黑树

平衡二叉树——红黑树

2-3树

在了解红黑树之前，要先学习一下2-3树

2-3树：

满足二分搜索树的性质，但不是二叉树。

2-3树就是每个节点有2个或者3个孩子的树

image-20201009194645835

例如这就是一棵2-3树：

image-20201009195155099

重要的性质：2-3树是一棵绝对平衡（从根节点到任意节点的路径一定是相同的）的树

绝对平衡

如图：2-3树是一棵可以保持绝对平衡的树

image-20201010161809183

红黑树

2-3树与红黑树的等价

在理解2-3树是什么之后，理解红黑树就不会太难了。

2-3树与红黑树之间的关系如图：

image-20201010161852826

由此我们再来看红黑树的性质：

红黑树就是这样的树：

  1. 每个节点是红色或者黑色
  2. 根节点是黑色
  3. 叶子节点是黑色
  4. 如果一个节点是红色的，那么他的孩子节点都是黑色的
    • 如果一个红节点的孩子有一个是红色的，就出现四节点了，就不是我们所说的2-3树了
  5. 从任意一个节点到叶子节点，经过的黑色节点是一样的（黑平衡）
    • 如同2-3树，是一棵绝对平衡的树

红黑树添加元素

红黑树只会添加红节点，以这个为前提，我们来看

image-20201010162121161

整体来看，处理的过程有三种情况

image-20201010162304760

代码

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
package BinaryTree.RBTree;

import BinaryTree.AVLTree.FileOperation;

import java.util.ArrayList;

/**
 * @author 董文浩
 * @Date 2020/10/10 10:44
 * 红黑树
 */
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;    //* 只插入黑色节点
        }
    }

    private Node root;
    private int size;

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

    public int getSize(){
        return size;
    }

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

    // * 判断节点node的颜色
    private boolean isRed(Node node){
        // * 为null代表叶子结点，叶子节点都是黑色
        if(node == null) {
            return BLACK;
        }
        return node.color;
    }

    //   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 filpColors(Node node){
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    // 向红黑树中添加新的元素(key, value)
    public void add(K key, V value){
        root = add(root, key, value);
        root.color = BLACK; // 完成后的根节点必须为黑色节点
    }

    // 向以node为根的红黑树中插入元素(key, value)，递归算法
    // 返回插入新节点后红黑树的根
    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.left = add(node.left, key, value);
        } else if(key.compareTo(node.key) > 0) {
            node.right = add(node.right, key, value);
        } else // key.compareTo(node.key) == 0
        {
            node.value = value;
        }
        // 左黑右红 -> 左旋
        if(isRed(node.right) && !isRed(node.left)){
            node =leftRotate(node);
        }
        // LL都为红
        if(isRed(node.left) && isRed(node.left.left)){
            node = rightRotate(node);
        }
        // 左右为红
        if(isRed(node.left) && isRed(node.right)){
            filpColors(node);
        }

        return node;
    }

    // 返回以node为根节点的二分搜索树中，key所在的节点
    private Node getNode(Node node, K key){

        if(node == null) {
            return null;
        }

        if(key.equals(node.key)) {
            return node;
        } else if(key.compareTo(node.key) < 0) {
            return getNode(node.left, key);
        } else // if(key.compareTo(node.key) > 0)
        {
            return getNode(node.right, key);
        }
    }

    public boolean contains(K key){
        return getNode(root, key) != null;
    }

    public V get(K key){

        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }

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

        node.value = newValue;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node){
        if(node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    // 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    private Node removeMin(Node node){

        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

}



对比普通平衡二叉树、AVL树、红黑树

  • 对于完全随机的数据来说，普通平衡二叉树足够使用了，因为完全随机的数据不会有太大的偏斜，而且普通平衡二叉树没有复杂的操作逻辑
  • 对于查询较多的情况，AVL树较好（红黑树牺牲了平衡性，达到了2logn）的高度
  • 红黑树的统计性能更好（综合增删查改所有操作）