Структуры данных и модели вычислений
Случайные двоичные деревья поиска
Поскольку основные операции с двоичными деревьями поиска требуют времени , где — высота дерева, важно знать, какова высота "типичного" дерева. Для этого принимают какие-то статистические предположения о распределении ключей и последовательности выполняемых операций. К сожалению, в общем случае ситуация трудна для анализа. Если определить случайное двоичное дерево из различных ключей как дерево, получающееся из пустого дерева добавлением этих ключей в случайном порядке, считая все перестановок равновероятными, то можно доказать, что средняя высота случайного двоичного дерева поиска, построенного по различным ключам, равна.
