Почему произвольное двоичное дерево не может быть преобразовано в BST только с помощью вращения двоичного дерева?

Question

Я не понимаю, почему второе утверждение неверно: «Произвольное двоичное дерево может быть преобразовано в двоичное дерево поиска». Каковы примеры BT, которые не могут быть преобразованы в BST после стольких вращений двоичного дерева, сколько необходимо?

Answer 1

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