Двоичное дерево в двоичное дерево поиска (BST)

Question

Как вы можете преобразовать двоичное дерево в двоичное дерево поиска с дополнительным пространством O (1)?

Answer 1

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

Вот наивная реализация, которая должна удовлетворять вашим критериям, я не буду описывать действительные шаги, которые вы должны выполнить, только общий алгоритм.

1. Grab случайный лист узел из существующего дерева
2. Unlink узла листа из существующего дерева
3. Сделать Узел корень вашего нового бинарного дерева поиска
4. захватить другой случайный лист узел с вашим существующее дерево
5. Unlink этого узла из существующего дерева
6. Найдите правильное место для, и связать узел, в новое бинарное дерево поиска
7. Повторите шаг 4-6 до тех пор, пока исходное дерево не станет пустым

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

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

Answer 2

Преобразование двоичного дерева в двусвязном list- можно сделать Inplace в O (N) Затем сортировать его с помощью сортировки слияния, NlogN Преобразовать список обратно в дерево - О (п)

Простого NlogN решение.