AVL Вставка и балансировка петли
Я реализую AVL Trees в C ++ на своем собственном коде, но эта проблема больше понимание AVL деревья, а не сам код. Прошу прощения, если он здесь не подходит, но я полз через Интернет и до сих пор не нашел решения своей проблемы.
Мой код работает, как и ожидалось, с относительно небольшими входными данными (~ 25-30 цифр), поэтому я полагаю, что он должен работать больше. Я использую массив, в котором я храню узлы, которые я посетил во время вставки, а затем использую цикл while. Я поднимаю высоты каждого узла при необходимости, я знаю, что эта процедура должна закончиться когда я нахожу узел которого высоты равны (их результат вычитания равен 0).
Проблема в том, что касается балансировки. Пока я могу найти Баланс фактор каждого узла и правильно сбалансировать дерево Я не уверен, должен ли я прекратить регулировать высоту после балансировки и просто закончить цикл вставки или продолжайте, пока условие не будет указано, и я просто не могу понять это сейчас. Я знаю, что при удалении узла и повторной балансировке дерева я должен продолжать проверять, но я не уверен насчет вставки и балансировки.
Кто-нибудь может предоставить какое-либо понимание этого и, возможно, некоторую документацию?
Решение
Если вы вставляете только один элемент за раз: требуется только один (одинарный или двойной) поворот, чтобы перенастроить дерево AVL после того, как вставка вывела его из баланса. http://cis.stvincent.edu/html/tutorials/swd/avltrees/avltrees.html Вы можете, вероятно, доказать это самостоятельно после того, как знаете заключение.
Другие решения
Просто для справки будущих читателей есть нет нужно отредактировать высоту узлов над уравновешенным узлом, если вы реализовали двоичное дерево, как в моем примере:
10
(1)/ \(2)
8 16
(1)/ \(0)
11
(Numbers in parenthesis are the height of each sub tree)
Предположим, что на дереве выше мы вставляем узел с data=15 Тогда полученное поддерево выглядит следующим образом:
10
(1)/ \(2)
8 16
(1)/ \(0)
11
(0)/ \(1)
15
Обратите внимание, что предыдущие высоты поддеревьев еще не редактировались. После успешной вставки мы запускаем путь вставки, в данном случае его (11, 16, 10), После бега по этому пути мы редактируем высоты, когда это необходимо. Это означает, что оставленная высота поддерева 16 будет 2 пока это правильная высота поддерева 0 приводя к несбалансированному дереву AVL. После балансировки дерева с двойным вращением поддерево имеет вид:
15
(1)/ \(1)
11 16
Таким образом, высота поддерева, как и прежде, равна 1, поэтому высота над корнем этого поддерева не изменилась, и функция, изменяющая высоту, должна return сейчас.