Основной характеристикой эффективности использования бинарных деревьев поиска является средняя длина пути до идентификатора:
Линейное | Не сбалансированное | Сбалансированное | AVL-дерево | |
MIN | ||||
AVG | ||||
MAX | не определен | 1,44 |
Для идеально-сбалансированного дерева количество элементов с высотой соотносятся следующим образом: