Левосторонние красно-чёрные деревья - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:08:01Z

rollbackEdits.php mass rollback

194.88.143.66 в 06:24, 1 сентября 2022

2022-09-01T06:24:16Z

Дмитрий Мурзин: Дмитрий Мурзин переименовал страницу Левосторонние красно-черные деревья в Левосторонние красно-чёрные деревья: Ёфикация

2019-01-31T20:42:50Z

Дмитрий Мурзин переименовал страницу Левосторонние красно-черные деревья в Левосторонние красно-чёрные деревья: Ёфикация

188.227.117.250 в 21:32, 27 июня 2018

2018-06-27T21:32:04Z

188.227.117.250: /* Вращения */

2018-06-20T12:33:25Z

‎Вращения

188.227.117.250: /* Вращения */

2018-06-20T12:26:15Z

‎Вращения

188.227.117.250: /* Вращения */

2018-06-20T12:25:55Z

‎Вращения

188.227.117.250: /* Вращения */

2018-06-20T12:25:42Z

‎Вращения

188.227.117.250: /* Свойства */

2018-06-20T11:44:50Z

‎Свойства

188.227.117.250: /* Свойства */

2018-06-20T11:43:24Z

‎Свойства

← Предыдущая		Версия 16:08, 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 Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition = Левостороннее красно-черное дерево {{---}} тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска.		\|definition = Левостороннее красно-черное дерево {{---}} тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска.

← Предыдущая		Версия 06:24, 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 Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition = Левостороннее красно-черное дерево {{---}} тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска.		\|definition = Левостороннее красно-черное дерево {{---}} тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска.

@@ Строка 119: / Строка 119: @@
         '''return''' h
-===Удаление максимума===
+==Удаление максимума==
 * Спускаемся вниз по правому краю  дерева.
 * Если поиск заканчивается на узле с <tex>4</tex>-мя или <tex>5</tex>-ю потомками, просто удаляем узел.

@@ Строка 13: / Строка 13: @@
 * Количество черных узлов на каждом таком пути одинаково.
-Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево.Первая операция трансформируют <tex>3</tex>-узел (совокупность из <tex>3</tex> узлов, где <tex>2</tex> узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в  <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот.  Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
+Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево. Первая операция трансформируют <tex>3</tex>-узел (совокупность из <tex>3</tex> узлов, где <tex>2</tex> узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в  <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот.  Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
 ===Псевдокод===
 [[File:rotateRight.png|310px|thumb|upright|Rotate Right]]

@@ Строка 13: / Строка 13: @@
 * Количество черных узлов на каждом таком пути одинаково.
-Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево.Первая операция трансформируют <tex>3</tex>-узел(совокупность из <tex>3</tex> узлов, где <tex>2</tex> узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в  <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот.  Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
+Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево.Первая операция трансформируют <tex>3</tex>-узел (совокупность из <tex>3</tex> узлов, где <tex>2</tex> узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в  <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот.  Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
 ===Псевдокод===
 [[File:rotateRight.png|310px|thumb|upright|Rotate Right]]

← Предыдущая	Версия 20:42, 31 января 2019
(нет различий)

@@ Строка 13: / Строка 13: @@
 * Количество черных узлов на каждом таком пути одинаково.
-Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево.Первая операция трансформируют <tex>3</tex>-узел, левый потомок которого окрашен в красный, в  <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот.  Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
+Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево.Первая операция трансформируют <tex>3</tex>-узел(совокупность из <tex>3</tex> узлов, где tex>2</tex> узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в  <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот.  Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
 ===Псевдокод===
 [[File:rotateRight.png|310px|thumb|upright|Rotate Right]]
@@ Строка 31: / Строка 31: @@
         h.color = RED
         '''return''' x
 ==Переворот цветов==
 В красно-черных деревьях используется такая  операция как '''переворот цветов''' , которая инвертирует цвет узла и двух его детей.  Она не изменяет количество черных узлов  на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.

@@ Строка 6: / Строка 6: @@
 *Корневой узел всегда черный.
 *Каждый новый узел всегда окрашен в красный цвет.
-*Каждый дочерний узел листа дерева считается черным.
+*Каждый дочерний нулевой узел листа дерева считается черным.
 ==Вращения==