@BRADFORD

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

Деталей, особо, нет. Весь вопрос указан в оглавлении. Интересуюсь потому, что такой вопрос вынесли на экзамен по теории алгоритмов.
  • Вопрос задан
  • 113 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Можно. Декартово дерево можно реализовать через split/merge. Даже если у вас нет второго ключа, то можно релизовать это храня высоты деревьев или вообще случайно решать, стоит ли вставлять элемент сюда (где вызывать split) и какая из двух вершин станет корнем поддерева при merge.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
mayton2019
@mayton2019
Bigdata Engineer
Давайте порассуждаем что такое вообще "поворот дерева". Это - метафора. Это изменение двух потомков двух узлов a и b. По сути это функция transform:
void transform(Node *a, Node *b) {....}
при этом (a,b) - состоят в отношении relatives. Родственники.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
19 июл. 2024, в 11:46
3000 руб./за проект
19 июл. 2024, в 11:31
2500 руб./в час
19 июл. 2024, в 11:30
2500 руб./в час