Когда (см. рис. 7.4), необходимо рассмот-
реть еще один нижележащий уровень. На рис. 7.8 показано дерево, в котором но-
вый узел вставляется в левую часть Т2 поддерева LR. Он с той же вероятностью
может быть добавлен в правое поддерево Т3. В любом случае поддеревья ТА и Тс
удовлетворяют свойству AVL, а поддерево Тх - нет.
Так как дерево до вставки узла являлось AVL-деревом, ТА должно быть макси-
мум на один уровень длиннее, чем Т4. Был добавлен всего один узел, так что ТА
выросло всего на один уровень. Это означает, что ТА должно быть ровно на два
уровня выше Т4.
Также известно, что глубина Т2 максимум на единицу больше, чем глубина Т3.
Иначе Тс будет разбалансировано и узел X не будет самым нижним узлом в дере-
ве с разбалансированными поддеревьями.
Кроме того, поддерево Т, должно достичь той же самой глубины, что и Т3.
Если оно будет короче, ТА будет разбалансированным, а это снова противоречит
предположению, что узел X является самым нижним узлом в дереве с разбалан-
сированными поддеревьями. Если глубина поддерева Т( больше глубины Т3, то Т,
будет иметь глубину на 2 уровня больше, чем глубина Т4. В том случае дерево
было бы разбалансировано еще до добавления нового узла.
Следовательно, основания деревьев расположены в точности так, как показано
на рис. 7.8. Поддерево Т2 достигает самой большой глубины, Т1 и Т3 достигают глу-
бины на один уровень выше, а глубина Т4 на единицу превышает глубину Т1 и Т3.
Используя изложенные выше факты, можно перебалансировать дерево, как по-
казано на рис. 7.9. Это вращение называется влево-вправо, потому что узлы А и С
как бы сдвигаются на одну позицию влево, а узлы С и X - на одну позицию вправо.
Рис. 7.8. Добавление нового узла в поддерево LR
Рис. 7.9. Вращение влево-вправо
Это вращение так же не изменяет Порядка расположения элементов дерева.
Симметричный обход дерева до и после вращения происходит в порядке Т1, А, Т2,
С, Т3, X, Т4.
Глубина перебалансированного поддерева не изменилась. Перед добавлением
нового узла глубина поддерева была равна глубине поддерева Т1 плюс 2. После
того как дерево перебалансируется, глубина поддерева осталась той же. Это озна-
чает, что остальная часть дерева сбалансирована. Следовательно, нет необходимо-
сти продолжать балансировку дальше.
|
Главная
Каталог файлов
