Рекурсивный алгоритм вставки элемента в rb – дерево
RB_Insert(root, k, data)
1
root-корень
RB-дерева
2
k
–ключ нового элемента
3
data
– данные нового элемента
3 root ← RB_Insert1(root, k, data, 0, ins)
4 color [root] ← BLACK
5 return ins
RB_Insert1(t, k, data, s, inserted)
1
t-корень
дерева/поддерева
2
k
–ключ нового элемента
3
data
– данные нового элемента
4
s-
тип родителя(левый-0/правый-1)
5
iserted
– возвращаемый признак вставки
6 if k = key[t]
7 then inserted ← FALSE
8 return t
9 if t = nil
10 then t ← Create_RB_Node(k, data)
11 color[t] ← RED
12 inserted ← TRUE
13 return t
14 if color[left[t]] = RED and color[right[t]] = RED
15 then color[t] ← RED
16 color[left[t]] ← color[right[t]] ← BLACK
17 if k < key[t]
18 then left[t] ← RB_Insert1(left[t], k, data,0, ins)
19 if color[t] = RED and color[left[t]] = RED and s = 1
20 then t ← R(t)
21 if color [left[t]] = RED and color [left[left[t]]] = RED
22 then t ← R(t)
23 color[t] ← BLACK
24 color[right[t]] ← RED
25 else right[t] ← RB_Insert1(right[t], k, data,1, ins)
26 if color[t] = RED and color[right[t]] = RED and s = 0
27 then t ← L(t)
28 if color[right[t]] = RED and color[right[right[t]]] = RED
29 then t ← L(t)
30 color[t] ← BLACK
31 color[left[t]] ← RED
32 inserted ← ins
33 return t
Итеративный алгоритм вставки элемента в rb – дерево
It_RB_Insert(root, k, data)
1
root-корень
дерева
2
k
–ключ нового элемента
3
data
– данные нового элемента
4
if
root
= tnil 
tnil
– фиктивный узел RB-дерева
5 then root ← Create_RB_Node(k, data)
6 color[root] ← BLACK
7 return TRUE
8 t ← root
9 while t ≠ tnil
10 do
11 pred ← t
12 if k = key[t]
13 then return FALSE
14 if k < key[t]
15 then t ← left[t]
16 else t ← right[t]
17 if k < key[pred]
18 then t ← left[pred] ← Create_RB_Node(k, data)
19 else t ← right[pred] ← Create_RB_Node(k,data)
20 color[t] ← RED
21 while t ≠ root and color[p[t]] = RED
22 do if p[t] = left[p[p[t]]]
23 then y ← right[p[p[t]]]
24
if
color[y]=RED 
случай
1
25 then color[p[t]] ← color[y] ← BLACK
26 color[p[p[t]]] ← RED
27 t ← p[p[t]]
28
else
if
t = right[p[t]] 
случай
2
29 then t ← p[t]
30 It_L(root, t)
31
color[p[t]] ← BLACK 
случай
3
32 color[p[p[t]]] ← RED
33 It_R(root, p[p[t]])
34
else
симметричный
текст (строки 23 – 33)с заменой left
на right
35
конец
цикла
36 color[root] ← BLACK
37 return TRUE
It_L (root, t)
1 x ← right[t]
2 right[t] ← left[x]
3
if
left[x] ≠ tnil 
tnil
– фиктивный
узел
RB-дерева
4 then p[left[x]] ← t
5 p[x] ← p[t]
6 if p[t] = tnil
7 then root ← x
8 else if t = left[p[t]]
9 then left[p[t]] ← x
10 else right[p[t]] ← x
11 left[x] ← t
12 p[t] ← x