Бинарное преобразование дерева с использованием поворотов
Пока я изучал среднесрочные вопросы о двоичных деревьях, я нашел утверждение, что любое произвольное двоичное дерево с n-узлами может быть преобразовано в любое другое двоичное дерево с n-узлами с максимум 2*n-2 поворотами. Есть ли доказательства этому? Я нашел какое-то доказательство с асимптотическими обозначениями, но это было не так ясно. Я имею в виду, может кто-то объяснить / показать, почему это правда? И если он говорит, что двоичное дерево n-узла, включает ли оно корень?
2 ответа
Этот ответ взят из CLRS 3-е издание учебника вопрос 13.2-4.
Позволять
LEFT = бинарное дерево всего левого связного списка
ВПРАВО = бинарное дерево всего связанного справа списка
Вы можете легко повернуть ВЛЕВО в ПРАВО в (n-1) оборотах.
например: n = 3
3 2 1
От 2 до 1 от 3 до 2
1 3Доказательство: поскольку по определению каждое правое вращение будет увеличивать длину самого правого пути как минимум на 1. Поэтому, начиная с самого правого пути с длиной 1 (наихудший случай), вам нужно максимально (n-1) поворотов, выполненных для сделать это в право.
Таким образом, вы можете легко сделать вывод, что любая произвольная форма двоичного дерева с n узлами может повернуться в ПРАВО в течение (n-1) поворотов. Пусть T_1 будет узлом, которым вы начинаете. Пусть T_2 будет узлом, которым вы заканчиваете.
Вы можете повернуть T_1 вправо в течение (n-1) поворотов. Точно так же Вы можете повернуть T_2 к ПРАВО в пределах (n-1) поворотов.
Поэтому, чтобы повернуть T_1 в T_2, просто поверните T_1 в ПРАВО, а затем выполните обратное вращение, чтобы повернуть из ПРАВА в T_2.
Следовательно, вы можете сделать это в (n-1)+(n-1) = 2n-2 вращениях в верхней границе.
Надеюсь, это поможет!=) Вскоре Чи Лунг, Университет Торонто
Если утверждение относится к бинарным деревьям, а не к деревьям BST, я думаю, что это утверждение допустимо, поскольку нет ограничений на порядок узлов. И простая математическая индукция должна доказать утверждение.