Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Алгоритм удаления из BST-дерева на основе объединения поддеревьев

Структуры BST - деревьев | Задание к лабораторной работе | Структуры сбалансированных деревьев | Задание к лабораторной работе | Методические указания к выполнению задания | Функции хеширования | Разрешение коллизий и структуры хеш-таблиц | Задание к лабораторной работе | Методические указания к выполнению задания | Алгоритм пирамидальной сортировки |


Читайте также:
  1. А и вас‑то, царей‑князей, не бьют, не казнят». Мотив неприкосновенности правителя‑жреца
  2. Алгоритм анализа иллюстрации
  3. Алгоритм вставки элемента в 2-3 - дерево
  4. Алгоритм вставки элемента в AVL-дерево
  5. Алгоритм захисту БД MS Access
  6. Алгоритм катетеризации мочевого пузыря.
  7. Алгоритм пирамидальной сортировки

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 trBST_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 bRoot_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-дерево

mybiblioteka.su - 2015-2024 год. (0.007 сек.)