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

Question

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

Answer 1

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

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

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

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

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

Answer 2

Конвертировать двоичное дерево в двусвязный список - можно сделать на месте в O (n) Затем сортируйте с помощью сортировки слиянием, nlogn Преобразовать список обратно в дерево - O (n)

Простое решение nlogn.