Можно ли сбалансировать бинарное дерево поиска без использования поворотов дерева?

Question

[BRADFORD]

Деталей, особо, нет. Весь вопрос указан в оглавлении. Интересуюсь потому, что такой вопрос вынесли на экзамен по теории алгоритмов.

Comments

[Akina]

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

Answer 1

[Wataru]

Можно. Декартово дерево можно реализовать через split/merge. Даже если у вас нет второго ключа, то можно релизовать это храня высоты деревьев или вообще случайно решать, стоит ли вставлять элемент сюда (где вызывать split) и какая из двух вершин станет корнем поддерева при merge.

Comments

[mayton2019]

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

[Wataru]

mayton2019, Если свапать только 2 ключа, то нарушится свойство дерева поиска. Поэтому обычно используют именно повороты. Тут не тоько ключи меняются местами, но и стуктура дерева.

Ну, и конечно, вопрос в скорости этого процесса. Так-то, очевидно, что всегда можно вообще все дерево разобрать на элементы и потом из них собрать новое, идеально сбалансированное дерево.

[mayton2019]

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

Answer 2

[mayton2019]

Давайте порассуждаем что такое вообще "поворот дерева". Это - метафора. Это изменение двух потомков двух узлов a и b. По сути это функция transform:
void transform(Node *a, Node *b) {....}
при этом (a,b) - состоят в отношении relatives. Родственники.

Далее можно детализовать левый и правый поворот но сигнатура - таже самая. Звучит вопрос - можем ли мы сбалансировать дерево без использования такого шаблона разработки?