О.В. Сенюкова - Сбалансированные деревья поиска (1113408), страница 4
Текст из файла (страница 4)
*/2 left[x] ← right[y]3 if right[y] ≠ NULL then4parent[right[y]] ← x/* В строках 5–11 отсоединяем x от его родителя и присоединяему вместо x. */205 parent[y] ← parent[x]6 if parent[x] = NULL then7root[T] ← y8 else if x = right[parent[x]] then9right[parent[x]] ← y10 else11left[parent[x]] ← y/* Соединяем x и y. */12 right[y] ← x13 parent[x] ← yxT3yT1xT3yT2T1yT1xT2T2T3Рис. 13.
Иллюстрация функции TREE-ROTATE-R(T, x)2. Добавление в правое поддерево правого сына опорного узла.Случай, симметричный предыдущему.+2A+1 B0Bh0T1AhT3T3h+1T2hT1XT2X(а)(б)Рис. 7. Добавление узла в правое поддерево правого сынаопорного узла и балансировка – левый поворот213. Добавление в правое поддерево левого сына опорного узла.Необходимо произвести двойной поворот — налево, потом направо (LR): сначала левый сын опорного узла (A) поворачиваетсяналево относительно своего правого сына (B), а затем опорныйузел (C) поворачивается направо относительно своего нового левого сына (B).C-2CA +1-2BB -2-1 BA0A00C+1hhh-1T4T4hT3h-1T1T1X0T2T3T10XhhT2hT3hT2T40XРис.
8. Добавление узла в правое поддерево левого сына опорногоузла и балансировка – левый-правый поворотНа Рис. 8(а) правым поддеревом левого сына опорного узла является поддерево с корнем в B. При этом узел X может быть добавлен как в поддерево Т2, так и в поддерево Т3 – тип поворота прибалансировке от этого не изменится. Если до добавления узла X вправое поддерево узла A это правое поддерево было пусто, то вроли В выступает сам узел X. В результате двойного поворота узелB окажется наверху комбинации узлов ABC.
За один поворот этосделать нельзя, потому как в начальный момент узел B являетсясамым нижним в комбинации ABC. Поэтому первый поворот (Aотносительно B налево) поднимает B на один уровень вверх относительно С, а второй поворот (C относительно B направо) поднимает B еще на один уровень вверх относительно C. В итоге, слевау B окажется A с поддеревом Т1, а справа у B окажется C с поддеревом Т4. Высоты поддеревьев Т1 и Т4 совпадают.
Поддерево Т2 сузлом X и поддерево Т3 в соответствии со свойствами дерева поиска прикрепятся к узлам A и C соответственно. Поскольку их вы22соты отличаются от высот Т1 и Т4 не более, чем на 1, баланс вовсех узлах – A, B, C – по модулю не превысит 1.
Баланс в B будетравен 0.TREE-ROTATE-LR(T, x)/* На вход подается дерево T и опорный узел x. */1 TREE-ROTATE-L(T, left[x])2 TREE-ROTATE-R(T, x)4. Добавление в левое поддерево правого сына опорного узла.Случай, симметричный предыдущему.+2A-2-1AC-2 BB +100C-1B0AChhT1h-1T1hT2h-1T4T3T40XX0T2T3T1hT3hhT2T4X0Рис. 9. Добавление узла в левое поддерево правого сына опорногоузла и балансировка – правый-левый поворотЧтобы проще было запомнить, как производится двойной повороти не выписывать промежуточное дерево, достаточно обратитьвнимание на вращение комбинации из трех узлов.
Эта комбинациявключает в себя опорный узел и корни тех поддеревьев, куда добавился новый узел, нарушивший баланс. Если, например, добавляем узел в левое поддерево правого сына опорного узла, то комбинация будет состоять из опорного узла, правого сына опорногоузла и левого сына правого сына опорного узла.
Тот узел, которыйбыл самым нижним в этой комбинации, после двойного поворотастановится самым верхним, независимо от того, выполняется правый-левый поворот или левый-правый (см. Рис. 10).23C -2A +1BB-1A00C+1hT4hh-1T1T2T3hhT3hT2T1XT400X(а)+2A-1+1C0B-1B0AChT1hh-1T4T3T2T3T10XhhT2T4X0(б)Рис. 10. Двойной поворот: самый нижний узел в «треугольнике»становится самым верхним (обозначен ромбиком):(а) левый-правый поворот; (б) правый-левый поворотРезюмируя правила поворотов при выполнении операции балансировки АВЛ-деревьев, отметим общее правило: если добавлениенового узла, приводящее к разбалансировке, происходит в левое24поддерево левого сына опорного узла или в правое поддерево правого сына опорного узла, т.е.
если стороны сына и внука опорногоузла одноименны, то необходимо произвести одинарный поворот.Если добавление происходит в правое поддерево левого сынаопорного узла или в левое поддерево правого сына опорного узла,т.е. стороны разноименны, то необходимо произвести двойной поворот. Мнемоническое правило для запоминания того, в какуюсторону производится поворот: добавление в левое поддерево левого сына опорного узла –правый (R); добавление в правое поддерево левого сына опорного узла– левый-правый (LR); добавление в левое поддерево правого сына опорного узла– правый-левый (RL); добавление в правое поддерево правого поддерева сынаопорного узла – левый (L).Определение 2: Глубина узла равна длине простого пути от корня до этого узла.Таким образом, поворот производится в противоположную сторону.
Визуально это правило выглядит так, что если самый глубокийузел (тот, который был добавлен последним) находится слева илисправа, то производится одинарный поворот опорного узла относительно поддерева, содержащего этот узел, в противоположнуюсторону, чтобы выровнять высоты. Если самый глубокий узелнаходится посередине, то потребуется двойной поворот.Ниже приведена реализация операции вставки узла в АВЛ-деревочерез вспомогательную процедуру восстановления баланса.AVL-RESTORE-BALANCE(T, x)/* На вход подается дерево T и узел x, в котором надо восстановить баланс, если он был нарушен. */1 if balance[x] < –1then /* у узла x высота левого поддерева больше высоты правого поддерева */252if height[left[left[x]]] > height[right[left[x]]] then /* самыйглубокий узел слева */3TREE-ROTATE-R(T, x)4else /* самый глубокий узел посередине */5TREE-ROTATE-LR(T, x)6 if balance[x] > 1 then /* у узла x высота правого поддеревабольше высоты левого поддерева */7if height[right[right[x]]] > height[left[right[x]]] then /* самыйглубокий узел справа */8TREE-ROTATE-L(T, x)9else /* самый глубокий узел посередине */10TREE-ROTATE-RL(T, x)AVL-INSERT(T, x)/* На вход подается дерево T и узел x, который надо добавить вдерево.
*/1 TREE-INSERT(T, x)/* Поскольку мы не знаем, где именно находится опорный узел, встроках 2–5 проходим по всем узлам, лежащим на пути от x ккорню, и вызываем процедуру восстановления баланса. */2 current ← x3 while current ≠ NULL do4AVL-RESTORE-BALANCE(T, current)5current ← parent[current]3.2 Удаление узла из АВЛ-дереваНепосредственно удаление узла из АВЛ-дерева происходит так же,как и удаление узла из обычного двоичного дерева поиска, в соответствии с алгоритмом, описанном в Разделе 2.3. Таким образом,если у узла менее двух сыновей, то удаляется сам узел, а если двасына, то удаляемым узлом становится его последователь, информация (ключ) из которого предварительно переписывается в удаляемый узел. Чтобы после удаления сохранились свойства АВЛдерева, возможно, понадобится выполнить балансировку. Для это26го надо подниматься вверх по пути от удаленного узла к корню ипроверять в этих узлах баланс.
Если в узле баланс нарушен, тонадо выполнить соответствующий поворот – одинарный илидвойной. Остановить просмотр можно на том узле, в котором показатель баланса не поменялся. Это означает, что высота его поддерева, левого или правого, в котором производилось удаление, неизменилась.При балансировке после удаления используются те же виды поворотов, что и после вставки узла в дерево. Рассмотрим, как определить тип поворота. На иллюстрациях ниже показано, какой поворотвосстановит баланс в ближайшем разбалансированном узле к удаляемому (опорном узле). Используя эти правила, можно будет определять тип поворота и при подъеме наверх по дереву, если баланс вродителях будет нарушаться после текущей балансировки.Правила выполнения поворотов при удалении узла из АВЛ-дереваследующие.1. Левое поддерево стало ниже правого на 2 уровня.a.
У правого сына (B) высота правого поддерева больше, либо равна высоте левого поддерева (height(T3) ≥ height(T2)),Необходимо произвести левый поворот (L): опорный узел (A) поворачивается налево относительно своего правого сына (B).b. У правого сына (C) высота правого поддерева меньше высоты левого поддерева (height(T4) < height(B)).Необходимо произвести двойной поворот — направо, потом налево (RL): сначала правый сын опорного узла (C) поворачиваетсянаправо относительно своего левого сына (B), а затем опорныйузел (A) поворачивается налево относительно своего нового правого сына (B).Поддерево с корнем в B должно иметь высоту h+1.
При этом высоты поддеревьев T2 и T3 могут быть равны h, а могут различатьсяна 1: либо h и h-1, либо h-1 и h.27A +2+1 BB0hAh+1T10h+2h+1T2T3hT3T1T2(а)A +20BB-1hAT1+1h+2h+1T3T3hT2h+1T1T2(б)Рис. 11. Левое поддерево короче правого и(а) height(T3) > height(T2); (б) height(T3) = height(T2).Балансировка: левый поворот28A +2C -1B0hBT1+1A0C0h+2T4T3T1hhT2T2T3T4Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
