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

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

Если я вставляю 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, а затем, как бы сделать необходимые вращения.

источник

2011-02-02 kachilous

Как вы определяете эти факторы баланса? Мне кажется, что вы делаете это неправильно. –

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

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

источник

2011-02-02 22:59:14 box

Я понимаю, как я просчитал коэффициент баланса, но меня немного смущает алгоритм cut-link. Когда я переименую узлы в a, b, c в порядке трансверсальности, это будет: a-5, b-10, c-12. Итак, тогда 10 будет корнем? – kachilous

Так z = 10, потому что 10 - неуравновешенный узел. По пути к вставленному узлу мы определяем y = 5 и x = 2. Остальные поддеревья T0 = 1, T1 = 4 | 3, T2 = 8 | 7 9 и T3 = 12 | 13. Затем мы пересекаем x, y и z по порядку. Итак, a = x, b = y, c = z. Мы устанавливаем b как новый корень поддерева, который равен 5. 2 - корень левой и 5 - корень правого поддерева. После добавления T0, T1, T2 и T3 мы получаем дерево сверху. Кстати: я должен был упомянуть о том, что при определении x, y и z необходимо следовать по пути к вставленному узлу. – box

хорошо спасибо! – kachilous

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

ответ

Смежные вопросы