Редактирование: Красно-черное дерево

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 19: Строка 19:
 
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей.
 
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей.
  
Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: $10$, $6$, $45$, $4$, $8$. На примере можно видеть, что после добавления вершины с ключом <tex>0</tex> и соответствующих перекрашиваний вершина с ключом <tex>6</tex> становится красной с красным родителем. Дальше добавим <tex>5</tex>. Так как мы добавляем к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого <tex>(-3)</tex>. Тогда вершина с ключом <tex>4</tex> станет красной (<tex>0</tex> и <tex>5</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
+
Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <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> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
  
 
===Альтернативные===
 
===Альтернативные===
Строка 63: Строка 63:
 
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
 
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
 
|proof=
 
|proof=
Рассмотрим красно-чёрное дерево с высотой <tex>h</tex>. Так как у красной вершины чёрные дети (по свойству $3$) количество красных вершин не больше $\dfrac{h}{2}$.
+
Рассмотрим красно-чёрное дерево с высотой <tex>h</tex>. Так как у красной вершины чёрные дети (по свойству $3$) количество красных вершин не больше $h / 2$.
Тогда чёрных вершин не меньше, чем <tex>\dfrac{h}{2} - 1</tex>.
+
Тогда чёрных вершин не меньше, чем <tex>h / 2 - 1</tex>.
  
 
По доказанной лемме, для количества внутренних вершин в дереве <tex>N</tex> выполняется неравенство:
 
По доказанной лемме, для количества внутренних вершин в дереве <tex>N</tex> выполняется неравенство:
  
<tex>N \geqslant 2^{h/2}-1</tex>
+
<tex>N \geqslant 2^{\frac{h}{2}}-1</tex>
  
 
Прологарифмировав неравенство, имеем:
 
Прологарифмировав неравенство, имеем:
  
<tex>\log(N+1) \geqslant \dfrac{h}{2}</tex>
+
<tex>\log(N+1) \geqslant \frac{h}{2}</tex>
  
 
<tex>2\log(N+1) \geqslant h</tex>
 
<tex>2\log(N+1) \geqslant h</tex>
Строка 84: Строка 84:
 
=== Вставка элемента ===
 
=== Вставка элемента ===
 
Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет <tex>nil</tex> (то есть этот сын {{---}} лист). Вставляем вместо него новый элемент с нулевыми потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство <tex>3</tex>, для исправления достаточно рассмотреть два случая:
 
Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет <tex>nil</tex> (то есть этот сын {{---}} лист). Вставляем вместо него новый элемент с нулевыми потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство <tex>3</tex>, для исправления достаточно рассмотреть два случая:
# "Дядя" этого узла тоже красный. Тогда, чтобы сохранить свойства <tex>3</tex> и <tex>4</tex>, просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" {{---}} в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин "отцы" черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству <tex>2</tex>. [[Файл:Untitled-1.png|200px]]
+
 
# "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. Таким образом, свойство <tex>3</tex> и постоянство черной высоты сохраняются.
+
1. "Дядя" этого узла тоже красный. Тогда, чтобы сохранить свойства <tex>3</tex> и <tex>4</tex>, просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" {{---}} в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин "отцы" черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству <tex>2</tex>.  
 +
 
 +
[[Файл:Untitled-1.png|200px]]
 +
 
 +
2. "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. Таким образом, свойство <tex>3</tex> и постоянство черной высоты сохраняются.
  
 
[[Файл:Untitled-2.png|250px|]]
 
[[Файл:Untitled-2.png|250px|]]
Строка 151: Строка 155:
 
=== Удаление вершины ===
 
=== Удаление вершины ===
 
При удалении вершины могут возникнуть три случая в зависимости от количества её детей:  
 
При удалении вершины могут возникнуть три случая в зависимости от количества её детей:  
* Если у вершины нет детей, то изменяем указатель на неё у родителя на <tex>nil</tex>.
+
# Если у вершины нет детей, то изменяем указатель на неё у родителя на <tex>nil</tex>.
* Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
+
# Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
* Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка (так как такая вершина находится в правом поддереве исходной вершины и она самая левая в нем, иначе бы мы взяли ее левого ребенка. Иными словами сначала мы переходим в правое поддерево, а после спускаемся вниз в левое до тех пор, пока у вершины есть левый ребенок). Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.
+
# Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка (так как такая вершина находится в правом поддереве исходной вершины и она самая левая в нем, иначе бы мы взяли ее левого ребенка. Иными словами сначала мы переходим в правое поддерево, а после спускаемся вниз в левое до тех пор, пока у вершины есть левый ребенок). Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.
 
Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
 
Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
  
* Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца {{---}} в красный цвет, сохраняя таким образом черную высоту дерева. Хотя все пути по-прежнему содержат одинаковое количество чёрных узлов, сейчас <tex>x</tex> имеет чёрного брата и красного отца. Таким образом, мы можем перейти к следующему шагу.  
+
1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца {{---}} в красный цвет, сохраняя таким образом черную высоту дерева. Хотя все пути по-прежнему содержат одинаковое количество чёрных узлов, сейчас <tex>x</tex> имеет чёрного брата и красного отца. Таким образом, мы можем перейти к следующему шагу.  
*:
+
 
*:[[Файл:Untitled-3.png|400px|]]
+
[[Файл:Untitled-3.png|400px|]]
*:
+
 
* Если брат текущей вершины был чёрным, то получаем три случая:
+
2. Если брат текущей вершины был чёрным, то получаем три случая:
** Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через <tex>b</tex>, но добавит один к числу чёрных узлов на путях, проходящих через <tex>x</tex>, восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.
+
* Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через <tex>b</tex>, но добавит один к числу чёрных узлов на путях, проходящих через <tex>x</tex>, восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.
**:
+
 
**:[[Файл:Untitled-4.png|400px|]]
+
[[Файл:Untitled-4.png|400px|]]
**:
+
 
** Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у <tex>x</tex> есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни <tex>x</tex>, ни его отец не влияют на эту трансформацию.
+
* Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у <tex>x</tex> есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни <tex>x</tex>, ни его отец не влияют на эту трансформацию.
**:
+
 
**:[[Файл:Untitled-5.png|400px|]]
+
[[Файл:Untitled-5.png|400px|]]
**:
+
 
** Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца {{---}} в чёрный, делаем вращение. Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство <tex>3</tex> и <tex>4</tex> не нарушаются. Но у <tex>x</tex> теперь появился дополнительный чёрный предок: либо <tex>a</tex> стал чёрным, или он и был чёрным и <tex>b</tex> был добавлен в качестве чёрного дедушки. Таким образом, проходящие через <tex>x</tex> пути проходят через один дополнительный чёрный узел. Выходим из алгоритма.
+
* Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца {{---}} в чёрный, делаем вращение. Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство <tex>3</tex> и <tex>4</tex> не нарушаются. Но у <tex>x</tex> теперь появился дополнительный чёрный предок: либо <tex>a</tex> стал чёрным, или он и был чёрным и <tex>b</tex> был добавлен в качестве чёрного дедушки. Таким образом, проходящие через <tex>x</tex> пути проходят через один дополнительный чёрный узел. Выходим из алгоритма.
**:
+
 
**: [[Файл:Untitled-6.png|400px|]]
+
[[Файл:Untitled-6.png|400px|]]
  
 
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
 
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
Строка 332: Строка 336:
 
#Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.
 
#Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.
 
#Сбалансированность этих деревьев хуже, чем у [[АВЛ-дерево | АВЛ]], но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.
 
#Сбалансированность этих деревьев хуже, чем у [[АВЛ-дерево | АВЛ]], но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.
#Использует всего $1$ бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит $2$ бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример {{---}} Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.
+
#Использует всего 1 бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит 2 бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример {{---}} Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.
  
 
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.
 
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.
Строка 340: Строка 344:
 
=== Изоморфизм деревьев ===
 
=== Изоморфизм деревьев ===
  
Красно-черные деревья изоморфны [[B-дерево | B-деревьям]] $4$ порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом<ref>[http://rflinux.blogspot.ru/2011/10/red-black-trees.html Абстрактные типы данных {{---}} Красно-чёрные деревья (Red black trees)]</ref>. Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют элементы, хранящиеся в одном узле B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла {{---}} цвет. Только один из элементов узла в B-дереве красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.
+
Красно-черные деревья изоморфны [[B-дерево | B-деревьям]] 4 порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом<ref>[http://rflinux.blogspot.ru/2011/10/red-black-trees.html Абстрактные типы данных {{---}} Красно-чёрные деревья (Red black trees)]</ref>. Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют элементы, хранящиеся в одном узле B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла {{---}} цвет. Только один из элементов узла в B-дереве красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.
  
 
[[Файл:Rbtree.png‎|750px|]]
 
[[Файл:Rbtree.png‎|750px|]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)