Какова средняя асимптотическая глубина простого несбалансированного дерева поиска?

Question

Для сбалансированного дерева поиска это O (log (N)) для всех случаев. Для несбалансированных деревьев поиска наихудшим случаем является O (N), например, вставка 1, 2, 3, 4, .., а сложность наилучшего случая - это когда он сбалансирован, например, вставка 6, 4, 8, 3, 5 7 Как определить среднюю сложность случая для несбалансированного дерева поиска?

Answer 1

Средняя высота бинарных деревьев - тета (sqrt (n)).Это было показано (или указано, не очень точно) в следующей статье: http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf.

Но, возможно, вас больше интересует средняя глубина случайного узла, а это тета (log n), так какможно увидеть здесь: http://www.toves.org/books/data/ch05-trees/index.html (раздел 5.2.4).