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

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

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

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

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

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

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

Процедура пошуку в бінарному дереві отримує на вході значення 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

Час на виконання цієї процедури є також O(h)

## [ред.] Дивись також

- Збалансоване дерево
- AVL-дерево
- B-дерево
- Червоно-чорне дерево

Отримано від "http://uk.wikipedia.org../../../%D0%B1/%D1%96/%D0%BD/%D0%91%D1%96%D0%BD%D0%B0%D1%80%D0%BD%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D1%88%D1%83%D0%BA%D1%83.html"

Категорії: Структури даних | Алгоритми сортування

##### Views

- Стаття
- Обговорення
- Поточна версія

##### Пошук

##### Іншими мовами

- Česky
- Dansk
- Deutsch
- English
- Español
- Suomi
- Français
- עברית
- Italiano
- 日本語
- Nederlands
- Polski
- Português
- Русский
- 中文