Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2019-11-19 | 218 |
5.00
из
|
Заказать работу |
|
|
Если добавление нового узла, приводящее к разбалансировке, происходит в левое поддерево левого сына опорного узла или в правое поддерево правого сына опорного узла, т.е. если стороны сына и внука опорного узла одноименны, то необходимо произвести одинарный поворот. Если добавление происходит в правое поддерево левого сына опорного узла или в левое поддерево правого сына опорного узла, т.е. стороны разноименны, то необходимо произвести двойной поворот.
- добавление в левое поддерево левого сына опорного узла – правый (R);
- добавление в правое поддерево левого сына опорного узла – левый-правый (LR);
- добавление в левое поддерево правого сына опорного узла – правый-левый (RL);
- добавление в правое поддерево правого поддерева сына опорного узла – левый (L).
Простой поворот вправо (влево) производит следующую трансформацию дерева:
Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.
Анализ возможных случаев в рамках данной ситуации показывает, что для исправления разбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).
Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.
Удаление узла из АВЛ-дерева
Непосредственно удаление узла из АВЛ-дерева происходит так же, как и удаление узла из обычного двоичного дерева поиска. Если у узла менее двух сыновей, то удаляется сам узел, а если два сына, то удаляемым узлом становится его последователь, информация (ключ) из которого предварительно переписывается в удаляемый узел. Чтобы после удаления сохранились свойства АВЛ- дерева, возможно, понадобится выполнить балансировку. Для этого надо подниматься вверх по пути от удаленного узла к корню и проверять в этих узлах баланс. Если в узле баланс нарушен, то надо выполнить соответствующий поворот – одинарный или двойной. Остановить просмотр можно на том узле, в котором показатель баланса не поменялся. Это означает, что высота его поддерева, левого или правого, в котором производилось удаление, не изменилась. При балансировке после удаления используются те же виды поворотов, что и после вставки узла в дерево.
|
1. Левое поддерево стало ниже правого на 2 уровня.
a. У правого сына (B) высота правого поддерева больше, либо равна высоте левого поддерева (height(T3) ≥ height(T2)), необходимо произвести левый поворот (L): опорный узел (A) поворачивается налево относительно своего правого сына (B).
b. У правого сына (C) высота правого поддерева меньше вы- соты левого поддерева (height(T4) < height(B)). Необходимо произвести двойной поворот — направо, потом налево (RL): сначала правый сын опорного узла (C) поворачивается направо относительно своего левого сына (B), а затем опорный узел (A) поворачивается налево относительно своего нового правого сына (B).
Левое поддерево короче правого и (а) height(T3) > height(T2); (б) height(T3) = height(T2). Балансировка: левый поворот
2. Правое поддерево стало ниже левого на 2 уровня (случай, симметричный случаю 1).
a. У левого сына высота левого поддерева больше, либо равна высоте правого поддерева. Случай, симметричный случаю 1а.
b. У левого сына высота левого поддерева меньше высоты правого поддерева. Случай, симметричный случаю 1b
Правила удаления такие же, как при вставке: если самые глубокие узлы находятся справа или слева, то производится одинарный поворот опорного узла в противоположную сторону, а если они находятся посередине, то производится двойной поворот.
|
|
|
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!