Вставка AVL и балансировочная петля

Я реализую деревья AVL на C++ в своем собственном коде, но эта проблема больше связана с пониманием деревьев AVL, чем с самим кодом. Извините, если здесь не поместилось, но я перерыл весь интернет и так и не нашел решения своей проблемы.

Мой код работает, как и ожидалось, с относительно небольшими входными данными (~ 25-30 цифр), поэтому я полагаю, что он должен работать и для большего количества. Я использую массив, в котором я храню узлы, которые я посетил во время вставки, а затем, используя цикл while, я увеличиваю высоту каждого узла, когда это необходимо, я знаю, что эта процедура должна закончиться, когда я найти узел, высоты которого равны (то есть результат их вычитания равен 0).

Проблема в балансировке. Хотя я могу найти Коэффициент баланса каждого узла и правильно сбалансировать дерево, я не уверен, следует ли мне прекратить регулировку высоты после балансировки и просто завершить цикл вставки или продолжить идет до тех пор, пока не подразумевается условие, и я просто не могу понять это сейчас. Я знаю, что во время удаления узла и повторной балансировки дерева я должен продолжать проверять, но я не уверен насчет вставки и балансировки.

Кто-нибудь может дать какое-либо представление об этом и, возможно, какую-то документацию?


c++ algorithm avl-tree
person Theocharis K.    schedule 30.11.2012    source источник
comment
У вас есть доступ в Интернет только к этому сайту? как насчет дерева поиска AVL в Google? Вы получаете подробное объяснение с исходным кодом, как в моем обновленном посте.   -  person AlexWien    schedule 30.11.2012

Ответы (2)


arrow_upward
0
arrow_downward

Если вы вставляете только один элемент за раз: требуется только одно (одинарное или двойное) вращение для корректировки дерева AVL после того, как вставка выводит его из равновесия. http://cis.stvincent.edu/html/tutorials/swd/avltrees/avltrees.html Вероятно, вы сможете доказать это сами, когда узнаете вывод.

person digit plumber    schedule 30.11.2012
comment
Тем не менее, это не имеет никакого отношения к моему вопросу. Я знаю, что одного вращения достаточно, чтобы снова сделать его AVL, мой вопрос в том, что после того, как это вращение будет выполнено, мне нужно настроить высоту любого узла над повернутым узлом? - person Theocharis K.; 30.11.2012
comment
Да, вам нужно обновить высоты после поворотов. oopweb.com/Algorithms/Documents/AvlTrees/Volume/AvlTrees.htm - person digit plumber; 30.11.2012

arrow_upward
0
arrow_downward

Просто для справки будущим читателям: нет необходимости редактировать высоту узлов над узлом, который вы сбалансировали, если вы реализовали двоичное дерево, как в моем примере:

           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.

person Theocharis K.    schedule 11.01.2013