Характеристики бинарных деревьев поиска

1. Упорядоченность

Бинарное дерево поиска может служить реализацией таблицы поиска.

Наша цель при использовании бинарного дерева поиска — сразу получать значение по ключу. Минимум, максимум, следующий, предыдущий, floor, ceil, rank (какой элемент имеет какой ранг) и select (какой элемент является n-м) — всё это проявления свойства упорядоченности бинарных деревьев поиска.

2. Ограничения

Бинарные деревья поиска имеют ограничения по временной производительности.

Как показано на рисунке ниже, из одних и тех же узлов можно построить два различных бинарных дерева поиска, и оба будут удовлетворять определению:

Бинарное дерево поиска может выродиться в связный список. Соответственно, операция поиска в бинарном дереве поиска связана с высотой дерева, и в этом случае высота дерева равна количеству его узлов n. При этом все соответствующие алгоритмы бинарного дерева поиска вырождаются до уровня O(n).

Другие расширения