Сначала предположим, что новый узел добавляется к поддереву R на рис. 7.4.
В этом случае два правых поддерева узла X изменяться не будут, поэтому их мож-
но сгруппировать в один треугольник, как показано на рис. 7.5. Новый узел был
добавлен к дереву Т1, при этом поддерево ТА с корнем в узле А становится по край-
ней мере на два уровня длиннее, чем поддерево Т3.
Так как дерево перед добавлением узла было AVL-деревом, ТА должно быть мак-
симум на один уровень длиннее поддерева Т3. Вы добавили всего один узел к дереву,
поэтому ТА должно быть ровно на два уровня выше, чем поддерево Т3.
Также известно, что поддерево Т1, не более чем на один уровень выше поддере-
ва Т2. В противном случае узел X не был бы самым низким узлом в дереве с разба-
лансированными поддеревьями. Если бы поддерево Т1, было на два уровня выше
Т2, дерево было бы разбалансировано в узле А.
Вы можете поменять узлы местами с помощью правого вращения (right rotation),
как показано на рис. 7.6. Это вращение называется правым, поскольку узлы А и X
как бы сдвинуты на одну позицию вправо. Рис. 7.5. Добавление нового узла в поддерево R Рис. 7.6. Правое вращение
Обратите внимание, что это вращение сохраняет порядок расположения эле-
ментов дерева «меньше чем».Симметричный обход любого из этих деревьев про-
исходит таким образом: Т1, А, Т2, X, Т3.
Поскольку обход обоих деревьев происходит одинаково, то и порядок распо-
ложения элементов в них будет идентичным.
Также необходимо обратить внимание, что глубина поддерева, с которым вы
работаете, осталась той же самой. Перед добавлением нового узла глубина подде-
рева была равна глубине поддерева Т2 плюс 2. После добавления узла и примене-
ния правого вращения глубина поддерева не увеличивается. Любая часть дерева,
лежащая выше узла X, при этом остается сбалансированной, поэтому дальнейшая
балансировка не нужна.
Опубликовал Kest
October 23 2009 07:59:45 ·
0 Комментариев ·
10412 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
