Двійкове дерево пошуку
Двійкове (або Бінарне) дéрево пóшуку (англ. binary search tree, BST) в інформатиці — двійкове дерево, в якому кожній вершині x співставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:[Джерело?]
- нехай x — довільна вершина двійкового дерева пошуку. Якщо вершина y знаходиться в лівому піддереві вершини x, то val[y] ≤ val[x].
- Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].
Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритму центрованого обходу дерева.[Джерело?]
Представляється таке дерево вузлами наступного вигляду:
*Node = (element, key, left, right, parent). Доступ до дерева T здійснюється за допомогою посилання root.
Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n — розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log2n) або O(h), де h — висота дерева (хоча гарантувати, що h не перевищує log2n можна лише для збалансованих дерев, які є ефективнішими на пошукових алгоритмах, аніж прості бінарні дерева пошуку).[Джерело?]
Зміст |
[ред.] Операції з двійковим деревом пошуку
Найпоширенішою операцією, яка виконується з бінарним деревом пошуку, є пошук в ньому певного ключа. Крім того, бінарні дерева пошуку підтримують такі запити, як пошук мінімального і максимального елемента, а також попереднього і наступного.
[ред.] Пошук
Для пошуку вузла із заданим ключем в бінарному дереві пошуку використовується наступна процедура Tree_Search, яка отримує в якості параметрів покажчик на корінь бінарного дерева і ключ k, а повертає покажчик на вузол з цим ключем (якщо такий існує; в іншому випадку повертається значення NIL).
| Tree_Search (x, k) |
|---|
1. if х = nil або k = key [k] 2. then return х 3. if k < key [x] 4. then return Tree_Search (left [x], k) 5. else return TREE_SEARCH (right [x], k) |
Процедура пошуку починається з кореня дерева і проходить вниз по дереву. Для кожного вузла х на шляху вниз його ключ key[x] порівнюється з переданим в якості параметра ключем k. Якщо ключі однакові, пошук завершується. Якщо k менше key[х], пошук триває в лівому піддереві х; якщо більше - то пошук переходить в праве піддерево. Ту ж процедуру можна записати ітеративно, "розгортаючи" рекурсію в цикл while.
[ред.] Ітеративна версія процедури Пошук
| Iterative_Tree_Search(x, k) |
|---|
1. while x ≠ NIL и k ≠ key[х] 2. do if k ← key[х] 3. then х ← left[x] 4. else х ← right[x] 5. return x |
[ред.] Пошук мінімального(максимального) елемента
Алгоритм пошуку мінімального елемента.
Елемент з мінімальним значенням ключа легко знайти, слідуючи за вказівниками left від кореневого вузла до тих пір, поки не зустрінеться значення NIL. Процедура TREE_MINIMUM(x) повертає покажчик на знайдений елемент піддерева з коренем x.
| TREE_MINIMUM(X) |
|---|
1. while left[x] ≠ NIL 2. do x ← left[x] 3. return x |
Алгоритм пошуку максимального елемента симетричний:
| TREE_MAXIMUM(X) |
|---|
1. while left[x] ≠ NIL 2. do x ← right[x] 3. return x |
Обидва алгоритми вимагають часу O(h), де h - висота дерева.
[ред.] Наступний і попередній елементи
Якщо x - покажчик на деякий вузол дерева, то процедура TREE_SUCCESSOR(X) повертає покажчик на вузол з наступним за x елементом або nil, якщо зазначений елемент - останній в дереві:
| TREE_SUCCESSOR(X) |
|---|
1. if right[x] ≠ NIL 2. then return TREE_MINIMUM(right[x]) 3. у ← p[x] 4. while y ≠ NIL та x = right[y] 5. do x ← у 6. у ← p[y] 7. return у |
Наведена процедура окремо розглядає два випадки. Якщо праве піддерево вершини не пусте, то наступний за x елемент є крайнім лівим вузлом у правому піддереві, який виявляється процедурою TREE_MlNlMUM(right[x]). З іншого боку, якщо праве піддерево вузла x пусте, та у x існує наступний за ним елемент y, то y є найменшим предком x, чий лівий вузол також є предком x. Для того щоб знайти y, ми просто піднімаємося вгору по дереву до тих пір, поки не зустрінемо вузол, який є лівим дочірнім вузлом свого батька. Ця дія виконується в рядках 3-7 алгоритму.
Час роботи алгоритму TREE_SUCCESSOR в дереві заввишки h складає O(h), оскільки ми або рухаємося по шляху вниз від вихідного вузла, або по шляху нагору. Процедура пошуку подальшого вузла в дереві TREE_PREDECESSOR симетрична процедурі TREE_SUCCESSOR і також має час роботи O(h).
Якщо в дереві є вузли з однаковими ключами, ми можемо просто визначити наступний і попередній вузли як ті, що повертаються процедурами TREE_SUCCESSOR та TREE_PREDECESSOR відповідно.
[ред.] Додавання елемента
Для вставки нового значення v в бінарне дерево пошуку Т ми скористаємося процедурою TREE_INSERT. Процедура отримує як параметр вузол z, у якого key[z] = v, left[z] = NIL і right[z] = NIL, після чого вона таким чином змінює Т і деякі поля z, що z виявляється вставленим в відповідну позицію в дереві.
| TREE_INSERT (T, Z) |
|---|
1. у ← NIL 2. х ← root[T] 3. while x ≠ NIL 4. do у ← x 5. if key[z] < key [x] 6. then x ← left[x] 7. else x ← right[x] 8. p [z] ← у 9. if у = NIL 10. then root[T] ← z // Дерево T - пусте 11. else if key[z] <key[y] 12. then left[y] ← z 13. else right[у] ← z |
[ред.] Видалення елемента
Процедура видалення даного вузла z з бінарного дерева пошуку отримує в якості аргументу покажчик на z. Процедура розглядає три можливі ситуації:
1. Якщо у вузла z немає дочірніх вузлів, то ми просто змінюємо його батьківський вузол р[z], замінюючи в ньому покажчик на z значенням NIL.
2. Якщо у вузла z лише один дочірній вузол, то ми видаляємо вузол z, створюючи новий зв'язок між батьківським і дочірнім вузлом вузла z.
3. Якщо у вузла z два дочірніх вузла, то ми знаходимо наступний за ним вузол у, у якого немає лівого дочірнього вузла, прибираємо його з позиції, де він перебував раніше, шляхом створення нового зв'язку між його батьком і нащадком, і замінюємо ним вузол Z.
DELETE (T, z) 1 if left[z] = NULL or right[z]=NULL 2 then y:=z 3 else y:=SUCCESSOR(z) 4 if left[y] <> NULL 5 then x:=left[y] 6 else x:= right[y] 7 if x <> NULL 8 then p[x]:=p[y] 9 if p[y]:=NULL 10 then root[T]:=x 11 else if y=left[p[y] ] 12 then left[p[y] ] :=x 13 else right[p[y] ]:=x 14 if y <> z 15 then val[z]:=val[y] 16 //копіювання додаткових даних з y 17 return y
Час на виконання цієї процедури є також O(h)
[ред.] Джерела
«Искусство программирование. Сортировка и поиск». Дональд Кнут.
«Алгоритмы. Построение и анализ». Кормен Томас, Лейзерсон Чарльз.
[ред.] Див. також
 |
У Вікіджерелах є оригінали текстів на тему: |
