Изменения

Перейти к: навигация, поиск

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

5069 байт добавлено, 00:01, 13 января 2019
Высота красно-черного дерева
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корю корню иметь красных детей.
Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <tex>10, 6, 45, 4, 8</tex>. На примере можно видеть, что после добавления вершины с ключом <tex>0</tex> и соответствующих перекрашиваний вершина с ключом <tex>6</tex> становится красной с красным родителем. Дальше добавим <tex>5</tex>. Так как мы добавляем к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого <tex>-3</tex>. Тогда вершина с ключом <tex>4</tex> станет красной (<tex>0</tex> и <tex>5</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
{{Лемма
|statement= В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.
|proof=
По индукции докажем, что поддерево любого узла <tex>x</tex> с черной высотой <tex>hb(x)</tex> содержит не менее <tex>2^{hb(x)} - 1</tex> внутренних узлов. '''База индукции:''' Если рассмотреть высота узла <tex>x</tex> равна <tex>0,</tex> то <tex>x</tex> {{---}} это лист , <tex>hb(фиктивную вершинуx)= 0, то </tex> <tex>2^{0} - 1 = 0.</tex> '''Индукционный переход:''' Пусть наше предположение верно для нее лемма вернавысот до <tex>h'. Рассмотрим </tex> Теперь рассмотрим внутреннюю вершину <tex>x</tex>. Пусть с двумя потомками, для которой <tex>hb(x)=h'</tex>. Тогда если ее потомок <tex>p</tex> {{---}} черный, то его высота <tex>hb(p)=h'-1</tex>, а если красный, то <tex>hb(p) = h'</tex>. Таким образомНо поскольку высота потомка меньше, по предположению индукциичем высота узла <tex>x</tex>, для него выполняется индукционное предположение. В таком случае в поддеревьях содержится не менее поддереве узла <tex>2^{h'}-1x</tex> вершин, а во всём дереве, соответственно, содержится не менее чем <tex>2^{h'-1}-1 + 2^{h'-1}-1 + 1=2^{h'+1}-1</tex>. Следовательно, утверждение верно и для всего дерева.
}}
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
|proof=
Рассмотрим красно-чёрное дерево с высотой <tex>h.</tex> Так как у красной вершины чёрные дети <tex>(</tex>по свойству <tex>3),</tex> количество красных вершин не больше <tex>h / 2. </tex> Тогда чёрных вершин не меньше, чем <tex>h / 2 - 1.</tex>
Так как только черные узлы могут иметь красных детейПо доказанной лемме, то для количества внутренних вершин в самом длинном пути от корня до листа красных вершин будет точно не больше половины, поэтому если обычная высота дерева равна <tex>h</tex>, то черная высота дерева будет не меньше дереве <tex>h/2-1N</tex> и, по лемме, количество внутренних вершин в деревевыполняется неравенство:
<tex>N \geqslant 2^{h/2}-1</tex>
'''func''' insert(key)
Node t = Node(key, red, ''nil'', ''nil'') <font color=green>// конструктор, в который передаем ключ, цвет, левого и правого ребенка </font>
'''if''' root == ''nil''дерево пустое
root = t
t.parent = ''nil''
Node p = root
Node q = ''nil''
'''while''' p != ''nil''<font color=green>// спускаемся вниз, пока не дойдем до подходящего листа </font>
q = p
'''if''' p.key < t.key
p = p.left
t.parent = q
<font color=green>// добавляем новый элемент красного цвета </font>
'''if''' q.key < t.key
q.right = t
'''func''' fixInsertion(t: '''Node''')
'''if''' root == t{{---}} корень t.colour = black
'''return'''
<font color=green>// далее все предки упоминаются относительно t </font> '''while''' t.parent !"отец" красный <font color= ''nil'' '''and''' t.parent.colour == red Node grandfather = t.parent.parent Node uncle = ''nil''green>// нарушается свойство <tex>3</tex> </font> '''if''' grandfather.left == t.parent "отец" {{---}} левый ребенок '''if''' grandfather.right != ''nil'' uncle = grandfather.rightесть "дядя" '''if''' uncle.colour == red <font color=green>// случай, когда "дядя" красный </font> t.parent.colour = black uncle.colour = black grandfather.colour = red
t = grandfather
'''else'''
<font color=green>// случай, когда нет "дяди" </font> '''if''' t.{{---}} правый сын t = parent leftRotate(t) parent = black grandfather = red rightRotate(grandfather) '''else''' <font color=green>// "отец" {{---}} правый ребенок </font> '''if''' есть "дядя" '''if''' "дядя" красный parent.right =black uncle = black grandfather = red t = grandfather '''else''' <font color=green>// нет "дяди" </font> '''if''' t{{---}} левый ребенок
t = t.parent
leftRotaterightRotate(t) t.parent.colour = black grandfather.colour = red rightRotate(g) '''else''' if grandfather.left != ''nil'' uncle = grandfather.left; if uncle.colour == red <font color=green>// случай, когда "дядя" красный </font> 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 <font color=green>// восстанавливаем свойство корня </font>
=== Удаление вершины ===
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
Из рассмотренных случаев ясно, что при удалении выполняется не более трёх вращений.
 
'''Псевдокод:'''
'''func''' delete(key)
Node p = root
<font color=green>// находим узел с ключом key</font>
'''while''' p.key != key
'''if''' p.key < key
p = p.right
'''else'''
p = p.left
'''if''' у p нет детей
'''if''' p {{---}} корень
root = ''nil''
'''else'''
ссылку на p у "отца" меняем на ''nil''
'''return'''
Node y = ''nil''
Node q = ''nil''
'''if''' один ребенок
ссылку на у от "отца" меняем на ребенка y
'''else'''
<font color=green>// два ребенка</font>
y = вершина, со следующим значением ключа <font color=green>// у нее нет левого ребенка </font>
'''if''' y имеет правого ребенка
t.right.parent = y.parent
'''if''' y {{---}} корень
root = t.right
'''else'''
у родителя ссылку на y меняем на ссылку на первого ребенка y
'''if''' y != p
p.colour = y.colour
p.key = y.key
'''if''' y.colour == black
<font color=green>// при удалении черной вершины могла быть нарушена балансировка</font>
fixDeleting(q)
 
'''func''' fixDeleting(p: '''Node''')
<font color=green>// далее родственные связи относительно p</font>
'''while''' p {{---}} черный узел и не корень
'''if''' p {{---}} левый ребенок
'''if''' "брат" красный
brother = black
parent = red
leftRotate(parent)
'''if''' у "брата" черные дети <font color=green>// случай <tex>1:</tex> "брат" красный с черными детьми</font>
brother = red
'''else'''
'''if''' правый ребенок "брата" черный <font color=green>// случай, рассматриваемый во втором подпункте:</font>
brother.left = black <font color=green>// "брат" красный с черными правым ребенком</font>
brother = red
rightRotate(brother)
brother.colour = parent.colour <font color=green>// случай, рассматриваемый в последнем подпункте</font>
parent = black
brother.right = black
leftRotate(parent)
p = root
'''else''' <font color=green>// p {{---}} правый ребенок</font>
<font color=green>// все случаи аналогичны тому, что рассмотрено выше</font>
'''if''' "брат" красный
brother = black
parent = red
rightRotate(p.parent)
'''if''' у "брата" черные дети
brother = red
'''else'''
'''if''' левый ребенок "брата" черный
brother.right = black
brother = red
leftRotate(brother);
brother = parent
parent = black
brother.left = black
rightRotate(p.parent)
p = root
p = black
root = black
=== Объединение красно-чёрных деревьев ===
Число черных узлов на любом пути от листа до вершины одинаково.
|proof=
В B-дереве глубина всех листьев одинакова. Из каждого узла B-дерева выбирается только один элемент для окраски в черный цвет, следовательно, одинаково и путь в симметричным бинарным B-дереве состоит только из элементов, лежащих количество внутренних узлов на одном каждом пути в . Мы сопоставляем чёрный цвет одному элементу внутреннего узла B-дереведерева. Значит , количество черных чёрных элементов на любом пути от листа до вершины одинаково.
}}
{{Утверждение
Корень дерева {{---}} черный.
|proof=
Вершина BЕсли в корне один элемент, то он {{--дерева состоит из узла-}} чёрный. Если же в корне несколько элементов, то заметим, в котором что один элемент окрашен в чёрный цвет, остальные {{---}} черныйв красный. Горизонтальные связи, соединяющие элементы внутри одного узнала, ведут из чёрного элемента в красный, следовательно, красные элементы будут подвешены к чёрному. Он и выбирается в качестве корня симметричного бинарного B-дерева.
}}
Анонимный участник

Навигация