входное значение для создания бинарных деревьев поиска

Question

В бинарном дереве поиска. Если я введу «2,1,3,4,5», дерево будет похоже на

              2
              /\
              1 3
                 \
                  4
                   \
                    5

Но с вводом типа "5,2,1,3,7,6,8".

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

Итак, мой вопрос, как получить входные данные, чтобы получить подобную сбалансированную древовидную структуру? (Я не хочу использовать деревья AVL.) Есть ли у нас приемы для правильной сортировки или перестановки чисел и их вывода в качестве входных данных. Я ищу входные данные, чтобы дерево могло создать высоту до 10.

Answer 1

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

1. Вставить середину всего массива.
2. Рекурсивно вставьте левую и правую половинки массива, используя эту процедуру.

Например, в вашем случае значений 1 - 8 с удалением 5 вы бы отсортировали значение как

1 2 3 5 6 7 8

Затем вы должны вставить 5, а затем рекурсивно применить эту процедуру к двум половинкам. На половине 1 2 3 вы должны вставить 2, а затем рекурсивно вставить 1 и 3. Это дает порядок до

 5 2 1 3

Теперь вы рекурсивно обрабатываете другую половину, 6 7 8, которая вставляет 7, а затем рекурсивно вставляет 6 и 8. В целом, это создает порядок

5 2 1 3 7 6 8

Это именно тот порядок, который вы предложили ранее в своем посте.

Эта процедура выполняется за O (n lg n) времени. Я не уверен, что это оптимально, поэтому, если кто-то захочет опубликовать лучший ответ, я бы хотел его увидеть.