Случайное двоичное дерево поиска

Question

У меня есть BST, где я случайно вставляю ключи от 1 ... n (каждая перестановка выполняется с вероятностью 1 / n!) . мой вопрос, почему результирующие деревья не являются однородными , даже если перестановка однородна ?

Answer 1

Многое зависит от реализации дерева. Это самобалансировка? Рассмотрим простые деревья 1 2 3 и 3 2 1

Very simple tree:
add 1

1

add 2


1
 \
  2

add 3

 1
  \
   2
    \
     3

, затем 3 2 1

добавить 3

3

add 2


  3
 /
2

add 1

     3
    /
   2
  / 
 1

Сейчас делаю 2 3 1

2

2
 \
  3


  2
 / \
1   3

Answer 2

бинарное дерево поиска - это не просто единое дерево поиска ... дерево строится в том порядке, в котором в нем сохраняются новые значения. как уже показал световой кодер, это не гарантирует однородность ...

равномерное распределение случайных чисел не гарантирует порядок значений, который является оптимальным для построения двоичного дерева

для поиска минимальных усилий через двоичное дерево, дерево должно регулярно перестраиваться. Обычно это происходит в нерабочее время, когда алгоритм может прочитать все дерево в связанный список, а затем из этого списка построить новое дерево с оптимальной однородностью