Бінарне дерево пошуку

Матеріал з Вікіпедії — вільної енциклопедії.

Бінáрне дéрево пóшуку (англ. binary search tree, BST) в інформатиці - бінарне дерево, в якому кожній вершині x співставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:

нехай x -- довільна вершина бінарного дерева пошуку. Якщо вершина y знаходиться в лівомі піддереві вершини x, то val[y] ≤ val[x]. Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].

Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритма центрованого обходу дерева. Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n -- розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log₂n) або O(h), де h - висота дерева (хоча гарантувати, що h не перевищує log₂n можна лише для збалансованих дерев, які є ефективнішими на пошукових алгоритмах, аніж прості бінарні дерева пошуку).

Зміст

1 Пошук в бінарному дереві
2 Мінімум, максимум, наступник та попередник
3 Додавання елементу
4 Видалення елементу
5 Дивіться також

[ред.] Пошук в бінарному дереві

Процедура пошуку в бінарному дереві отримує на вході значення k, яке необхідно знайти, та вказівник x на корень того піддерева, в якому слід шукати.

SEARCH (x, k)
1 if x = NULL or k = val[x]
2   then return x
3 if k < val[x]  
4   then return SEARCH (left[x], k)
5   else return SEARCH (right[x], k)

В процесі пошуку ми рухаємось від кореня, порівнюючи значення k зі значенням в поточній вершині х. Якщо k < val[x], пошук рекурсивно продовжується в лівому піддереві (k може бути тільки там згідно умови впорядкованості), інакше -- у правому піддереві. Очевидно, що довжина шляху не перевищує висоти дерева, тому час пошуку є O(h), де h - висота дерева.

[ред.] Мінімум, максимум, наступник та попередник

Мінімальний елемент в дереві можна знайти, розглянувши послідовно ліве піддерево left[x]:

MINIMUM (x)
1 while left[x]<>NULL
2   do x:=left[x]
3 return x

Процедура знаходження максимуму симетрична. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O(h)

Елемент, що є наступним за даним (в сенсі відношення впорядкованості) можна знайти за допомогою такої процедури:

SUCCESSOR (x)
1 if right[x] <> NULL
2   then return MINIMUM (right[x])
3 y:=p[x]
4 while y<>NULL and x = right[y]
5   do x:=y
6      y:=p[y]
7 return y

Процедура знаходження попереднього даному елемента є симетричною. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O(h)

[ред.] Додавання елементу

Процедура додавання елементу в бінарне дерево T додає елемент, зберігаючи умову впорядкованості. Параметром тут є вказівник z на нову вершину, в яку поміщене значення val[z], left[z]=right[z]=NULL.

INSERT (T, z)
1  y:=NIL
2  x:=root[T]
3  while x <> NULL 
4    do y:=x
5      if val[z] < val[x]
6        then x:=left[x]
7        else x:=right[x]
8  p[z]:=NULL
9  if y = NULL
10   then root[T] :=z
11   else if val[z]<val[y]
12     then left[y]:=z
13     else right[y]:=z

Процедура рухається вниз по дереву, при цьому зберігаючи в y вказівник на батька вершини x. Порівнюючи значення в x та z, процедура вирішує, в яке з піддерев рухатись далі. Процес завершується тоді, коли x=NULL. Саме сюди й слід помістити вершину z (рядки 8-13). Ця операція також потребує часу для виконання, пропорційного O(h)

[ред.] Видалення елементу

Параметром для процедури є вказівник на вершину, що видаляється. Тут можливі три варіанти дій:

якщо у вершини немає дітей, достатньо помістити NULL у відповідне поле його батька (замість вказівника на вершину, що видаляється)
якщо у вершини є одна дитина, можна з'єднати батька цієї вершини безпосередньо з її дитиною
якщо вершина має двох дітей, слід спочатку знайти слідуючий (в сенсі порядку) елемент y, в якого немає лівої дитини, а потім скопіювати значення та додаткові дані з вершини y на місце вершини, що видаляється, а саму вершину y видалити.

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