Удаление из красно черного дерева

Удаление из красно черного дерева

Красно-черные деревья — один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O (log n ).

Прекрасно написанные разделы о красно-черных деревьях вы найдете у Кормена-Ривеста-Лейзертона в их талмуде об алгоритмах.


Теория
Красно-черное дерево — это бинарное дерево с следующими свойствами:

  • Каждый узел покрашен либо в черный, либо в красный цвет.
  • Листьями объявляются NIL -узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели). Листья покрашены в черный цвет.
  • Если узел красный, то оба его потомка черны.
  • На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.

Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой 2. Кратчайшее возможное расстояние от корня до листа равно двум — когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырем — узлы при этом покрашены (от корня к листу) так: красный, черный, красный, черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться.
Вставка
Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить. Новый узел всегда добавляется как лист, поэтому оба его потомка являются NIL -узлами и предполагаются черными. После вставки красим узел в красный цвет. После этого смотрим на предка и проверяем, не нарушается ли красно-черное свойство. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.

Вставив красный узел с двумя NIL -потомками, мы сохраняем свойство черной высоты (свойство 4). Однако, при этом может оказаться нарушенным свойство 3, согласно которому оба потомка красного узла обязательно черны. В нашем случае оба потомка нового узла черны по определению (поскольку они являются NIL -узлами), так что рассмотрим ситуацию, когда предок нового узла красный: при этом будет нарушено свойство 3. Достаточно рассмотреть следующие два случая:

    Красный предок, красный "дядя" : Ситуацию красный-красный иллюстрирует рис. 1. У нового узла X предок и "дядя" оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить "дедушку" нового узла (узел B ), поскольку он может оказаться красным. Обратите внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень мы красим в черный цвет корень дерева. Если он был красным, то при этом увеличивается черная высота дерева.

  • Красный предок, черный "дядя" : На рис. 3.7 представлен другой вариант красно-красного нарушения — "дядя" нового узла оказался черным. Здесь узлы может понадобиться вращать, чтобы скорректировать поддеревья. В этом месте алгоритм может остановиться из-за отсутствия красно-красных конфликтов и вершина дерева (узел A) окрашивается в черный цвет. Обратите внимание, что если узел X был в начале правым потомком, то первым применяется левое вращение, которое делает этот узел левым потомком.
  • Каждая корректировка, производимая при вставке узла, заставляет нас подняться в дереве на один шаг. В этом случае до остановки алгоритма будет сделано 1 вращение (2, если узел был правым потомком). Метод удаления аналогичен.

    Главная > Документ

    Информация о документе
    Дата добавления:
    Размер:
    Доступные форматы для скачивания:
    Читайте также:  Как переместить картинки на карту памяти

    Красно – черные деревья.

    Красно–черное дерево – двоичное дерево поиска, узлы которого разделены на красные и черные. Каждый узел хранит дополнительное поле – его цвет (color).

    Глубина двух любых листьев в дереве отличается не более чем в два раза. Поэтому дерево можно назвать сбалансированным.

    И
    так, узел хранит поля: color, key, left, right, p. Для удобства оперирования в красно-черном дереве значения NIL заменены на указатели на фиктивные листья дерева. Поэтому каждый узел дерева – внутренний и имеет двух сыновей.

    Для красно-черного дерева выполняются RB-свойства (red-black properties):

    каждый узел – либо красный, либо черный;

    каждый лист – черный;

    если узел красный, оба его сына – черные;

    все пути, ведущие вниз от корня к листья, содержат одинаковое количество черных узлов.

    На рисунке все пути от каждого узла вниз содержат одинаковое количество черных узлов. Около каждого узла записана его черная высота.

    Число черных узлов на пути от корня дерева или поддерева к листьям называется черной высотой. В это число не входит черный узел в корне дерева. Каждый узел x дерева имеет черную высоту в h(x), равную числу черных узлов на пути до какого-либо листа. Высота дерева h(x) ≤ 2 log (n+1), где n – число внутренних узлов.

    Утверждение : По меньшей мере поддерево с корнем x содержит 2 bh ( x ) – 1 узлов.

    Действительно, лист имеет bh(x) = 0. Для него количество узлов в поддереве 2 bh ( x ) –1 = 2 0 –1 = 0.

    По индукции вершина x с bh(x) = k имеет два поддерева с bh = k–1. Тогда число внутренних узлов в поддеревьях равно 2 k –1 – 1 + 2 k –1 – 1 + 1 = 2 k – 1 .

    Если высота дерева – h, то его черная высота ≥ h/2.

    Тогда n ≥ 2 h /2 – 1

    n+1 ≥ 2 h/2 или log(n+1)

    Следовательно h ≤ 2 log (n+1).

    Таким образом, сложность операций над красно-черным деревом можно оценить как O(log n). Но операции вставки и удаления Tree_Insert и Tree_Delete могут испортить структуру красно-черного дерева, нарушив RB-свойства.

    П
    оэтому эти операции модифицируются таким образом, чтобы реализовать добавление и удаление узлов за O(log n) времени с сохранением RB-свойств. Делается это за счет перекраски и левых и правых однократных поворотов узлов с сохранением упорядоченности поддеревьев.

    Обе операции лишь меняют указатели в узлах и занимают время O(1).

    Left_Rotate (T, x)

    right [x] ← left [y]

    p[y] ← p[x] делаем родителя x родителем y

    else if x = left [p[x]]

    then left [p[x]] ← y

    else right [p[x]] ← y

    left [y] ← x делаем x левым ребенком y

    Операция Right_Rotate (T, x) симметрична.

    Сначала выполняется обычная операция включения в двоичное дерево Tree_Insert и новая вершина помечается красным цветом. После этого восстанавливаются RB-свойства, если они нарушены путем перекраски вершин и вращений.

    Рассмотрим случаи нарушения RB-свойств на примере включения в дерево:

    П
    ри включении х нарушено третье RB-свойство для вершины 5 (оба сына должны быть черные). Т.е. RB-свойство нарушается, если родитель нового узла красный.

    Как можно восстановить его:

    Случай 1: Если родитель красный, то родитель родителя – черный (в силу RB-свойства 2). Если у деда (7) второй сын – у ( дядя нового узла х) тоже красный, то можно перекрасить указанных предков: сделать деда красным, а родителя и дядю – черными. Это не изменит черную высоту дерева и восстановит третье свойство для родителя(5).

    П
    осле перекраски.

    Т
    .е. теперь 5 – черная вершина, которая может иметь и красного и черного сына. Но появился новый красный узел х(7). Теперь нарушено 3-е RB-свойство родителя узла 7 (2), т.к. этот узел тоже красный. К сожалению дядя (14) не красный и перекраску делать нельзя, не нарушив черной высоты. Тогда используем LL – поворот родителя х – (2).

    Исправлено нарушение 3-го свойства для узла 2, но нарушено для узла 7.

    С
    лучай 3 отличается от случая 2 тем, что х является левым, а не правым сыном своего родителя. В этом случае делаем правый поворот родителя (11).

    Красную вершину 7, оказавшуюся в корне, окрашиваем в черную, а вершины 2 и 11 – в красные. Это не нарушит RB-свойство 4).

    Читайте также:  Планета обезьян игра 2018


    RB_Insert (T, x)

    Tree_Insert (T, x)

    while x ≠ root [T] and color [p[x]] = RED

    dv if p[x] = left [p[p[x]]]

    then y ← right [p[p[x]]]

    if color [y] = RED

    then color [p[x]] ← BLACK случай 1

    color [y] ← BLACK случай 1

    color [p[p[x]]] ← RED случай 1

    x ← p[p[x]] случай 1

    else if x = right [p[x]]

    then x ← p[x] случай 2

    Left_Rotate (T, x) случай 2

    color [p[x]] ← BLACK случай 3

    color [p[p[x]]] ← RED случай 3

    Right_Rotate (T, p[p[x]]) случай 3

    else (симметричный текст с заменой left ↔ right)

    color [root[T]] ← BLACK

    При включении, если выпадает случай 3, выполняется не более одного вращения, и в случае 2 – не более двух вращений.

    Удаление из красно – черного дерева.

    Удаление из RB-дерева также требует O(log n)времени. Удаление вершины несколько сложнее добавления. Для упрощения удаления в дереве используется вместо значения NIL фиктивные элементы nil[T]. Более того, физически в дереве присутствует один фиктивный элемент, на который ссылаются все листья дерева и узлы, имеющие одного сына. Фиктивный элемент имеет те же поля, что и другие узлы, т.е. p, left, right, key и color, причем в алгоритмах играют роль только поля p и color. Цвет фиктивного элемента всегда черный. Благодаря фиктивному элементу все узлы внутренние.

    Операция RB_Delete работает такаже, как и Interative_Tree_Delete. Но вырезав вершину, она вызывает вспомогательную операцию RB_FixUp, которая перекрашивает узлы или производит вращения для восстановления RB-свойств после удаления узла. Эта операция используется, если вырезан черный узел.

    if left[x] = nil [T] or right[T] = nil [T]

    else y ← Tree_Successor (z)

    if left [y] ≠ nil [T]

    else x ← right [y]

    p [x] ← p[y] вырезание, в фиктивный элемент записывается родитель у

    else if y = left [p[y]]

    then left [p [y]] ← x

    else right [p[y]] ← x

    then key [z] ← key [y]

    копируем дополнительные данные из вершины у

    if color [y] = BLACK

    then RB_FixUp (T, x)

    Отличия RB_Delete от Interative_Tree_Delete:

    вместо nil используется nil[T];

    в строке 7 нет проверки if x ≠nil и p[x]←p[y] выполняется всегда, т.е. фиктивный элемент начинает ссылаться на родителя вырезаемого узла;

    используется RB_FixUp в случае вырезания черного узла. Вырезание его приводит к нарушению четвертого RB-свойства . Вырезание красного узла не приводит к нарушению RB-свойств.

    При удалении черного узла возможны 2 ситуации:

    В
    первом случае нарушение можно компенсировать перекрасив узел х в черный цвет. Это позволит ликвидировать и нарушение третьего свойства, если родитель вырезанного узла у – красный.

    Во втором случае применяется перестройка в корне поддерева, где возникло нарушение четвертого свойства. Причем узел х считается дважды черным, способным поделиться своей чернотой с вышележащими на пути к нему узлами.

    Нужно перестроить вышележащие узлы таким образом, чтобы избавиться от дважды черного узла, не нарушив RB-свойств дерева.

    Если х – корень, тогда лишняя чернота просто удаляется из дерева. Иначе выполняется циклическая перестройка корней поддеревьев, лежащих на пути к х, путем перекрашивания и вращений влево или вправо. Перестройка учитывает 4 возможных случая, которые могут встретиться на пути.

    Р
    ассмотрим эти случаи:

    Э
    то наиболее благоприятный случай. Можно перекрасить родителя х в черный цвет, х сделать обычным черным узлом, а w – красным. На этом перестройка заканчивается. Если родитель х – черный, то он становится дважды черным и перестройка поднимается в верхнее поддерево.

    Если новый х – корень дерева, то лишняя чернота просто удаляется из дерева.

    Этот случай можно свести к первому, чтобы братом х стал черный узел. Для этого сделаем левый поворот родителя узла х.

    3
    ). Теперь разберемся со случаями, отличными от 1, т.е. когда сыновья ц разного цвета: Перекрасив родителя х в черный цвет, а w – в красный , мы нарушим свойство 3 для w.

    П
    оэтому сделаем сначала правый поворот узла w.

    Для случая 4 важно, что правый сын узла w – красный. Перекрашивать нельзя. Левый сын может быть и красным и черным. Опять же действие по схеме случая 1 не годится, т.к. это приведет к нарушению свойства 3.

    Читайте также:  Как блокировать неизвестные номера на андроид

    Тогда произведем вращение влево родителя х. Узел х отдает свою черноту родителю, а правый сын узла w перекрашивается в черный цвет. Узел w берет цвет корня поддерева до поворота.

    В этом случае происходит полное поглощение излишней черноты и на этом перестройка прекращается.

    Итак, рассмотрев действия в различных случаях, подробно рассмотрим только операцию RB_FixUp (T, x).

    It_RB_Delete (root, k) + RB_FixUp (root, z). О( logn ).

    Удаление вершины несколько сложнее включения (может быть нарушено 4-ое свойство при удалении черного узла). Для упрощения программирования операции удаления в RB -дерево вводится фиктивный элемент NIL , который будет использоваться вместо ссылок nil в терминальных узлах дерева. Все терминальные узлы, не имеющие сыновей или одного сына, вместо nil имеют ссылку на фиктивный элемент NIL . Фиктивный элемент не содержит ни ключей, ни данных. Используются только ссылки на сыновей и родителя. Цвет фиктивного элемента всегда черный. Благодаря фиктивному узлу все реальные узлы всегда внутренние.

    После удаления вызывается дополнительная операция ( RB _ FixUp ), которая восстанавливает нарушенное 4-ое свойство — все пути вниз (от корня к листьям) содержат одинаковое число черных узлов (одинаковая черная высота). Восстановление ведется путем перекрашивания узлов и вращений на пути поиска удаляемого элемента. 1)Если удаляемый узел y -красный, то 4-е свойство RB -дерева не нарушается и операция удаления на этом завершается. 2)Если удалена черная вершина, то выполняется операция RB _ FixUp для сына ( z ) удаленного узла ( y ). Сыном удаленного узла может быть либо его единственный левый или правый сын, либо фиктивный узел NIL , причем в этот момент p [ z ] или p [ NIL ] указывают на родителя удаленного узла y .

    RB -дерево, как структура обладает следующими RB —свойствами: 1) каждый узел либо R , либо B ; 2) каждый лист B ; 3) если узел R , то оба сына – B ; 4) все пути вниз (от корня к листьям) содержат одинаковое число B узлов (одинаковая B высота); 5) корень черный.

    При удалении черного узла возможны 2 ситуации:

    1) нарушение можно компенсировать, пере-красив узел х в черный цвет. Это позволит ликвидировать и нарушение 3-его свойства, если родитель вырезанного узла у – красный.

    2) применяется перестройка в корне поддерева, где возникло нарушение четвертого свойства. Причем узел х считается дважды черным, способным поделиться своей чернотой с вышележащими на пути к нему узлами. Нужно перестроить вышележащие узлы таким образом, чтобы избавиться от дважды черного узла, не нарушив RB -свойств дерева. Если х – корень, тогда лишняя чернота просто удаляется из дерева. Иначе выполняется циклическая перестройка корней поддеревьев, лежащих на пути к х , путем перекрашивания и вращений влево или вправо.

    Перестройка учитывает 4 возможных случая, которые могут встретиться на пути:

    Можно перекрасить родителя х в черный цвет, х сделать обычным черным узлом, а w – красным. На этом перестройка заканчивается.

    Если родитель х – черный, то он становится дважды черным и перестройка поднимается в верхнее поддерево. Если новый х – корень дерева, то лишняя чернота просто удаляется из дерева.


    Этот случай можно свести к первому, чтобы братом х стал черный узел. Для этого сделаем левый поворот родителя узла х .


    to be continued …

    Сыновья w разно-го цвета

    . Перекра-сив родителя х в черный цвет, а w – в красный, мы на-рушим свойство 3 для w . Поэтому сделаем сначала правый поворот узла w .


    Важно, что правый сын узла w – красный. Перекрашивать нельзя. Левый сын может быть и красным и черным. Опять же действие по схеме случая 1 не годится, т.к. это приведет к нарушению свойства 3. Поэтому произведем вращение влево родителя х. Узел х отдает свою черноту родителю, а правый сын узла w перекрашивается в черный цвет. Узел w берет цвет корня поддерева до поворота. В этом случае происходит полное поглощение излишней черноты и на этом перестройка прекращается.

    Операция RB _ Delete выполняется за O ( logn ). Обычно производится не более трех вращений.

    Ссылка на основную публикацию
    Топ лучших видеокарт для игр
    Видеокарты крайне быстро улучшаются, практически каждые полгода выходит видеоадаптер, значительно превосходящий предшественника. Активный прогресс обусловлен быстрым увеличением системных требований компьютерных...
    Телефон леново включается но не запускается
    Бывает, что пользователь включает свой смартфон, процесс доходит до заставки (логотипа) и дальше не грузится. Сразу начинается паника, ведь телефон...
    Телефон леново инструкция для чайников
    Большинство из нас чувствует себя неуверенно, когда приходится знакомиться с новой операционной системой. И несмотря на то, что Андроид сегодня...
    Топ приложений для запоминания слов
    Топ-8 приложений, где запоминать английские слова Приложения для изучения английских слов помогают быстро и эффективно пополнять словарный запас. Без работы...
    Adblock detector