Дерево пошуку
В інформатиці де́рево пошуку (як структура даних) — це деревоподібна структура даних, яку застосовують для пошуку конкретних ключів усередині множини. Щоб дерево могло функціонувати як дерево пошуку, ключ кожного вузла повинен бути більшим за будь-які ключі в піддеревах ліворуч і менше будь-яких ключів у піддеревах праворуч.
Перевагою дерев пошуку є їх ефективний час пошуку за умови, що дерево достатньо збалансоване, тобто листя на обох кінцях мають подібну глибину. Існують різні види структур даних, які є деревами пошуку. Деякі з них також дозволяють ефективно додавати та видаляти елементи. Операції на таких деревах потім повинні підтримувати баланс дерева.
Дерева пошуку часто застосовуються для реалізації асоціативного масиву. Алгоритм дерева пошуку використовує ключ від пари ключ-значення, щоб знайти місце, а потім програма зберігає всю пару ключ-значення у цьому конкретному місці.
Загальні відомості
Дерева пошуку призначені для представлення словників як абстрактного типу даних. Як і пріоритетні черги, вони представляють зважені множини, але з іншим набором операцій, а саме:
- Search — пошук елемента із заданим ключем.
- Minimum — пошук елемента з мінімальним ключем.
- Maximum — пошук елемента з максимальним ключем.
- Predecessor — пошук елемента з попереднім ключем.
- Successor — пошук елемента з наступним ключем.
- Insert — вставка елемента зі своїм ключем.
- Delete — видалення зазначеного елемента.
Вважається, що кожен елемент словника має ключ (вагу), що приймає значення з лінійно впорядкованої множини. Такою множиною може бути, наприклад, числова множина або множина слів в деякому алфавіті. В останньому випадку як лінійний можна розглядати лексикографічний порядок. Таким чином, дерево пошуку може бути використано і як словник, і як пріоритетна черга. Час виконання основних операцій пропорційний висоті дерева. Якщо кожен внутрішній вузол двійкового дерева має рівно двох нащадків, то його висота і час виконання основних операцій пропорційні логарифму числа вузлів. І навпаки, якщо дерево являє собою лінійний ланцюжок з n вузлів, цей час виростає до Ο(n). Відомо, що висота випадкового двійкового дерева є Ο(log n), так що в цьому випадку час виконання основних операцій є Ο(log n). Звичайно, що виникаючі на практиці двійкові дерева пошуку можуть бути далекі від випадкових. Однак, прийнявши спеціальні заходи по балансуванню дерев, можна гарантувати, що висота дерев з n вузлами буде O(log n).
Види дерев
Двійкове дерево пошуку
Бінарне дерево пошуку — це структура даних на основі вузлів, де кожен вузол містить ключ і два піддерева, лівий та правий. Для всіх вузлів ключ лівого піддерева повинен бути меншим ніж ключ вузла, а ключ правого піддерева повинен бути більшим ніж ключ вузла. Усі ці піддерева повинні бути двійковими деревами пошуку.
Найгірша часова складність операції пошуку у двійковому дереві пошуку — це висота дерева, яка може бути такою ж малою, як O (log n) для дерева з n елементами.
Б-дерево
Б-дерева — це узагальнення двійкових дерев пошуку, оскільки будь-який вузол у такому дереві може мати змінну кількість піддерев. Хоча вузли-діти мають заздалегідь визначений розмір(порядок), вони не обов'язково будуть заповнені даними, тобто Б-дерева можуть потенційно займати місце в пам'яті, але не використовувати його. Перевага полягає в тому, що Б-дереву не потрібно перебалансовуватися так часто, як іншим самобалансованим деревам.
Завдяки змінному розміру вузла, Б-дерева оптимізовані для систем, які зчитують великі блоки даних. Вони також часто застосовуються в базах даних.
Часова складність операції пошуку в Б-дереві становить O (log n).
(а, б)-дерево
(а, б)-дерево — це дерево пошуку, в якому всі його листя мають однакову глибину. Кожен вузол має, щонайменше а дітей та щонайбільше б дітей, в той час як корінь має щонайменше 2 дітей і щонайбільше б дітей.
Часова складність пошуку в (a, b)-дереві становить O (log n).
Трійкове дерево пошуку
Трійкове дерево пошуку — це дерево, в якому кожен вузол зберігає один символ, а саме дерево упорядковується так само, як і двійкове дерево пошуку, за винятком можливого третього вузла.
Пошук у трійковому дереві пошуку передбачає передачу стрічки, щоб перевірити, чи містить її якийсь шлях.
Часова складність операції пошуку в збалансованому трійковому дереві пошуку дорівнює O (log n).
Джерела
- Thomas H. Cormen, Charles E. Leiserson. Introduction to algorithms.