Примеры применения двоичного дерева поиска

Сортировка

Бинарное дерево поиска может быть использовано для реализации простого алгоритма сортировки. Как и в случае с heapsort, мы вставляем все значения, которые мы хотим отсортировать, в новую упорядоченную структуру данных - в данном случае это двоичное дерево поиска - и затем перемещаемся по порядку.

Наихудшее время для build_binary_tree - O(n*n) - если вы передаете ему отсортированный список значений, он объединяет их в связанный список без левых поддеревьев. Например, build_binary_tree ([1, 2, 3, 4, 5]) выдает дерево (1 (2 (3 (4 (5)))))).

Есть несколько схем для преодоления этого недостатка с помощью простых бинарных деревьев; наиболее распространенным является самобалансирующееся двоичное дерево поиска. Если эта же процедура выполняется с использованием такого дерева, общее время наихудшего случая составляет O(n log n), что является асимптотически оптимальным для сортировки сравнения. На практике добавленные издержки во времени и пространстве для сортировки на основе дерева (особенно для распределения узлов) делают его уступающим другим асимптотически оптимальным сортировкам, таким как heapsort для сортировки статического списка. С другой стороны, это один из наиболее эффективных методов добавочной сортировки, добавление элементов в список с течением времени при постоянной сортировке списка.

Операции с приоритетной очередью

Деревья двоичного поиска могут служить приоритетными очередями: структурами, которые позволяют вставлять произвольный ключ, а также искать и удалять минимальный (или максимальный) ключ. Вставка работает как объяснено ранее. Find-min идет по дереву, следуя указателям влево, насколько это возможно, не ударяя по листу:

// Условие: T не является листом дерева
function find-min(T):
    while hasLeft(T):
        T ? left(T)
    return key(T)

Find-max аналогичен: следуйте правым указателям, насколько это возможно. Delete-min (max) может просто найти минимум (максимум), а затем удалить его. Таким образом, и вставка, и удаление занимают логарифмическое время, так же, как в двоичной куче (binary heap), но в отличие от двоичной кучи и большинства других реализаций очереди с приоритетами, одно дерево может поддерживать все функции find-min, find-max, delete-min и одновременно delete-max, что делает бинарные деревья поиска подходящими в качестве двусторонних очередей с приоритетами.

---

Читайте также:

• Структуры данных: двоичное дерево поиска
• Операции с двоичным деревом поиска: поиск
• Операции с двоичным деревом поиска: обход