О.В. Сенюкова - Сбалансированные деревья поиска (1113408), страница 7
Текст из файла (страница 7)
В первых трех случаях предполагается, что брат B узлаN черный. При этом отец F и сыновья брата CL и CR могут иметьлюбые цвета. Наиболее простой случай, когда F красный, а CL и43CR – черные (случай 1). Тогда не требуется поворота, а понадобится только перекраска. В случае 2 предполагается, что у B красный правый сын CR. В этом случае потребуется и перекраска, иповорот. Случай 3, когда правый сын черный, а левый – красный, спомощью перекраски и поворота сводится к случаю 2.
Когда братB узла N красный, его сыновья CL и CR и отец F могут быть только черными, следовательно, этому условию соответствует толькоодин случай (4), и он сводится к предыдущим трем случаям с помощью перекраски и поворота. В последнем случае, когда все узлы комбинации черные, можно будет только уровнять количествочерных узлов в путях, идущих от F налево и направо, перекрасивбрата B узла N в красный цвет, и продолжить процедуру восстановления свойства 4 КЧ-деревьев наверх.1. Отец F узла N красный, остальные узлы черные. Эта конфигурация является наиболее простой для восстановления свойствКЧ-дерева.
Достаточно просто перекрасить узлы F и B в противоположные цвета, после чего количество черных узлов в путях,идущих через F налево, увеличится на один. Количество черныхузлов в путях, идущих через F направо при этом не изменится, каквидно из Рис.
19. Поэтому, все пути будут содержать одинаковоеколичество черных узлов.FFNT1BT2T3NCLCRT4 T5T6T1BT2T3CLCRT4 T5T6Рис. 19. Отец F узла N красный: перекраска B и F2. Брат B узла N черный, а его правый сын CR красный. Вэтом случае, независимо от того, является ли F черным или красным, свойства КЧ-дерева восстанавливаются после поворота F вокруг B, перекраски CR в черный цвет и обмена цветами F и B.Действительно, если F был черным, то и B станет черным, поэтому44после поворота количество черных узлов слева увеличится наодин, а справа не изменится, потому что CR перекрашивается вчерный цвет. Если же F был красным, то количество черных узловслева все равно увеличится на один, потому что после поворота Fперекрашивается в черный цвет.
А справа количество черных узлов не изменится, потому что B станет красным.МеняемместамицветаFNT1BBT2T3FCLCRT4 T5T6T1CRNCL T5T2 T3T4T6Рис. 20. Брат B узла N черный и его правый сын красный: поворотF вокруг B, перекраска CR и обмен цветами F и B3. Брат B узла N черный, его правый сын CR черный, а левыйсын CL красный. Этот случай сводится к предыдущему, если повернуть левого сына CL относительно своего отца F так, чтобыподдерево B со своими сыновьями вытянулось в одну линию, иперекрасить CL и B. Тогда у N будет черный брат с красным правым сыном.4. Брат B узла N красный.
В этом случае F, CL и CR могут бытьтолько черными. За один шаг восстановить свойства КЧ-деревапри данной конфигурации невозможно. Но при помощи поворотаF налево вокруг B и перекраски F и B в противоположные цветаможно свести этот случай к тем, когда брат узла N черный, то естьк первым трем случаям. Из Рис. 22 видно, что после поворота иперекраски количество черных узлов во всех путях не изменится.Действительно, слева добавился красный узел, а справа удалился.45FFNT1BT2NCLT3T1CRT4 T5CLT2T3BT6T4 CRT5T6Рис.
21. Брат B узла N черный, его левый сын красный, а правый –черный: поворот CL вокруг B, перекраска CL и BFBNT1BT2T3FCLCRT4 T5T6T1CRNCL T5T2 T3T4T6Рис. 22. Брат B узла N красный: поворот F вокруг Bи перекраска F и B5. Все узлы комбинации (брат B, его дети CL и CR, а такжеотец F узла N) черные. В этом случае для того, чтобы уравнятьколичество черных узлов в путях, идущих от P налево и направо,достаточно перекрасить B в красный цвет.
Тогда справа станет наодин черный узел меньше. Но при этом необходимо учесть, что уF могут быть предки, а количество черных узлов во всех путях,проходящих через F, сократилось, поэтому оно будет меньше, чемв путях, проходящих, например, через брата F, если таковой имеется. Следовательно, если F не является корнем всего дерева, нужно продолжить наверх процедуру восстановления свойств КЧдерева. Тогда роль узла N будет играть F. Происходит поиск соответствующего случая, начиная со случая 1.Оценим количество поворотов, необходимых для восстановлениясвойств КЧ-дерева после удаления узла. Перекраска является менее трудоемкой операцией.
В случае 1 поворота не требуется, в46случае 2 требуется один поворот. Учитывая, каким образом случаисводятся друг к другу (4->1, 4->2, 4->3->2) и что каждый переход-> предполагает один поворот, получаем, что количество поворотов не превышает 3. В единственном случае (5), который приводитк возникновению цикла, производится только перекраска одногоузла. На каком-либо из шагов при подъеме наверх процедура остановится и сведется к случаям 1–4. Количество шагов ограниченовысотой дерева.FFNT1BT2T3NCLCRT4 T5T6T1BT2T3CLCRT4 T5T6Рис. 23.
Все узлы комбинации черные: перекраска B в красныйцвет и продолжение процедуры наверхНиже приведена реализация операции удаления узла из КЧ-деревас использованием вспомогательной процедуры восстановлениясвойств КЧ-дерева.RB-DELETE-FIXUP(T, x)/* На вход подается дерево T и n – сын удаленного узла. */1 while n ≠ root[T] и color[n] = BLACK do2if n = left[parent[n]] then3b ← right[parent[n]] /* b – брат n */4if color[b] = RED then /* случай 4 */5color[b] ← BLACK6color[parent[n]] ← RED7TREE-ROTATE-L(T, parent[n])8b ← right[parent[n]] /* теперь у n черныйбрат */9if color[left[b]] = BLACK и color[right[b]] = BLACKthen /* случай 1 или 5 */4710color[b] ← RED11n ← parent[n] /* при следующем заходе вцикл просмотрим отца n: если он красный, то имел место случай1 (в цикл не заходим), а если он черный, то имел место случай 5(продолжаем цикл) */12else13if color[right[b]] = BLACK then /* случай 3 *//* сводим к случаю 2 */14color[left[b]] ← BLACK15color[b] ← RED16RIGHT-ROTATE(T, b)17b ← right[parent[n]]18color[b] ← color[parent[n]] /* случай 2 */19color[parent[n]] ← BLACK20color[right[b]] ← BLACK21LEFT-ROTATE(T, parent[n])22n ← root[T] /* при попытке зайти в циклследующий раз процесс прекратится */23else24(симметричный фрагмент с заменой left ↔ right)25 color[n] ← BLACKRB-DELETE(T, z)/* На вход подается дерево T и узел z, который необходимо удалить из дерева, возвращается удаленный узел.
*/1 if left[z] = null[T] или right[z] = null[T] then /* один из сыновейузла z – фиктивный лист */2y←z3 else4y ← TREE-SUCCESSOR(z)5 if left[y] ≠ null[T] then/* присваиваем x единственного сына y */6x ← left[y]7 else8x ← right[y]489 parent[x] ← parent[y]10 if parent[y] = null[T] then11root[T] ← x12 else13if y = left[parent[y]] then14left[parent[y]] ← x15else16right[parent[y]] ← x17 if y ≠ z then18key[z] ← key[y]19 if color[y] = BLACK then/* если удаленный узел y – черный, то вызываем процедуру восстановления, которой передаем его сына */20RB-DELETE-FIXUP(T, x)21 return y4.3 Оценка сложности поиска в КЧ-деревеЛемма 1. Красно-черное дерево с n внутренними узлами (без фиктивных листьев) имеет высоту не более 2log2(n+1).Доказательство.1.
Обозначим через bh(x) черную высоту поддерева с корнем вузле x. Покажем вначале, что оно содержит не менее 2bh(x) – 1 внутренних узлов.a. Индукция. Для листьев (не фиктивных) bh(x) = 0, то есть,2bh(x) – 1 = 20 – 1 = 0.b. Пусть теперь x – не лист и имеет черную высоту bh(x) = k.Тогда каждый сын x имеет черную высоту не менее k – 1.Действительно, если узел красный, его сыновья могут бытьтолько черными, и в этом случае черная высота сына x будетна 1 меньше, чем черная высота x, т.е. будет равнаk – 1, потому как при расчете черной высоты узла сам узел вэто число не включается.
Если узел черный, то его сыновья49могут быть как черными, так и красными. Если сын черный,то аналогично предыдущему случаю его черная высота на 1меньше, чем у x и равна k – 1. Если сын красный, то он имеетчерную высоту такую же, как и x, т.е. k, т.к. количество черных узлов от x до листа, не включая x, такое же, как и количество черных узлов от его красного сына до листа.c. По предположению индукции каждый сын имеет чернуювысоту bh ≥ k – 1, а, следовательно, не менее 2k-1 – 1 узлов.Поэтому поддерево с корнем x имеет не менее 2k-1 – 1 + 2k-1 –1 + 1 = 2k – 1 узлов.2.
Теперь пусть высота дерева равна h.a. По свойству красно-черных деревьев, что если узел красный,то оба его сына черные, черные узлы составляют не меньшеполовины всех узлов на пути от корня к листу. Поэтому,черная высота дерева bh не меньше h/2.b. Тогда n ≥ 2h/2 – 1, откудаh ≤ 2log2(n + 1).(12)Лемма доказана.Из Леммы 1 следует, что поиск по КЧ-дереву имеет сложностьO(log2n).4.4 Задачи1. В каком случае при добавлении нового узла происходит увеличение черной высоты КЧ-дерева?2.
Как и где используется свойство, что корень КЧ-дерева черный?3. Могут ли все узлы КЧ-дерева из пяти внутренних узлов бытьчерными? А из 7 внутренних узлов?504. Может ли КЧ-дерево из 3 узлов, где все узлы черные, быть построено путем добавления в пустое дерево узлов по одному? Аесли еще и удалять можно?5. Переформулируйте определение КЧ-дерева так, чтобы дляобеспечения сбалансированности не требовалось вводить фиктивные листовые узлы.6. Чему равно максимальное и минимальное число красных узловв КЧ-дереве высоты h?7.
Чему равно минимальное количество узлов в КЧ-дереве высоты h?8. Назовем узел полулистовым, если у него не более одного потомка. (Рассматриваются только реальные потомки, а не фиктивные листья.) Относительной разбалансировкой назовем отношениенаибольшей длины пути от корня до полулистового узла в дереве кнаименьшей. Чему равна максимальная возможная относительнаяразбалансировка КЧ-дерева? Чему равна максимальная возможнаяотносительная разбалансировка АВЛ-дерева?5. Самоперестраивающиеся деревья(splay trees)Самоперестраивающееся дерево – это двоичное дерево поиска,которое, в отличие от предыдущих двух видов деревьев не содержит дополнительных служебных полей в структуре данных (баланс, цвет и т.п.). Оно позволяет находить быстрее те данные, которые использовались недавно.
Самоперестраивающееся деревобыло придумано Робертом Тарьяном и Даниелем Слейтером в1983 году.Идея самоперестраивающихся деревьев основана на принципе перемещения найденного узла в корень дерева. Эта операция называется splay(T, k), где k – это ключ, а T – двоичное дерево поиска.После выполнения операции splay(T, k) двоичное дерево T перестраивается, оставаясь при этом деревом поиска, так, что:51если узел с ключом k есть в дереве, то он становится корнем;если узла с ключом k нет в дереве, то корнем становитсяего предшественник или последователь.Таким образом, поиск узла в самоперестраивающемся дереве фактически сводится к выполнению операции splay. Эвристика moveto-front (перемещение найденного узла в корень) основана напредположении, что если тот же самый элемент потребуется вближайшее время, он будет найден быстрее.Определение 6: Словарными операциями над деревом называются базовые операции: поиск, вставка и удаление.Рассмотрим реализацию других словарных операций через splay.5.1 Вставка узла в самоперестраивающееся деревоАлгоритм вставки узла в самоперестраивающееся дерево начинаетсвою работу с поиска узла в этом дереве с помощью описаннойвыше операции splay(T, k).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
