Сбалансированное бинарное дерево из отсортированного массива

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

Сперва стоит определиться с понятиями.

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

Пример бинарного дерева поиска

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

Сбалансированное оно, видимо, потому что в таком дереве в среднем требуется наименьшее количество операций для поиска.

Чтобы дерево имело минимальную высоту, количество узлов левого и правого поддеревьев должны максимально приближаться друг к другу. Построим дерево по этому принципу: середина каждого подраздела массива становится корневым узлом, а левая и правая части — соответствующими для него поддеревьями. Т.к. массив отсортирован, то полученное дерево соответствует определению бинарного дерева поиска.


Каким образом реализовать алгоритм?

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

Этот способ не слишком эффективен — обход дерева требует O(log N) операций, чтобы вставить каждый узел потребуется O(n * log N) времени.

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

Алгоритм получился примерно такой:

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

Реализация получилась довольно простой. Единственное на что нужно обратить внимание — смещение на единицу при выборе границ частей массива.


Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.