Как построить бинарное дерево поиска

Question

Я в настоящее время обучение бинарное дерево поиска, если вставить эти значения в мое дерево:

13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 

Тогда мой бинарное дерево поиска будет выглядеть следующим образом:

Если добавить еще один номер 15 к моему дереву:

13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18, 15 

Мой вопрос, является ли это первым один:

13 
    \ 
    14 
    \ 
    15 
     \ 
     18 

или второй один:

13 
    \ 
    14 
    \ 
     18 
    /
    15 

правильный способ вставить 15 в выше бинарного дерева поиска?

Answer 1

Второй выход является правильным, если вы «обычный» BST. Однако, если вы используете сбалансированные BST, то существует вероятность того, что он может перейти к перестановке относительного положения узлов в дереве. Я уверен, что книга (или ссылка), за которой вы следуете, должна иметь объяснение для такого вопроса. Как правило, при добавлении узла в предыдущую структуру (т. Е. Предыдущие позиции узлов) не вносили изменений. Однако это может привести к «неуравновешенным» или «перекошенным» деревьям. Это может привести к увеличению времени поиска для узла. Чтобы исправить эту проблему, используются «сбалансированные деревья», такие как красно-черное дерево, деревья avl и т. Д. В таких деревьях модификация древовидной структуры обычно выполняется при добавлении узла. Направить следующее для получения дополнительной информации:

https://en.wikipedia.org/wiki/Binary_search_tree?oldformat=true

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree?oldformat=true

Answer 2

Оба способа будут работать, но первый из них будет несовместимо с тем, как строится ваше текущее дерево.

В частности, обратите внимание на раздел 4-12-10:

4 
\ 
12 
/
10 

Уровень, при котором данные появляются в дереве фиксируется при вставке, и не меняется, поскольку все больше элементы будут добавлены. Вот почему второй подход - это то, что вы ищете.