Понимание двоичного поиска Дерево построения

Question

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

Answer 1

форма, что бинарное дерево поиска занимает зависит от двух вещей:

1. Порядка, в которые вставляются элементы и
2. Каких балансовые операции, если таковые имеются, то дерево делает во время установки.

Если у вас есть чисто двоичное дерево поиска без логики балансировки, то порядок, в который вставлены элементы, окажет сильное влияние на форму дерева. Например, возьмите значения 1, 2, 3, 4, 5, 6, 7. Если вы вставляете их в порядке 4, 2, 6, 1, 3, 5, 7, вы получите это дерево:

 4 
    / \ 
    2  6 
    /\ /\ 
    1 3 5 7 

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

 4 

    4 
/
    2 

    4 
/ \ 
    2  6 

    4 
/ \ 
    2  6 
/
1 

    4 
/ \ 
    2  6 
/\ 
1 3 

    4 
/ \ 
    2  6 
/\ /
1 3 5 

    4 
/ \ 
    2  6 
/\ /\ 
1 3 5 7 

с другой стороны, если вставить значения в порядке 1, 2, 3, 4, 5, 6 , 7, вы получите это дерево:

1 
\ 
    2 
    \ 
    3 
    \ 
     4 
     \ 
     5 
     \ 
      6 
      \ 
      7 

Интересно, что вставка элементов в BST в отсортированном порядке ne от худших вещей, которые вы можете сделать для дерева, так как это делает дерево линейной структурой. Вы лучше выбирать случайную перестановку элементов для вставки, или (если все они известны заранее) сортируя их и используя следующий рекурсивный алгоритм на отсортированной последовательности:

• Если нет никаких элементов, вы сделали.
• В противном случае:
  • Вставьте медиану в BST.
  • Рекурсивно вставьте первую половину элементов в BST.
  • Рекурсивно вставьте вторую половину элементов в BST.

Надеется, что это помогает!