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

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