В настоящее время я изучаю структуру данных с помощью C++. Я понимаю, как можно сбалансировать двоичное дерево поиска при вставке новых узлов.
Однако что, если у вас уже есть вырожденное дерево (единственный список ссылок), и вы хотите сбалансировать его, не создавая новое дерево? В заключение, как мне собрать вырожденное дерево в полное, используя существующие узлы? (ИСПОЛЬЗУЕМ методы ВРАЩЕНИЯ)
Например, мои узлы содержат данные (9 узлов): 1, 3, 6, 9, 12, 15, 18, 21, 24
Для этого мне нужен толчок. Я даже не знаю, с чего начать .. Я ценю вашу помощь.
Вырожденное дерево - это просто отсортированный связанный список. Найдите средний элемент списка, удалите начало списка перед серединой и прикрепите его слева от среднего элемента. Теперь у вас есть средний элемент в качестве корня и два вырожденных дерева (связанных списков) с каждой стороны. Повторяйте эту процедуру рекурсивно для каждой стороны.
Я забыл важную часть. Как бы вы использовали вращения для создания полного дерева?