Перебалансировка дерева AVL - PullRequest
Новая
       8

Перебалансировка дерева AVL

1 голос
/ 03 февраля 2011

У меня есть следующее дерево AVL: 

                               10
                             /    \
                            5     12
                           / \   /  \
                          2  8   11  13
                        /  \ /\   
                        1  4 7 9

Если я вставлю 3, то получу: 

                               10
                             /    \
                            5     12
                           / \   /  \
                          2  8   11  13
                        /  \ /\   
                        1  4 7 9
                          /
                         3

Если я вычисляю коэффициент баланса для каждого узла, кажется, что каждый BFдействителен: (Узел: BF) -> 10: 1, 5: 0, 2: -1, 1: 0, 4: -1, 8: 0, 7: 0, 9: 0, 3: 0, 12:0, 11: 0, 13: 0 Но, видимо, это дерево нуждается в восстановлении баланса.Где находится недопустимый BF, и как сделать необходимые повороты.

1 Ответ

1 голос
/ 03 февраля 2011

10 должен иметь коэффициент баланса 2 с левым поддеревом 5-2-4-3 и правым поддеревом 12-13. Действительное дерево после одного поворота может выглядеть как 5 | 2 10 | 1 4 8 12 | ноль ноль 3 ноль 7 9 11 13.

Возможный метод перебалансировки - алгоритм cut-link: 1. Назовите несбалансированный узел z, один из его дочерних y и один из дочерних x. 2. Переименуйте узлы в a, b, c в обходе по порядку и пусть их дочерние элементы будут T0, T1, T2 и T3 слева направо. 3. Установите b в качестве нового корня, a в качестве его левого дочернего элемента и c в качестве его правого дочернего элемента. 4. Добавьте четыре поддерева, соответствующие слева направо, как T0, T1, T2 и T3.

...