Создание двоичного дерева поиска с наименьшей глубиной

Question

У меня есть число от 1 до 31, и мне нужно создать двоичное дерево поиска с этими числами с наименьшей глубиной. Я думал о разделении 31/2 и создании моего корня. После этого разделение 16/2 и вставка 8 следующего, но это, похоже, не работает. Есть ли алгоритм, чтобы знать, в каком порядке вставлять числа, чтобы дерево могло иметь наименьшую глубину?

Answer 1

Если у вас есть номера 1-31, 31 номера, вы хотите, чтобы 15 номеров слева от корня и 15 номеров справа.
Итак, корень 16 (что не 31/2, а 31/2 + 1).

Повторяя ту же процедуру, левое поддерево имеет 15 элементов, поэтому вам нужно семь чисел с каждой стороны этого поддерева.
Итак, корень левого поддерева равен 8 (это 15/2 + 1, здесь есть шаблон).
Аналогичный расчет дает корень правого поддерева.

И так далее.