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

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


tree binary-tree binary-search-tree binary-search
person Mooh    schedule 21.03.2011    source источник
comment
Что вы имеете в виду под «однородными» деревьями? Сбалансированные деревья?   -  person florin    schedule 22.03.2011
comment
Он имеет в виду, почему структура деревьев отличается, когда данные одинаковы.   -  person corsiKa    schedule 22.03.2011
comment
@glowcoder спасибо, это именно то, что я имею в виду   -  person Mooh    schedule 22.03.2011
comment
посмотрите на мой ответ - рассмотрите структуру дерева при каждой вставке и куда пойдет следующий элемент. Вы увидите, что без какой-либо перебалансировки добавление элементов в отсортированном порядке приводит к очень плохо оптимизированному дереву!!   -  person corsiKa    schedule 22.03.2011

Ответы (2)


arrow_upward
3
arrow_downward

Многое зависит от реализации дерева. Это самобалансировка? Рассмотрим простые деревья 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
person corsiKa    schedule 21.03.2011

arrow_upward
1
arrow_downward

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

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

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

person Ingo    schedule 21.03.2011