红黑树

鸣谢：
https://www.jianshu.com/p/0eaea4cc5619
https://blog.csdn.net/tanrui519521/article/details/80980135
https://zhuanlan.zhihu.com/p/24367771

删除：https://www.cnblogs.com/tongy0/p/5460623.html

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

性能优于AVL树，C++中的map，以及Java中的TreeMap，TreeSet， Java8中的HashMap的实现也采用了红黑树。

5条基本特征：

（1）每个结点要么是红的要么是黑的。
（2）根结点是黑的。
（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
（4）如果一个结点是红的，那么它的两个儿子都是黑的。
（5）对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

  • 红黑树的5条特性确保了从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得整棵树大致上是平衡的

upload successful

树的插入：（警惕红）

新插入的节点总是设为红色的，所以如果父节点为黑色，就不需要修复，因为没有任何性质被改变，所以只有在父节点为红色节点时需要做修复操作。

可以肯定调节的时候该点一定有grandparent，因为根节点为黑，连续两个红才需要调整。

情况1：cur为红，parent为红，pParent为黑，uncle存在且为红

则将parent，uncle改为黑，pParent改为红，然后把pParent当成cur，继续向上调整。

对策 :把父节点和叔叔节点变黑，爷爷节点涂红，然后把当前节点指针给到爷爷，让爷爷节点那层继续循环，接受红黑树特性检测。

simple case

z是当前点

情况2：cur为红，parent为红，pParent为黑，uncle不存在/u为黑

对策：当前节点的父节点作为新的当前节点，以新当前指点为支点左旋

parent为pParent的左孩子，cur为parent的左孩子，则进行右单旋转。

upload successful

情况3：当前节点的父节点是红色，叔叔节点是黑色/不存在，且当前节点是其父节点的右儿子，祖父节点的左儿子是父节点

对策： 父节点变黑，祖父变红，以祖父节点为支点右旋

1为当前点，祖父节点为下一轮遍历的当前节点。

只变色不拐

4为当前点，取初始父节点3为下一轮遍历的当前节点。然后交换一下3和4，然后再重组

不变色只拐

3为当前点，取父亲为下一轮遍历的当前节点。

变色+拐

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
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
#define N 1000
#define red true
#define black false
class Node{
    public:
    static int length;
    bool br;
    // true red false black
    int num;
    Node*l,*r,*f;
    Node(){
        num=-1;
        r=f=l=NULL;
    } 
};
int Node::length=0;
void left_turn(Node*&root){
    Node*p=root->f;
    Node*pP=root->f->f;
    if(p->l){
        p->l->f=pP;
    }
    p->f=pP->f;
    pP->r=p->l;
    p->l=pP;
    if(pP->f==NULL){

    }
    else if(pP->f->num>pP->num){
        pP->f->l=p;
    }
    else{
        pP->f->r=p;
    }
    pP->f=p;
}
void right_turn(Node*&root){
    Node*p=root->f;
    Node*pP=root->f->f;
    if(p->r){
        p->r->f=pP;
    }
    p->f=pP->f;
    pP->l=p->r;
    p->r=pP;
    if(pP->f==NULL){

    }
    else if(pP->f->num>pP->num){
        pP->f->l=p;
    }
    else{
        pP->f->r=p;
    }
    pP->f=p;
}
void balance(Node*&root){
    // 如果是top点，没有father/grandfather需要单独讨论，因为可能是红点做top点
    if(root->f==NULL){
        root->br=black;
        return;
    }
    else if(root->br==black){
        return;
    }
    if(root->f->br==red){
        // Need to deal with this situation.
        // first decide you are in which side(l/r). there will be two choice and four cases.
        if(root->f->f->l&&root->f->f->r&&root->f->f->l->br==red&&root->f->f->r->br==red){
            // balance1 , p=red , uncle=red
            root->f->f->br=red;
            root->f->f->l->br=black;
            root->f->f->r->br=black;
            balance(root->f->f);
        }
        else{
            // balance2, p(left)=red , uncle=black/NULL
            if(root->f->f->r==NULL||root->f->f->r->br==black){
                // right turn
                Node*pP=root->f->f;
                Node*p=root->f;
                if(root->f->num>root->num){
                    p->br=black;
                    pP->br=red;
                    right_turn(root);
                    balance(root->f);
                }
                else{
                    root->br=black;
                    pP->br=red;                    
                    // adjust
                    if(root->l){
                        root->l->f=root->f;
                    }
                    p->r=root->l;
                    pP->l=root;
                    root->f=pP;
                    root->l=p;
                    p->f=root;
                    right_turn(root->l);
                    balance(root);
                }
            }
            // balance3 , p(right)=red , uncle(left)=black/NULL
            else{   // warm up
                Node*pP=root->f->f;
                Node*p=root->f;
                //left turn
                if(root->f->num>root->num){
                    root->br=black;
                    pP->br=red;                    
                    // adjust
                    pP->r=root;
                    p->f=root;
                    root->f=pP;
                    Node*t=root;
                    // 为了防止root被误置为NULL,出此下策保留该root指针
                    p->l=root->r; // bug p->l(指向root的左指针)=root->r 变成了 root=root->r
                    
                    root=t;
                    root->r=p;
                    left_turn(root->r);
                    balance(root);
                }
                else{
                    p->br=black;
                    pP->br=red;                    
                    left_turn(root);
                    balance(root->f);
                }
            }
        }
    }
    else{
        return;
    }
}
Node* leave=NULL;
Node* insert(Node*&root,int num){
    if(root==NULL){       
        Node *node=new Node();
        node->num=num;
        node->br=red;
        if(node->length==0){
            // root必须为black
            node->length=1;
            node->br=black;
        }
        root=node;
        leave=root;
        return node;
    }
    else if(root->num>num){
        root->l=insert(root->l,num);
        root->l->f=root;      
    }
    else{
        root->r=insert(root->r,num);
        root->r->f=root;      
    }
    return root;
}
// 打印看看结构
void print(Node*root){
    if(root==NULL){
        return;
    }
    cout<<root->num<<"  color: "<<(root->br==black?"black":"red")<<endl;
    print(root->l);
    print(root->r);
}
int main(){
  int i,j,input,k;
  int p,e;
  Node*root=NULL;
  freopen("inputs.txt","r+",stdin);
  cin>>p;
  for(i=0;i<p;i++){
      cin>>e;
      insert(root,e);
      balance(leave);
      root->length++; 
  }
  cout<<"preorder :\n";
  print(root);
}

