Красно-черное дерево

Материал из Викиконспекты
Версия от 21:06, 30 мая 2018; 178.62.106.169 (обсуждение) (Высота красно-черного дерева)
Перейти к: навигация, поиск

Красно-чёрное дерево (англ. red-black tree) — двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. red) и "чёрный" (англ. black).

Пример красно-чёрного дерева.

При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.

Для экономии памяти фиктивные листья можно сделать одним общим фиктивным листом.

Свойства

Оригинальные

Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный атрибут — цвет и для которого выполняются следующие свойства:

  1. Каждый узел промаркирован красным или чёрным цветом
  2. Корень и конечные узлы (листья) дерева — чёрные
  3. У красного узла родительский узел — чёрный
  4. Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов
  5. Чёрный узел может иметь чёрного родителя
Ослабленное красно-чёрное дерево.

Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.

Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корю иметь красных детей.

Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: [math]10, 6, 45, 4, 8[/math]. На примере можно видеть, что после добавления вершины с ключом [math]0[/math] и соответствующих перекрашиваний вершина с ключом [math]6[/math] становится красной с красным родителем. Дальше добавим [math]5[/math]. Так как мы добавляем к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого [math]-3[/math]. Тогда вершина с ключом [math]4[/math] станет красной ([math]0[/math] и [math]5[/math] — черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.

Альтернативные

В книге Кормена "Алгоритмы: построение и анализ" дается немного иное определение красно-черного дерева, а именно:

Двоичное дерево поиска является красно-чёрным, если обладает следующими свойствами:

  1. Каждая вершина — либо красная, либо черная
  2. Каждый лист — черный
  3. Если вершина красная, оба ее ребенка черные
  4. Все пути, идущие от корня к листьям, содержат одинаковое количество черных вершин

То, что только черная вершина может иметь красных детей, совместно с [math]4[/math]-тым свойством говорит о том, что корень дерева должен быть черным, а значит определения можно считать эквивалентными.

Высота красно-черного дерева

Определение:
Будем называть чёрной высотой (англ. black-height) вершины [math]x[/math] число чёрных вершин на пути из [math]x[/math] в лист, не учитывая саму вершину [math]x[/math].


Лемма:
В красно-черном дереве с черной высотой [math]hb[/math] количество внутренних вершин не менее [math]2^{hb+1}-1[/math].
Доказательство:
[math]\triangleright[/math]

По индукции докажем, что поддерево любого узла [math]x[/math] с черной высотой [math]hb(x)[/math] содержит не менее [math]2^{hb(x)} - 1[/math] внутренних узлов.

База индукции:

Если высота узла [math]x[/math] равна [math]0,[/math] то [math]x[/math] — это лист, [math]hb(x) = 0, [/math] [math]2^{0} - 1 = 0.[/math]

Индукционный переход:

Пусть наше предположение верно для высот до [math]h'.[/math] Теперь рассмотрим внутреннюю вершину [math]x[/math] с двумя потомками, для которой [math]hb(x)=h'[/math]. Тогда если ее потомок [math]p[/math] — черный, то его высота [math]hb(p)=h'- 1[/math], а если красный, то [math]hb(p) = h'[/math]. Но поскольку высота потомка меньше, чем высота узла [math]x[/math], для него выполняется индукционное предположение. В таком случае в поддереве узла [math]x[/math] содержится не менее чем [math]2^{h'} - 1 + 2^{h'} - 1 + 1 = 2^{h'+1} - 1[/math].

Следовательно, утверждение верно и для всего дерева.
[math]\triangleleft[/math]
Теорема:
Красно-чёрное дерево с [math]N[/math] ключами имеет высоту [math]h = O(\log N)[/math].
Доказательство:
[math]\triangleright[/math]

Так как только черные узлы могут иметь красных детей, то в самом длинном пути от корня до листа красных вершин будет точно не больше половины, поэтому если обычная высота дерева равна [math]h[/math], то черная высота дерева будет не меньше [math]h/2-1[/math] и, по лемме, количество внутренних вершин в дереве

[math]N \geqslant 2^{h/2}-1[/math]

Прологарифмировав неравенство, имеем:

[math]\log(N+1) \geqslant h/2[/math]

[math]2\log(N+1) \geqslant h[/math]

[math]h \leqslant 2\log(N+1)[/math]
[math]\triangleleft[/math]

Операции

Узел, с которым мы работаем, на картинках имеет имя [math]x[/math].

Вставка элемента

Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет [math]nil[/math] (то есть этот сын — лист). Вставляем вместо него новый элемент с [math]nil[/math]-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство [math]3[/math], для исправления достаточно рассмотреть два случая:

1. "Дядя" этого узла тоже красный. Тогда, чтобы сохранить свойства [math]3[/math] и [math]4[/math], просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" — в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин "отцы" черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству [math]2[/math].

Untitled-1.png

2. "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. Таким образом, свойство [math]3[/math] и постоянство черной высоты сохраняются.

Untitled-2.png

Псевдокод:

func insert(key)
    Node t = Node(key, red, nil, nil) // конструктор, в который передаем ключ, цвет, левого и правого ребенка 
    if root == nil
        root = t
        t.parent = nil
    else
        Node p = root
        Node q = nil
        while p != nil
            q = p
            if p.key < t.key
                p = p.right
            else
                p = p.left
        t.parent = q
        if q.key < t.key
            q.right = t
        else
            q.left = t
     fixInsertion(t) // проверяем, не нарушены ли свойства красно-черного дерева 
func fixInsertion(t: Node)
    if root == t
        t.colour = black
        return
    while t.parent != nil and t.parent.colour == red
        Node grandfather = t.parent.parent
        Node uncle = nil
        if grandfather.left == t.parent 
            if grandfather.right != nil
                 uncle = grandfather.right
                 if uncle.colour == red 
                     // случай, когда "дядя" красный 
                     t.parent.colour = black
                     uncle.colour = black
                     grandfather.colour = red
                     t = grandfather 
            else
                if t.parent.right == t
                    t = t.parent
                    leftRotate(t)
                t.parent.colour = black
                grandfather.colour = red
                rightRotate(g)
            else
                if grandfather.left != nil
                    uncle = grandfather.left;
                    if uncle.colour == red
                         // случай, когда "дядя" красный 
                         t.parent.colour = black
                         uncle.colour = black
                         grandfather.colour = red
                         t = grandfather
                else
                    if t.parent.left == t
                        t = t.parent
                        rightRotate(t)
                    t.parent.colour = black
                    grandfather.colour = red
                    leftRotate(grandfather)
    root.colour = black // восстанавливаем свойство корня 

Удаление вершины

При удалении вершины могут возникнуть три случая в зависимости от количества её детей:

  1. Если у вершины нет детей, то изменяем указатель на неё у родителя на [math]nil[/math].
  2. Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
  3. Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка (так как такая вершина находится в правом поддереве исходной вершины и она самая левая в нем, иначе бы мы взяли ее левого ребенка. Иными словами сначала мы переходим в правое поддерево, а после спускаемся вниз в левое до тех пор, пока у вершины есть левый ребенок). Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.

Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.

1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца — в красный цвет, сохраняя таким образом черную высоту дерева. Хотя все пути по-прежнему содержат одинаковое количество чёрных узлов, сейчас [math]x[/math] имеет чёрного брата и красного отца. Таким образом, мы можем перейти к следующему шагу.

Untitled-3.png

2. Если брат текущей вершины был чёрным, то получаем три случая:

  • Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через [math]b[/math], но добавит один к числу чёрных узлов на путях, проходящих через [math]x[/math], восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.

Untitled-4.png

  • Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у [math]x[/math] есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни [math]x[/math], ни его отец не влияют на эту трансформацию.

Untitled-5.png

  • Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца - в чёрный, делаем вращение. Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство [math]3[/math] и [math]4[/math] не нарушаются. Но у [math]x[/math] теперь появился дополнительный чёрный предок: либо [math]a[/math] стал чёрным, или он и был чёрным и [math]b[/math] был добавлен в качестве чёрного дедушки. Таким образом, проходящие через [math]x[/math] пути проходят через один дополнительный чёрный узел. Выходим из алгоритма.

Untitled-6.png

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

Псевдокод:

func delete(key)
    Node p = root
    // находим узел с ключом key
    while p.key != key 
        if p.key < key 
            p = p.right
        else
            p = p.left
    // случай, когда нет детей
    if p.left == nil and p.right == nil
        if p == root
            root = nil
        else
            if p.parent.left == p
               p.parent.left = nil
            else
               p.parent.right = nil
        return
    Node y = nil
    Node q = nil
    if p.left == nil or p.right == nil
        // один ребенок
        y = p
    else
        // два ребенка
        if p.left != nil
            y = p.left 
            while y.right != nil
                y = y.right
        else
            y = p.right;
            while y.left != nil
                y = y.left
    if y.left != nil
        q = y.left
    else
        q = y.right
    if q != nil
        q.parent = y.parent;
    if y.parent == nil
        root = q
    else
        if y is leftChild
            y.parent.left = q
        else
            y.parent.right = q
    if y != p
        p.colour = y.colour
        p.key = y.key
    if y.colour == black
        // при удалении черной вершины могла быть нарушена балансировка
        fixDeleting(q)

func fixDeleting(p: Node)
    Node brother = nil
    while p != root and p isBlack
         if p is leftChild
             brother = p.parent.right
             if brother isRed
                 brother.colour = black
                 p.parent.colour = red
                 leftRotate(p.parent)
                 brother = p.parent.right
             if brother.left isBlack and brother.right isBlack
                 brother.colour = red
                 p = p.parent
             else
                 if brother.right isBlack
                     brother.left.colour = black
                     brother.colour = red
                     rightRotate(brother)
                     brother = p.parent.right
                 brother.colour = p.parent.colour
                 p.parent.colour = black
                 brother.right.colour = black
                 leftRotate(p.parent)
                 p = root
         else // p is rightChild 
             brother = p.parent.left
             if brother isRed
                 brother.colour = black
                 p.parent.colour = red
                 rightRotate(p.parent)
                 brother = p.parent.left
             if brother.left isBlack and brother.right isBlack
                 brother.colour = red
                 p = p.parent
             else
                 if brother.left isBlack
                     brother.right.colour = black
                     brother.colour = red
                     leftRotate(brother);
                     brother = p.parent.left
                 brother.colour = p.parent.colour
                 p.parent.colour = black
                 brother.left.colour = black
                 rightRotate(p.parent)
                 p = root
      p.colour = black
      root.colour = black

Объединение красно-чёрных деревьев

Объединение двух красно-чёрных деревьев [math]T_{1}[/math] и [math]T_{2}[/math] по элементу [math]x[/math] выполняется, когда [math]key[T_{1}] \leqslant x[/math] и [math]x \leqslant key[T_{2}][/math], где [math]key[T][/math] — максимальные ключи дерева [math]T[/math]. Найдём чёрные высоты деревьев. Предположим также, что [math]hb[T_{1}] \geqslant hb[T_{2}][/math]. Тогда в дереве [math]T_{1}[/math] ищем среди чёрных вершин, имеющих чёрную высоту [math]hb[T_{2}][/math], вершину [math]y[/math] с наибольшим ключом. Пусть [math]T_{y}[/math] — поддерево с корнем [math]y[/math]. Объединяем это дерево с [math]T_{2}[/math] в одно с красным корнем [math]x[/math]. Теперь родителем вершины [math]x[/math] становится бывший отец вершины [math]y[/math]. Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины.

Если [math]hb[T_{1}] \leqslant hb[T_{2}][/math], то слияние происходит аналогично, только теперь мы ищем в дереве [math]T_{2}[/math] среди чёрных вершин, имеющих чёрную высоту [math]hb[T_{1}][/math], вершину [math]y[/math] с наименьшим ключом.

Так как общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за [math]O(\log{n})[/math].

Рассмотрим пример объединения двух красно-чёрных деревьев и вершины[math](35)[/math]:

Untitled-7.png

Узнаём чёрную высоту левого и правого дерева. Чёрная высота левого и правого деревьев равна [math]2[/math] и [math]1[/math] соответственно. Так как чёрная высота левого дерева больше, то ищем в левом дереве чёрную вершину, имеющую чёрную высоту правого дерева, с наибольшим ключом. Чёрная высота вершины[math](8)[/math] левого дерева равна высоте правого дерева и ключ является наибольшим. Поэтому вершина[math](8)[/math] становится левым сыном вершины[math](35)[/math], а правое дерево будет правым сыном. Вершина[math](35)[/math] станет правым сыном вершины[math](0)[/math]:

Untitled-8.png

Далее проверяем: не нарушили ли мы свойства красно-чёрного дерева. Так как присутствует нарушение(у красной вершины есть красный сын), то перекрасим вершины и сделаем поворот:

Untitled-9.png

Преимущества красно-чёрных деревьев

  1. Самое главное преимущество красно-черных деревьев в том, что при вставке выполняется не более [math]O(1)[/math] вращений. Это важно, например, в алгоритме построения динамической выпуклой оболочки. Ещё важно, что примерно половина вставок и удалений произойдут задаром.
  2. Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.
  3. Сбалансированность этих деревьев хуже, чем у АВЛ, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.
  4. Использует всего 1 бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит 2 бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример — Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.

Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.

Связь с 2-3 и 2-4 деревьями

Изоморфизм деревьев

Красно-черные деревья изоморфны B-деревьям 4 порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом[1]. Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют элементы, хранящиеся в одном узле B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла — цвет. Только один из элементов узла в B-дереве красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.

Rbtree.png

Корректность сопоставления деревьев

Сопоставив таким образом цвета узлам дерева, можно проверить, что полученное дерево удовлетворяет всем свойствам красно-черного дерева.

Утверждение:
У красного узла родитель не может быть красного цвета.
[math]\triangleright[/math]
В узле 2-4 дерева содержится не более трех элементов, один из которых обязательно красится в черный при переходе к симметричному бинарному B-дереву. Тогда оставшиеся красные элементы, если они есть, подвешиваются к черному. Из этих элементов могут идти ребра в следующий узел 2-4 дерева. В этом узле обязательно есть черная вершина, в нее и направляется ребро. Оставшиеся элементы узла, если они есть, подвешиваются к черной вершине аналогично первому узлу. Таким образом, ребро из красной вершины никогда не попадает в красную, значит у красного элемента родитель не может быть красным.
[math]\triangleleft[/math]
Утверждение:
Число черных узлов на любом пути от листа до вершины одинаково.
[math]\triangleright[/math]
В B-дереве глубина всех листьев одинакова. Из каждого узла B-дерева выбирается только один элемент для окраски в черный цвет, и путь в симметричным бинарным B-дереве состоит только из элементов, лежащих на одном пути в B-дереве. Значит количество черных элементов на любом пути от листа до вершины одинаково.
[math]\triangleleft[/math]
Утверждение:
Корень дерева — черный.
[math]\triangleright[/math]
Вершина B-дерева состоит из узла, в котором один элемент — черный. Он и выбирается в качестве корня симметричного бинарного B-дерева.
[math]\triangleleft[/math]

Сопоставление операций в деревьях

Все операции, совершаемые в B-дереве, сопоставляются операциям в красно-черном дереве. Для этого достаточно доказать, что изменение узла в B-дереве соответствует повороту в красно-черном дереве.

Утверждение:
Изменение узла в B-дереве соответствует повороту в красно-черном дереве.
[math]\triangleright[/math]

В 2-4 дереве изменение узла необходимо при добавлении к нему элемента. Рассмотрим, как будет меняться структура B-дерева и, соответственно, красно-черного дерева при добавлении элемента:

  • Если в узле содержался один элемент, то происходит добавление второго элемента, соответствующее добавлению красного элемента в красно-черное дерево.
  • Если в узле содержалось два элемента, то происходит добавление третьего элемента, что соответствует повороту и перекрашиванию вершин в красно-черном дереве.
  • Если в узле содержалось три элемента, то один из элементов узла становится самостоятельным узлом, к которому подвешиваются узел из пары элементов и узел из одного элемента. Эта операция соответствует перекрашиванию яруса красно-черного дерева из красного в черный цвет.

Rbtree2.png

При удалении элемента из узла B-дерева совершаются аналогичные процессы поворота и окраски вершин в красно-черном дереве, только в обратном направлении. Так как все операции в 2-4 дереве происходят за счет изменения узлов, то они эквивалентны соответствующим операциям в красно-черном дереве.
[math]\triangleleft[/math]
Теорема:
Приведенное выше сопоставление B-деревьев и красно-черных деревьев является изоморфизмом.
Доказательство:
[math]\triangleright[/math]
Доказательство следует непосредственно из приведенных выше утверждений.
[math]\triangleleft[/math]

См. также

Примечания

Источники информации