|
Читайте также: |
BST_Delete_Join (t, k, deleted)
1 
t – корень дерева или поддерева
2 k – значение удаляемого ключа
3 deleted – возвращаемый признак удаления
4 if t = nil
5 then deleted ← FALSE
6 return t
7 if k < key[ t ]
8 t hen left[ t ] ← BST_Delete_Join (left[ t ], k, del)
9 Calc_n (t)
10 deleted ← del
11 return t
12 if k > key[ t ]
13 then right[ t ] ← BST_Delete_Join (right[ t ], k, del)
14 Calc_n (t)
15 deleted ← del
16 return t
17 deleted ← TRUE
18 x ← JoinLR (left[ t ],right[ t ])
19 Delete_Node (t)
20 return x
JoinLR (tl,tr)
1 tl,tr – корни поддеревьев
2 if tr = nil then return tl
3 tr ← BST_Part (tr, 0)
4 left[ tr ] ← tl
5 Calc_n (tr)
6 return tr
Алгоритм объединения BST – деревьев
BST_Join(a,b)
1 
a,b -корни деревьев/поддеревьев
2 if a = 0 then return b
3 if b = 0 then return a
4 left ← left[ a ]
5 right ← right[ a ]
6 left[ a ] ← nil
7 right[ a ] ← nil
8 b ← Root_Insert (b, a)
9 left[ b ] ← BST_Join (left, left[ b ])
10 right[ b ] ← BST_Join (right, right[ b ])
11 return b
Root_Insert(b, a)
1 b – корень первого дерева / поддерева
2 a – корень первого дерева
3 if b = nil
4 then return a
5 if key[left[ b ]] = key[ a ]
6 then delete a
7 return R (b)
8 if key[right[ b ]] = key[ a ]
9 then delete a
10 return L (b)
11 if key[ a ] < key[ b ]
12 then left[ b ] ← Root_Insert (left[ b ], a)
13 return R (b)
14 else right[ b ] ← Root_Insert (right[ b ], a)
15 return L (b)
Алгоритм вертикальной печати BST – дерева
BST_Show(t, level)
1 t -корень дерева/поддерева
2 level – глубина узла t
3 if t = nil
Then return
5 Show (right[ t ], level +1)
6 for i← 0 to 2 
level
7 do печать ’_’
8 печать key[ t ]
9 перевод курсора на начало следующей строки
10 Show (left[ t ], level +1)
Приложение Г
Дата добавления: 2015-11-04; просмотров: 121 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Итеративный алгоритм поразрядной LSD-сортировки | | | Алгоритм вставки элемента в AVL-дерево |