Дерево пошуку

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Де́рево (як структура даних) — динамічна нелінійна структура даних, кожен елемент якої містить власне інформацію (або посилання на те місце в пам'яті ЕОМ, де зберігається інформація) та посилання на кілька (не менше двох) інших таких же елементів.

Загальні відомості[ред.ред. код]

Дерева пошуку призначені для представлення словників як абстрактного типу даних. Як і пріоритетні черги, вони представляють зважені множини, але з іншим набором операцій, а саме:

  • Search — пошук елемента із заданим ключем.
  • Minimum — пошук елемента з мінімальним ключем.
  • Maximum — пошук елемента з максимальним ключем.
  • Predecessor — пошук елемента з попереднім ключем.
  • Successor — пошук елемента з наступним ключем.
  • Insert — вставка елемента зі своїм ключем.
  • Delete — видалення зазначеного елемента.

Вважається, що кожен елемент словника має ключ (вагу), що приймає значення з лінійно впорядкованої множини. Такою множиною може бути, наприклад, числова множина або множина слів в деякому алфавіті. В останньому випадку в якості лінійного порядку можна розглядати лексикографічний порядок. Таким чином, дерево пошуку може бути використано і як словник, і як пріоритетна черга. Час виконання основних операцій пропорційний висоті дерева. Якщо кожен внутрішній вузол двійкового дерева має рівно двох нащадків, то його висота і час виконання основних операцій пропорційні логарифму числа вузлів. І навпаки, якщо дерево являє собою лінійний ланцюжок з n вузлів, цей час виростає до Ο(n). Відомо, що висота випадкового двійкового дерева є Ο(log n), так що в цьому випадку час виконання основних операцій є Ο(log n). Звичайно, що виникаючі на практиці двійкові дерева пошуку можуть бути далекі від випадкових. Однак, прийнявши спеціальні заходи по балансуванню дерев, можна гарантувати, що висота дерев з n вузлами буде O(log n).

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

Двійкове дерево пошуку
B-дерево
Збалансоване дерево
Червоно-чорне дерево

Джерела[ред.ред. код]

  • Thomas H. Cormen, Charles E. Leiserson. Introduction to algorithms.