Красно-черное дерево - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:17:22Z

rollbackEdits.php mass rollback

185.86.148.90 в 05:35, 1 сентября 2022

2022-09-01T05:35:46Z

195.133.239.83: Исправлен бесконечный цикл в псевдокоде fixInsertion

2021-05-09T11:43:00Z

Исправлен бесконечный цикл в псевдокоде fixInsertion

Dmitriy в 19:55, 3 июня 2019

2019-06-03T19:55:34Z

Dmitriy в 19:54, 3 июня 2019

2019-06-03T19:54:41Z

Внесённые изменения

Dmitriy в 19:23, 3 июня 2019

2019-06-03T19:23:18Z

Dmitriy: fixes

2019-06-03T19:22:19Z

fixes

Dmitriy: Added join & split

2019-05-22T12:49:49Z

Added join & split

Внесённые изменения

212.48.226.194 в 06:51, 28 марта 2019

2019-03-28T06:51:38Z

93.175.2.242: /* Высота красно-черного дерева */

2019-01-12T21:01:45Z

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

← Предыдущая		Версия 16:17, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Красно-чёрное дерево''' (англ. ''red-black tree'') {{---}} двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. ''red'') и "чёрный" (англ. ''black'').		'''Красно-чёрное дерево''' (англ. ''red-black tree'') {{---}} двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. ''red'') и "чёрный" (англ. ''black'').
	[[Файл:RBT.jpg‎\|350px\|thumb\|Пример красно-чёрного дерева.]]		[[Файл:RBT.jpg‎\|350px\|thumb\|Пример красно-чёрного дерева.]]

← Предыдущая		Версия 05:35, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Красно-чёрное дерево''' (англ. ''red-black tree'') {{---}} двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. ''red'') и "чёрный" (англ. ''black'').		'''Красно-чёрное дерево''' (англ. ''red-black tree'') {{---}} двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. ''red'') и "чёрный" (англ. ''black'').
	[[Файл:RBT.jpg‎\|350px\|thumb\|Пример красно-чёрного дерева.]]		[[Файл:RBT.jpg‎\|350px\|thumb\|Пример красно-чёрного дерева.]]

@@ Строка 119: / Строка 119: @@
       '''while''' "отец" красный <font color=green>// нарушается свойство <tex>3</tex> </font>
           '''if''' "отец" {{---}} левый ребенок
-              '''if''' есть "дядя"
+              '''if''' есть красный "дядя"
-                   '''if''' "дядя" красный
+                   parent = black
-                      parent = black
+                  uncle = black
-                      uncle = black
+                  grandfather = red
-                      grandfather = red
+                  t = grandfather
               '''else'''
                   '''if''' t {{---}} правый сын
                       t = parent
@@ Строка 134: / Строка 132: @@
                   rightRotate(grandfather)
           '''else''' <font color=green>// "отец" {{---}} правый ребенок </font>
-              '''if''' есть "дядя"
+              '''if''' есть красный "дядя"
-                  '''if''' "дядя" красный
+                  parent = black
-                      parent = black
+                 uncle = black
-                      uncle = black
+                 grandfather = red
-                      grandfather = red
+                 t = grandfather
               '''else''' <font color=green>// нет "дяди" </font>
                   '''if''' t {{---}} левый ребенок

@@ Строка 19: / Строка 19: @@
 Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей.
-Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <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> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
+Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: $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> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
 ===Альтернативные===

@@ Строка 68: / Строка 68: @@
 По доказанной лемме, для количества внутренних вершин в дереве <tex>N</tex> выполняется неравенство:
-<tex>N \geqslant 2^{\frac{h}{2}}-1</tex>
+<tex>N \geqslant 2^{\dfrac{h}{2}}-1</tex>
 Прологарифмировав неравенство, имеем:
-<tex>\log(N+1) \geqslant \frac{h}{2}</tex>
+<tex>\log(N+1) \geqslant \dfrac{h}{2}</tex>
 <tex>2\log(N+1) \geqslant h</tex>

@@ Строка 19: / Строка 19: @@
 Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей.
-Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <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> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
+Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <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> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
 ===Альтернативные===
@@ Строка 30: / Строка 30: @@
 # Все пути, идущие от корня к листьям, содержат одинаковое количество черных вершин