/*
7
5 7 1 4 6 3 2

5  color: black
3  color: red
1  color: black
2  color: red
4  color: black
7  color: black
6  color: red

6 7 0 4 5 2 1

6  color: black
4  color: red
1  color: black
0  color: red
2  color: red
5  color: black
7  color: black

*/

树的删除：（警惕黑）

在红黑树中，删除一个节点往大的说，只有以下四种情况。

情况一：删除的节点的左、右子树都非空；

情况二：删除的节点的左子树为空树，右子树非空；

情况三：删除的节点的右子树为空树，左子树非空；

情况四：删除的节点的左、右子树都为空树；

其中情况一，可以按与其他二叉搜索树的删除方式一样处理，最终可以转换到后面的三种情况。具体为：找到(Old)D节点的直接后继节点(暂且称为X节点)，然后将X的值转移到D节点，最后将X节点作为真正要被删除掉的节点(即：(Real)D节点)。这样删除操作后，可以保证该树仍然为一棵二叉搜索树。但这样删除(Real)D节点后，可能会破坏红黑树的性质。所以需要额外做一些调整处理，这便是下面将要详细讨论的内容。

说明：下文中所提到的D，除非有特别说明，否则都将指的是(Real)D（一般可以认为该RealD节点的左子树为空，OldD不一定），最终要删除的节点一般是OldD的右节点或者右节点的最前面的一个左节点，当然也可能无右节点只能删自己。

upload successful

删除的类别可以分为几种：

（1）首先 ，从当前点D和DR之间的颜色顺序看。

< 1 > 红->黑/NULL ，P肯定为黑 ， 直接删掉红，用黑（NULL）替换。

upload successful

< 2 > 黑->红 ，直接拿红替换黑，然后红变黑。

upload successful

< 3 > 黑->黑 / NULL ， 情况变得复杂。

（2）然后 ，根据uncle的颜色再分一次情况讨论：

< 1 > 如果uncle是红，那就很容易了。因为P不可能是红只能是黑，只有一种情况。

upload successful

upload successful

< 2 > uncle为黑时，特别复杂。

  • 1.SL=红，uncle=黑，P=黑/红，SR=黑/红

将S右旋转时，接着将SL改为P的颜色，P的颜色改为黑色(用这个黑色来填补DR分支的黑节点数)，将P左旋转。

upload successful

  • 2.SR=红，P=黑/红，SL=黑/红

upload successful

  • 3.S=黑，P=红，SL=SR=黑（处理简单，只要变色）

upload successful

  • 4.SR=SL=黑，P=黑（处理简单，只要变色）

upload successful

本文标题:红黑树

文章作者:SaltedMdFiveSh

发布时间:2019-10-01, 13:44:00

最后更新:2019-10-08, 13:10:34

原始链接:https://silver-birch-wawa.github.io/2019/10/01/红黑树/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 情况1：cur为红，parent为红，pParent为黑，uncle存在且为红
  2. 2. 情况2：cur为红，parent为红，pParent为黑，uncle不存在/u为黑
  3. 3. 情况3：当前节点的父节点是红色，叔叔节点是黑色/不存在，且当前节点是其父节点的右儿子，祖父节点的左儿子是父节点
  • 删除的类别可以分为几种：
    • | 本站总访问量次 ,本文总阅读量次