Алгоритм вставки элемента в AVL-дерево

AVL_Insert(t, k, data, h, inserted)

1 t – корень дерева / поддерева

2 k –ключ нового элемента

3 data – данные нового элемента

3 iserted – возвращаемый признак вставки

4 h – возвращаемый признак увеличения высоты

5 h ← FALSE

6 if₁ k = key[ t ]

7 then₁ inserted ← FALSE

8 return t

9 if₂ t=nil

10 then₂ t ← Create_Node (k, data)

11 bal[ t ] ← 0

12 h ← TRUE

13 inserted ← TRUE

14 return t

15 if₃ k < key[ t ]

16 then₃ left[ t ] ← AVL_Insert (left[ t ], k, data, hh, ins)

17 if₄ hh = TRUE

18 then₄ выросла левая ветвь

19 if₅ bal[ t ] = 1

20 then₅ bal[ t ] ← 0

21 else₅ if₆ bal[ t ] = 0

22 then₆ bal[ t ] ← -1

23 h ← TRUE

24 балансировка

25 else₆ if₇ bal[left[ t ]] = -1

26 then₇ t ← R (t)

27 else₇ t ← LR (t)

28 else₃ right[t] ← AVL_Insert (right[ t ], k, data, hh, ins)

29 if₈ hh = TRUE

30 then₈ выросла правая ветвь

31 if₉ bal[ t ] = -1

32 then₉ bal[ t ] ← 0

33 else₉ if₁₀ bal[ t ] = 0

34 then₁₀ bal[ t ] ← 1

35 h ← TRUE

36 балансировка

37 else₁₀ if₁₁ bal[right[ t ]] = 1

38 then₁₁ t ← L (t)

39 else₁₁ t ← RL (t)

40 inserted ← ins

41 return t

R (t)

1 x← left[ t ]

2 left[ t ] ← right[x]

3 right[x] ←t

4 bal[x] ← bal[ t ] ← 0

5 return x

LR (t)

1 x ← left[ t ]

2 y ← right[x]

3 right[x] ← left[y]

4 left[y] ← x

5 left[ t ] ← right[y]

6 right[y] ← t

7 if bal[y] =-1

8 then bal[ t ] ← 1

9 else bal[ t ] ← 0

10 if bal[y] = 1

11 then bal[x] ← -1

12 else bal[x] ← 0

13 bal[y] ← 0

14 return y

Рекурсивный алгоритм вставки элемента в 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

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

Итеративный алгоритм удаления элемента из RB – дерева

It_RB_Delete (root, k)

1 root -корень RB-дерева

2 k –ключ удаляемого элемента

3 t ← root

4 while k ≠ key[t] and t ≠ tnil tnil – фиктивный узел RB-дерева

5 do if k < key[t]

6 then t ← left[t]

7 else t ← right[t]

8 if t = tnil

9 then return FALSE

10 if left[t]= tnil or right[t] = tnil

11 then x ← t x- удаляемый узел

12 else x ← BST_Successor(root, t)

13 if left[x] ≠ tnil

14 then y ← left[x] y-сын удаляемого узла, возможно tnil

15 else y ← right[x]

16 p[y] ← p[x]

17 if p[x]= tnil x - корень

18 then root ← y

19 else if x =left[p[x]]

20 then left[p[x]] ← y

21 else right[p[x]] ← y

22 if x ≠ t x -замещающий узел

23 then key[t] ← key[x]

24 data[t] ← data[x]

25 if color[x]=BLACK

26 then RB_Fixup (root, y)

27 Delete_Node (x)

28 return TRUE

RB_Fixup(root, y)

1 root - корень дерева

2 y - узел с двойной чернотой

3 while y ≠ root and color[ y ] = BLACK

4 do if y = left[p[ y ]]

5 then w ← right[p[ y ]]

6 if color[w] = RED случай 1

7 then color[w] ← BLACK

8 color[p[ y ]] ← RED

9 It_L (root, p[ y ])

10 w ← right[p[ y ]]

11 if color[left[w]] =BLACK and color[right[w]]=BLACK случай 2

12 then color[w] ← RED

13 y ← p[ y ]

14 else if color[left[w]] = RED случай 3

15 then color[left[w]] ← BLACK

16 color[w] ← RED

17 It_R (root, w)

18 w ← right[p[ y ]]

19 случай 4

20 color[w] ← color[p[ y ]]

21 color[p[ y ]] ← BLACK

22 color[right[w]] ← BLACK

23 It_L (root, p[ y ])

24 y ← root для прекращения цикла

Else

26 симметричный фрагмент для y = right[p[ y ]]с заменой left на right

27 конец цикла

28 color[ y ] ← BLACK если y – красный узел или y -корень

Дата добавления: 2015-11-04