8000 back · codeflysafe/datastructure@ed2d44b · GitHub
[go: up one dir, main page]
Skip to content

Commit ed2d44b

Browse files
hsjfanshsjfans
committed
back
1 parent 6eb99d1 commit ed2d44b

File tree

1 file changed

+91
-2
lines changed

1 file changed

+91
-2
lines changed

‎docs/red_black_tree.md

Lines changed: 91 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@
4040

4141
得证
4242

43-
##调整节点
43+
## 调整节点
4444

4545
与avl树，类似，红黑树的插入或者删除，可能破坏其平衡(性质)。因此需要进行旋转调整。
4646

@@ -58,12 +58,101 @@
5858

5959

6060
### 左旋 and 右旋
61-
![](https://raw.githubusercontent.com/hsjfans/git_resource/master/20190506121552.png)
6261

62+
![](https://raw.githubusercontent.com/hsjfans/git_resource/master/20190506131550.png)
6363

64+
这些操作只是进行了指针的交换，话费常数时间。
6465

6566

6667

68+
### Insert element
69+
70+
对于新插入的节点，我们设定它都是红色的，然后采用一些操作，对其平衡性进行调整
71+
主要的调整方法为:
72+
73+
- recolor
74+
- rotation
75+
76+
#### 一个例子
77+
78+
先通过一个实例进行详细描述，后面在进行抽象，下面是一个红黑树插入元素15的过程。
79+
80+
81+
![](https://raw.githubusercontent.com/hsjfans/git_resource/master/20190506200643.png)
82+
83+
1. 先找到待插入的位置，插入元素15，并将其着色为 红色
84+
2. 15的祖父节点颜色是黑色，而它的父节点以及叔节点颜色是红色，因此，可以将祖父节点颜色下沉，即重新着色祖父节点为红色，叔节点以及父节点为黑色(case-1)。这时，冲突就变成了 10-18 颜色冲突
85+
86+
87+
![](https://raw.githubusercontent.com/hsjfans/git_resource/master/20190506200725.png)
88+
89+
3. 10-18 颜色冲突，且对于节点10来说，它并满足（case-1）的情况，无法进行重着色来满足条件4.此时，采用旋转操作，以节点10进行右旋（case-2），将10-18以及祖父节点在一条直线(看上去)。
90+
91+
![](https://raw.githubusercontent.com/hsjfans/git_resource/master/20190506201351.png)
92+
4. 再以节点10为节点，进行左旋(case-3)，然后重新着色（次数左子树黑高降低一，因此需要重新着色）
93+
5. 将跟节点重新着色。
94+
95+
#### 抽象
96+
97+
对于以上可以分为三种状态(或6种，因为左右情况对称)。
98+
```Insert(x)```,`x` 是插入的节点，`f(x)` 是其父节点，`f(f(x))` 是其祖父节点 `uncle of x as u(x)` 是其叔叔节点（y）。
99+
100+
单线条是黑色节点，双线条是红色
101+
102+
103+
104+
##### case-1
105+
106+
![](https://raw.githubusercontent.com/hsjfans/git_resource/master/20190506202531.png)
107+
108+
该情况是，`f(f(x))` 是黑色，`f(x)`是红色，`u(x)`是红色。
109+
110+
此时，可以将其祖父节点(`f(f(x))`)颜色吓成，即变成
111+
```
112+
color[f(x)] = BLACK
113+
color[f(f(x))] = RED
114+
color[u(x)] = BLACK
115+
```
116+
此时，可以解决节点x的颜色冲突。
117+
118+
119+
##### case-2
120+
121+
![](https://raw.githubusercontent.com/hsjfans/git_resource/master/20190506203203.png)
122+
123+
此时，节点`y`不是红色，无法通过着色来解决。x 是其父节点的右节点，视觉上看，节点`C-A-B`不再一条直线上，此时采用旋转，来使节点`C-A-B`在一条直线上
124+
125+
```
126+
127+
a->right = c
128+
c->left = b
129+
b->parent = c
130+
a->parent= c->parent
131+
c->parent = a
132+
133+
```
134+
135+
136+
##### case-3
137+
138+
![](https://raw.githubusercontent.com/hsjfans/git_resource/master/20190506204221.png)
139+
140+
节点`y`不是红色，无法通过着色来解决。x 是其父节点的左节点，视觉上看，节点`C-A-B`在一条直线上。此时，可以采用旋转加重着色进行调整。
141+
142+
```
143+
144+
c->left = a->right
145+
a->right = c
146+
a->parent=c->parent
147+
c->parent=a
148+
c->left=c
149+
150+
color[a] = BLACK
151+
color[c] = RED
152+
153+
154+
```
155+
67156

68157

69158

0 commit comments

Comments
 (0)
0