В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 3
Текст из файла (страница 3)
Красно-черным деревом называется бинарное дерево,1. Для каждой вершины которого определен «цвет» этой вершины – красный иличерный (корень дерева всегда черный)2. Красная вершина имеет только черных потомков3. В любой ветке от корня одинаковое число черных вершин («черная длина дерева»)(RB-свойства дерева)Длина красно-черного дерева не более чем в 2 раза превышает длину идеальносбалансированного дерева.
Действительно, рассмотрим все ветки от корня. Пусть h – чернаядлина дерева, а n – обычная. В силу того, что у красных вершин только черные потомки,Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год9имеем, что в каждой ветке красных вершин не больше, чем черных, а черных,соответственно – не менее половины.
Очевидно, отсюда h < n < 2h. Черное деревоабсолютно идеально сбалансировано, так что если H – число черных вершин, тоh log 2 H log 2 N n 2h 2 log 2 N .Заметим, что добавлять элемент в дерево мы можем только в концевые вершины (дляупорядоченного дерева можно добавлять элемент, как мы добавляли его в сбалансированноедерево (конечно, без применения балансировки дерева) – в структуре дерева при этомспособе просто добавляется еще один концевой элемент). При добавлении элемента пока небудем менять раскраску нашего дерева, а добавленный элемент покрасим в красный цвет.Теперь будем двигаться снизу вверх, восстанавливая корректную раскраску дерева.Единственно ошибочная ситуация после добавления – наш элемент красный, его «родитель»- тоже красный (поскольку черная раскраска дерева не менялась, то она осталасьсбалансированной).
Из исходной раскраски дерева следует, что родитель родителя нашегоэлемента – черный, а число черных вершин в поддеревьях одинаково:CBACLBLВ зависимости от раскраски CL возможны 2 варианта балансировки:Если CL – красный, то перекрашиваем C в красный, CL и B – в черный и тем самымвосстанавливаем корректность раскраски – это легко проверить (баланс черного сохранился,а раскраска теперь может оказаться нарушена только у C, тогда применяем процедуруперекраски для него):CBACLBLЕсли же CL – черный, то придется «вращать» поддерево (т.е. фактически сохраняя егоструктуру переставить элемент, с которого оно начинается).
Для показанного случаяполучается:BACBLCLЛегко видеть, что эта перестановка совершенно аналогична L1 (R1), применявшейся длябалансировки сбалансированного дерева поиска, но еще придется перекрашивать B вчерный цвет, а C – в красный. Если BL – красный, то придется применить еще и первуюописанную перекраску:Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год10BACBLCLОчевидно, черный баланс дерева сохраняется (1 + черная длина A), корректностьраскраски – тоже. При этом на каждом шаге алгоритма мы поднимаемся на 1 уровень вверхпо дереву, так что в конце концов мы придем к ситуации вида:BACТогда нам останется только покрасить B в черный цвет.
Это – единственная ситуация,которая может изменить черную длину дерева. Возможно, что мы до нее и не дойдем ираскраска станет корректной еще на более ранних стадиях работы алгоритма. Трудоемкостьдобавления элемента – порядка длины дерева, т.е. O log 2 N .Более сложной операцией является удаление элемента из красно-черного дерева.Удаление произвольного элемента упорядоченного дерева опять-таки можно организоватьтаким образом, чтобы из структуры дерева удалялась вершина, содержащая не более 1потомка.Если удаляемая вершина – красная, то все в порядке, никакие правила не нарушены(легко также видеть, что у этой вершины нет потомков вообще, т.к. если были бы, то былибы оба и оба черные – из определения к-ч дерева).
Хуже, если приходится удалять чернуювершину – черный баланс дерева при этом нарушается. Легко видеть, что удаляемаявершина либо не имеет потомков вообще, либо имеет только красного потомка (одного) – всилу того, что потомков не более 1го, а черная длина левого и правого поддеревьеводинакова. Если красный потомок существует, то он займет место удаляемой вершины ибудет перекрашен в черный цвет – никаких проблем с раскраской здесь не возникнет.Поэтому в дальнейшем рассматриваем случай удаления черной концевой вершины.Поставим на место нулевых указателей в дереве фиктивные элементы черного цвета –«листья» дерева. После удаления концевого элемента черного цвета из бывших 2х листьевэтого элемента поставим один и покрасим его в «дважды черный» (на рисунках далееобозначен серым цветом).
Будем избавляться от дважды черных вершин в дереве.Первая возможная ситуация – у дважды черного элемента «брат» – черного цвета и хотябы один потомок брата – красного цвета (либо оба не существуют)ABCCLCRВ этом случае применяем перестановку R1:Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год11СACRCLBЕсли A была черной, то C красим в дважды черный; если A была красной, то C красим вчерный.Второй случай –ABCCRDDRDL- здесь уже понадобится R2:DABCDLCRDRЗдесь D красится в красный, если A была красной; в черный, если A была черной.Окраска полностью восстанавливается.Третий случай – брат элемента – черный, оба его потомка – тоже черныеИтак, либоABCCLCR- перекрашиваем A в дважды черный, B – в черный, C – в красный и переходим науровень выше:Лекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год12ABCCRCLВо второй ситуацииABCCRCLдостаточно перекрасить A в черный, B в черный, C в красный.Легко видеть, что эти 2 ситуации полностью исчерпывают ситуацию «черный брат».Если брат – красный,ABCCLCRТо здесь достаточно применить R1, тогда получится один из ранее рассмотренныхслучаев (перекраска после поворота: A – в красный, C – в черный).Отдельный случай – когда дважды черный элемент оказался к корне.
В этом случаеперекрашиваем корень просто в черный цвет и это единственный случай, когда меняетсячерная длина дерева.Еще один тип деревьев является своеобразным обобщением деревьев поиска. B –деревом порядка n называют дерево1.Каждая вершина которого содержит не менее n и не более 2n значений (заисключением корня, просто содержащего не более 2n значений)2.Все значения, хранящиеся в вершине, упорядочены (по возрастанию)3.Вершина с k значениями имеет k+1 потомков, либо является концевой4.Если a – m-е значение в вершине все значения m-го потомка вершины меньше a,а значения в m+1 потомке – больше a5.Все концевые вершины в B-дереве лежат на одном уровнеЛекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год13Пример B-дерева порядка 2:3010213806543411712461100Очевидно, длина B – дерева порядка n не превосходит log n N 1 . Действительно, если унас на k-м уровне N kэлементов, то на следующем уровне N k 1 N k 1 n иk 1k 1jk 1соответственно справедлива оценка N k N1n n N1 n , а для общего числаj 1элементов в дереве - M k N k откуда и следует оценка для длины B-дерева.Поиск в B-дереве происходит за время, не превосходящее log 2 N 1 log n N 1 немного медленнее, чем в бинарном дереве поиска (на каждом уровне – бинарный поискумноженный на число уровней).Вставка элемента в B-дерево происходит так: вначале ищем место, куда вставитьэлемент – спускаемся вниз до концевых вершин, ища место, куда вставить элемент.
Еслиэлемент нужно вставлять туда, где еще есть свободное место, то производим вставку сразу(пример: добавление элемента 45 в приведенное ранее B-дерево); если элемент нужнодобавить в уже заполненную вершину (например, 5 в примере выше), то создаем новуювершину уровнем выше и «переливаем» половину данных из заполненной вершины всвежесозданную вершину. При добавлении элемента 5 это даст в примере выше10361171221304143658010054Если уровень выше, то алгоритм будет пробовать «разлить» и его по двум уровням ит.д.
Обрывается такой алгоритм при необходимости «разлить» корневой элемент. Например,добавим еще числа 6, 7, 8 в наше дерево. После первых двух шагов получится1031122456173061414365801007и такой алгоритм уже не работает. Но несложной модификацией его можно заставитьработать и в этом случае: создадим «нулевой» уровень, пока что пустой, и применим к немунаш алгоритм. Затем переставим указатели на корень дерева на этот новый элемент.ПолучитсяЛекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год1410172456130638126517418010043Т.е.
длина B-дерева в этом случае автоматически увеличится на 1, а все его свойствасохранятсяАналогично производится удаление элементов B-дерева. Если удаляемый элементлежит в концевой вершине и число элементов в ней больше n, то просто удаляем его. Еслиудаляемый элемент в концевой вершине и число элементов в ней уже n, то пробуем«перелить» несколько элементов из левого или правого соседа текущей вершины, чтобыраспределить число элементов в них поровну, и затем удаляем элемент. Если элементсодержит потомков (не лежит в концевой вершине), то пробуем перелить этот элементуровнем ниже и поставить на его место элемент из нижележащих уровней, после чегоспокойно удалить элемент. Первый метод неприменим когда у нас надо удалить элемент извершины с n элементами и левый или правый соседи этой вершины тоже содержат по nэлементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