-То, что только черная вершина может иметь красных детей, совместно с <tex>4</tex>-тым свойством говорит о том, что корень дерева должен быть черным, а значит определения можно считать эквивалентными.
+То, что только черная вершина может иметь красных детей, совместно с <tex>4</tex>-ым свойством говорит о том, что корень дерева должен быть черным, а значит определения можно считать эквивалентными.
 == Высота красно-черного дерева ==
@@ Строка 52: / Строка 52: @@
 Тогда черные высоты детей могут быть $hb(x)$ или $hb(x)-1$ {{---}} если потомок красный или черный соответственно.
-Тогда по предположению индукции в каждом из поддеревьев не менее $2^{hb(x)-2}-1$ вершин. Тогда всего в поддереве не менее $2*(2^{hb(x)-2}-1)+1 = 2^{hb(x)-1}-1$ вершин ($+1$ {{---}} мы учли еще саму вершину $x$).
+Тогда по предположению индукции в каждом из поддеревьев не менее $2^{hb(x)-2}-1$ вершин. Тогда всего в поддереве не менее $2\cdot(2^{hb(x)-2}-1)+1 = 2^{hb(x)-1}-1$ вершин ($+1$ {{---}} мы учли еще саму вершину $x$).
 Переход доказан.
@@ Строка 68: / Строка 68: @@
 По доказанной лемме, для количества внутренних вершин в дереве <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 h/2</tex>
+<tex>\log(N+1) \geqslant \frac{h}{2}</tex>
 <tex>2\log(N+1) \geqslant h</tex>
@@ Строка 83: / Строка 83: @@
 Узел, с которым мы работаем, на картинках имеет имя <tex>x</tex>.
 === Вставка элемента ===
-Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет <tex>nil</tex> (то есть этот сын {{---}} лист). Вставляем вместо него новый элемент с <tex>nil</tex>-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство <tex>3</tex>, для исправления достаточно рассмотреть два случая:
+Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет <tex>nil</tex> (то есть этот сын {{---}} лист). Вставляем вместо него новый элемент с нулевыми потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство <tex>3</tex>, для исправления достаточно рассмотреть два случая:
 . "Дядя" этого узла тоже красный. Тогда, чтобы сохранить свойства <tex>3</tex> и <tex>4</tex>, просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" {{---}} в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин "отцы" черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству <tex>2</tex>.
@@ Строка 173: / Строка 173: @@
 [[Файл: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|]]
@@ Строка 335: / Строка 335: @@
 #Самое главное преимущество красно-черных деревьев в том, что при вставке выполняется не более <tex>O(1)</tex> вращений. Это важно, например, в алгоритме построения [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)|динамической выпуклой оболочки]]. Ещё важно, что примерно половина вставок и удалений произойдут задаром.
 #Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.
-#Сбалансированность этих деревьев хуже, чем у АВЛ, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.
+#Сбалансированность этих деревьев хуже, чем у [[АВЛ-дерево | АВЛ]], но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.
 #Использует всего 1 бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит 2 бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример {{---}} Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.
 Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.
-== Связь с 2-3 и 2-4 деревьями ==
+== Связь с [[2-3_дерево | 2-3 и 2-4 деревьями]] ==
 === Изоморфизм деревьев ===

@@ Строка 195: / Строка 195: @@
           y = вершина, со следующим значением ключа <font color=green>// у нее нет левого ребенка </font>
           '''if''' y имеет правого ребенка
-              t.right.parent = y.parent
+              y.right.parent = y.parent
           '''if''' y {{---}} корень
-              root = t.right
+              root = y.right
           '''else'''
               у родителя ссылку на y меняем на ссылку на первого ребенка y

@@ Строка 48: / Строка 48: @@
 '''Индукционный переход:'''
-Пусть наше предположение верно для высот до <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>x</tex> содержится не менее чем   <tex>2^{h'-1} - 1 + 2^{h'-1} - 1 + 1 = 2^{h'+1} - 1</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>x</tex> содержится не менее чем   <tex>2^{h'-1} - 1 + 2^{h'-1} - 1 + 1 = 2^{h'} - 1</tex>.
 Следовательно, утверждение верно и для всего дерева.