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

Algocourselecturenotes в 15:46, 15 апреля 2020

2020-04-15T15:46:37Z

Algocourselecturenotes: /* Случай 2 */

2020-04-15T15:06:07Z

‎Случай 2

Algocourselecturenotes: /* Случай 2 */

2020-04-15T15:04:55Z

‎Случай 2

Algocourselecturenotes: /* Случай 2 */

2020-04-15T15:03:45Z

‎Случай 2

Algocourselecturenotes: /* Случай 2 */

2020-04-15T15:00:23Z

‎Случай 2

Algocourselecturenotes: /* Случай 2 */

2020-04-15T14:49:45Z

‎Случай 2

Algocourselecturenotes: /* Вставка */

2020-04-15T14:29:02Z

‎Вставка

Algocourselecturenotes: /* Вставка */

2020-04-15T14:28:34Z

‎Вставка

Algocourselecturenotes: /* Вставка */

2020-04-15T14:27:21Z

‎Вставка

Algocourselecturenotes: /* Случай 1 */

2020-04-15T14:16:04Z

‎Случай 1

@@ Строка 1: / Строка 1: @@
-[[File:rbtee_example.png|thumb|top|right|Пример КЧД]]
+[[File:rbtee_example.png|thumb|top|right|upright=1.2|Пример КЧД]]
 '''Красно-чёрное дерево'''(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:
@@ Строка 8: / Строка 9: @@
 # У красной вершины оба ребёнка чёрные
 # Чёрная высота каждой вершины определена корректно
 == Чёрная высота ==

← Предыдущая		Версия 15:06, 15 апреля 2020
Строка 66:		Строка 66:
	[[File:rbtee_insert_case2_subcase2.png\|thumb\|top\|left\|Подслучай 2]]		[[File:rbtee_insert_case2_subcase2.png\|thumb\|top\|left\|Подслучай 2]]

−	Легко заметить, что при таких действиях количество чёрных вершин на любом пути, проходящем через это поддерево не меняется. ~~Каких-либо конфликтов~~ так же ~~не возникает~~.	+	Легко заметить, что при таких действиях количество чёрных вершин на любом пути, проходящем через это поддерево не меняется. Остальные свойства КЧД так же выполняются. В частности, корень поддерева $a$ должен быть чёрным. Теперь дерево сбалансированно.

← Предыдущая		Версия 15:04, 15 апреля 2020
Строка 66:		Строка 66:
	[[File:rbtee_insert_case2_subcase2.png\|thumb\|top\|left\|Подслучай 2]]		[[File:rbtee_insert_case2_subcase2.png\|thumb\|top\|left\|Подслучай 2]]

−	Легко заметить, что при таких действиях количество чёрных вершин на любом пути, проходящем через это поддерево не меняется.	+	Легко заметить, что при таких действиях количество чёрных вершин на любом пути, проходящем через это поддерево не меняется. Каких-либо конфликтов так же не возникает.

← Предыдущая		Версия 15:03, 15 апреля 2020
Строка 65:		Строка 65:

	[[File:rbtee_insert_case2_subcase2.png\|thumb\|top\|left\|Подслучай 2]]		[[File:rbtee_insert_case2_subcase2.png\|thumb\|top\|left\|Подслучай 2]]
		+
		+	Легко заметить, что при таких действиях количество чёрных вершин на любом пути, проходящем через это поддерево не меняется.

← Предыдущая		Версия 15:00, 15 апреля 2020
Строка 63:		Строка 63:
	* $x$ - правый потомок $p$. В таком случае совершаем левое вращение с центром в $p$ и сводим этот случай к следующему ($p$ - новый $x$).		* $x$ - правый потомок $p$. В таком случае совершаем левое вращение с центром в $p$ и сводим этот случай к следующему ($p$ - новый $x$).
	* $x$ - левый потомок $p$. В этом случае совершаем правое вращение с центром в вершине $gp$, предварительно покрасив $gp$ в красный, а $p$ - в чёрный.		* $x$ - левый потомок $p$. В этом случае совершаем правое вращение с центром в вершине $gp$, предварительно покрасив $gp$ в красный, а $p$ - в чёрный.
		+
		+	[[File:rbtee_insert_case2_subcase2.png\|thumb\|top\|left\|Подслучай 2]]

@@ Строка 55: / Строка 55: @@
 === Случай 2 ===
 $u$ - чёрный (возможно фиктивный). Тогда далее будем считать, что $p$ - левый потомок $gp$. В ином случае дальнейшие действия следует отзеркалить.
@@ Строка 61: / Строка 63: @@
 * $x$ - правый потомок $p$. В таком случае совершаем левое вращение с центром в $p$ и сводим этот случай к следующему ($p$ - новый $x$).
 * $x$ - левый потомок $p$. В этом случае совершаем правое вращение с центром в вершине $gp$, предварительно покрасив $gp$ в красный, а $p$ - в чёрный.

@@ Строка 50: / Строка 50: @@
 === Случай 1 ===
-[[File:rbtee_insert_case2_subcase1.png|thumb|top|right|Первый случай]]
+[[File:rbtee_insert_case1.png|thumb|top|right|Первый случай]]
 $u$ - красный (не фиктивный). Тогда красим $u$ и $p$ в чёрный, а $gp$ - в красный. После этого количество чёрных вершин на любом пути, проходящем через $gp$ не изменяется. Но могло нарушиться свойство 4, если родитель $gp$ оказался красным, или свойство 2, если $gp$ оказался чёрным. В первом случае конфликт был поднят выше по дереву - его можно исправить рекурсивно. Во втором случае мы просто красим $gp$ в чёрный цвет.
@@ Строка 62: / Строка 62: @@
 * $x$ - левый потомок $p$. В этом случае совершаем правое вращение с центром в вершине $gp$, предварительно покрасив $gp$ в красный, а $p$ - в чёрный.
-[[File:rbtee_insert_case1.png|thumb|top|right|]]
+[[File:rbtee_insert_case2_subcase1.png|thumb|top|right|]]

← Предыдущая		Версия 14:27, 15 апреля 2020
Строка 53:		Строка 53:

	$u$ - красный (не фиктивный). Тогда красим $u$ и $p$ в чёрный, а $gp$ - в красный. После этого количество чёрных вершин на любом пути, проходящем через $gp$ не изменяется. Но могло нарушиться свойство 4, если родитель $gp$ оказался красным, или свойство 2, если $gp$ оказался чёрным. В первом случае конфликт был поднят выше по дереву - его можно исправить рекурсивно. Во втором случае мы просто красим $gp$ в чёрный цвет.		$u$ - красный (не фиктивный). Тогда красим $u$ и $p$ в чёрный, а $gp$ - в красный. После этого количество чёрных вершин на любом пути, проходящем через $gp$ не изменяется. Но могло нарушиться свойство 4, если родитель $gp$ оказался красным, или свойство 2, если $gp$ оказался чёрным. В первом случае конфликт был поднят выше по дереву - его можно исправить рекурсивно. Во втором случае мы просто красим $gp$ в чёрный цвет.
		+
		+	=== Случай 2 ===
		+
		+	$u$ - чёрный (возможно фиктивный). Тогда далее будем считать, что $p$ - левый потомок $gp$. В ином случае дальнейшие действия следует отзеркалить.
		+
		+	Рассмотрим два подслучая:
		+	* $x$ - правый потомок $p$. В таком случае совершаем левое вращение с центром в $p$ и сводим этот случай к следующему ($p$ - новый $x$).
		+	* $x$ - левый потомок $p$. В этом случае совершаем правое вращение с центром в вершине $gp$, предварительно покрасив $gp$ в красный, а $p$ - в чёрный.
		+
		+	[[File:rbtee_insert_case1.png\|thumb\|top\|right\|]]

← Предыдущая		Версия 14:16, 15 апреля 2020
Строка 52:		Строка 52:
	[[File:rbtee_insert_case1.png\|thumb\|top\|right\|Первый случай]]		[[File:rbtee_insert_case1.png\|thumb\|top\|right\|Первый случай]]

−	$u$ - красный. Тогда красим $u$ и $p$ в чёрный, а $gp$ - в красный. После этого количество чёрных вершин на любом пути, проходящем через $gp$ не изменяется. Но могло нарушиться свойство 4, если родитель $gp$ оказался красным, или свойство 2, если $gp$ оказался чёрным. В первом случае конфликт был поднят выше по дереву - его можно исправить рекурсивно. Во втором случае мы просто красим $gp$ в чёрный цвет.	+	$u$ - красный (не фиктивный). Тогда красим $u$ и $p$ в чёрный, а $gp$ - в красный. После этого количество чёрных вершин на любом пути, проходящем через $gp$ не изменяется. Но могло нарушиться свойство 4, если родитель $gp$ оказался красным, или свойство 2, если $gp$ оказался чёрным. В первом случае конфликт был поднят выше по дереву - его можно исправить рекурсивно. Во втором случае мы просто красим $gp$ в чёрный цвет.