Структуры данных

BST: Дерево поиска

Цели урока

  • Понять BST свойство: левые < корень < правые
  • Реализовать поиск за O(log n)
  • Реализовать вставку и удаление
  • Понять проблему баланса

Предварительные знания

  • Бинарные деревья
  • Введение в деревья

Представьте телефонный справочник с миллионом контактов. Как найти нужный за доли секунды? BST - это та же идея, что в бинарном поиске, но встроенная в структуру данных.

  • Индексы в базах данных
  • Словари и множества в языках программирования
  • Файловые системы (поиск файлов)
  • Автодополнение в поиске

Изобретение бинарного дерева поиска

Идея хранить ключи в дереве так, чтобы слева лежали меньшие, а справа большие, оформилась на рубеже 1950-1960-х. Около 1960 года П. Ф. Уиндли, а также Эндрю Бут и другие описали вставку в такое дерево как способ одновременно сортировать и индексировать данные. Недостающий кусок добавил Томас Хиббард в 1962 году: он дал корректный алгоритм удаления узла с двумя детьми через замену на преемника (или предшественника), и этот приём мы используем до сих пор. Уже тогда было понятно, что при случайных вставках операции стоят в среднем O(log n), но на отсортированном входе дерево вырождается в список с O(n). Именно эта слабость подтолкнула к созданию самобалансирующихся деревьев из следующего урока.

BST свойство: Левые < Корень < Правые

**BST (Binary Search Tree)** - бинарное дерево с правилом:

Для каждого узла: все значения в **левом** поддереве **меньше** узла, все в **правом** - **больше**.

Какое дерево является BST? A) 5 B) 5 / \ / \ 3 7 3 7 / / \ 4 2 6

Поиск: O(log n)

Поиск в BST - как бинарный поиск: на каждом шаге отсекаем половину.

**O(log n)** - только для сбалансированных BST! Для вырожденных (линейных) - O(n).

BST с 1000 узлов, сбалансированное. Максимум сколько сравнений для поиска?

Вставка: найди место и добавь

Вставка похожа на поиск: идём по дереву, пока не найдём пустое место.

Новый узел всегда становится **листом** - мы не переставляем существующие узлы.

После вставки в BST новый узел будет:

Удаление: три случая

Удаление сложнее - нужно сохранить BST свойство. **Три случая:**

При удалении узла с двумя детьми мы:

Проблема баланса

BST отлично работает... пока сбалансирован.

Форма дереваПоискПример
СбалансированноеO(log n)Случайные вставки
ВырожденноеO(n)Отсортированные вставки

**Решение:** самобалансирующиеся деревья (AVL, Red-Black) автоматически поддерживают баланс.

Что происходит при вставке отсортированных данных в BST?

BST операции

  • BST: левые < корень < правые
  • Поиск: O(log n) - бинарный поиск в дереве
  • Вставка: O(log n) - новый узел всегда лист
  • Удаление: 3 случая, O(log n)
  • Вырожденный BST = список = O(n)

Следующие темы

Чтобы решить проблему баланса, используются самобалансирующиеся деревья.

  • AVL и Red-Black — Автоматическая балансировка

Связанные уроки

  • ds-09-trees-intro — BST adds ordering invariant on top of general tree
  • ds-10-tree-traversals — In-order traversal is the natural BST sorted scan
  • ds-12-balanced-trees — Balanced BSTs fix the degeneration problem of naive BST
  • ds-06-hash-intro — Hash map vs BST - O(1) vs O(log n) with ordering tradeoff
  • comp-17-symbol-table
  • db-09-indexes-btree
BST: Дерево поиска

0

1

Войти