2-3-дерево - История изменений

СВ: /* Сравнение с альтернативами */

2026-10-25T20:06:54Z

Сравнение с альтернативами

← Предыдущая		Версия 20:06, 25 октября 2026
Строка 469:		Строка 469:
	! Структура !! Хранит баланс !! Высота !! Поиск !! Вставка/удаление !! Особенность		! Структура !! Хранит баланс !! Высота !! Поиск !! Вставка/удаление !! Особенность
	\|-		\|-
	\| '''2-3 дерево''' \|\| нет (структурно) \|\| <math>\le \log_2 n</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| 2–3 ребёнка на узел		\| '''2-3 дерево''' \|\| нет (структурно) \|\| <math>\le \log_2 L</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| 2–3 ребёнка на узел
	\|-		\|-
	\| [[2-3-4 дерево]] \|\| нет \|\| <math>\le \log_2 n</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| 2–4 ребёнка; изоморфно КЧ		\| [[2-3-4 дерево]] \|\| нет \|\| <math>\le \log_2 L</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| 2–4 ребёнка; изоморфно КЧ
	\|-		\|-
	\| [[АВЛ-дерево\|АВЛ-дерево]] \|\| BF/высота \|\| <math>\le 1.44\log_2 n</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| строгий баланс, много поворотов		\| [[АВЛ-дерево\|АВЛ-дерево]] \|\| BF/высота \|\| <math>\le 1.44\log_2 n</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| строгий баланс, много поворотов
Строка 479:		Строка 479:
	\| B-дерево порядка <math>t</math> \|\| нет \|\| <math>\le \log_t n</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| рассчитано на страницы диска		\| B-дерево порядка <math>t</math> \|\| нет \|\| <math>\le \log_t n</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| рассчитано на страницы диска
	\|}		\|}

			'''Обозначения в таблице.''' <math>L</math> — число внешних листьев; для 2-3 и 2-3-4 <math>L = n + 1</math>, где <math>n</math> — число ключей.

	'''Вердикт.''' 2-3 дерево — самый простой пример «многоключевого» баланса: нет полей баланса, а гарантия высоты следует из формы. На практике в памяти чаще берут двоичные КЧ/АВЛ (компактнее на узел), а на диске — B-деревья больших порядков; 2-3 дерево ценно как модель, объясняющая и B-деревья, и красно-чёрные деревья.		'''Вердикт.''' 2-3 дерево — самый простой пример «многоключевого» баланса: нет полей баланса, а гарантия высоты следует из формы. На практике в памяти чаще берут двоичные КЧ/АВЛ (компактнее на узел), а на диске — B-деревья больших порядков; 2-3 дерево ценно как модель, объясняющая и B-деревья, и красно-чёрные деревья.

СВ: /* Корректность и оценка сложности */

2026-10-25T20:06:29Z

Корректность и оценка сложности

← Предыдущая		Версия 20:06, 25 октября 2026
Строка 445:		Строка 445:
	== Корректность и оценка сложности ==		== Корректность и оценка сложности ==

	'''Лемма 1 (граница высоты).''' 2-3 дерево с <math>n</math> ключами имеет высоту <math>h</math>, где <math>\log_3 n \le h \le \log_2 n</math>.		'''Лемма 1 (граница высоты).''' 2-3 дерево с <math>L</math> внешними листьями (и <math>n = L - 1</math> ключами) имеет высоту <math>h</math>, где <math>\log_3 L \le h \le \log_2 L</math>.

	''Доказательство.'' У каждого внутреннего узла от 2 до 3 детей, все листья на глубине <math>h</math>. Число листьев <math>L</math> удовлетворяет <math>2^h \le L \le 3^h</math>~~. Так как ключей <math>n = L - 1</math> (или~~ <math>L \~~approx n</math>), то <math>2^~~h \le n</math> и <math>n ~~\le 3^h~~</math>, ~~откуда~~ <math>~~\log_3 n \le~~ h \le \~~log_2~~ n</math>. <math>\blacksquare</math>		''Доказательство.'' У каждого внутреннего узла от 2 до 3 детей, все внешние листья на глубине <math>h</math>. Число листьев <math>L</math> удовлетворяет <math>2^h \le L \le 3^h</math>, откуда <math>\log_3 L \le h \le \log_2 L</math>. Так как ключей <math>n = L - 1</math>, получаем <math>h = \Theta(\log n)</math>. <math>\blacksquare</math>

	'''Теорема 2 (корректность вставки).''' После <code>Insert</code> дерево остаётся 2-3 деревом с тем же множеством ключей плюс новый.		'''Теорема 2 (корректность вставки).''' После <code>Insert</code> дерево остаётся 2-3 деревом с тем же множеством ключей плюс новый.
Строка 455:		Строка 455:
	'''Теорема 3 (корректность удаления).''' После <code>Delete</code> дерево остаётся 2-3 деревом без удалённого ключа.		'''Теорема 3 (корректность удаления).''' После <code>Delete</code> дерево остаётся 2-3 деревом без удалённого ключа.

	''Доказательство.'' Заимствование переносит ключ из соседа-3-узла через родителя, сохраняя и порядок, и число детей; слияние объединяет два 2-узла и разделяющий ключ родителя в один 3-узел, уменьшая число детей родителя на один — недостача поднимается вверх и в итоге поглощается, а опустевший корень заменяется единственным ребёнком. Все листья остаются на одной глубине. <math>\blacksquare</math>		''Доказательство.'' Заимствование переносит ключ из соседа-3-узла через родителя, сохраняя и порядок, и число детей; слияние объединяет два 2-узла и разделяющий ключ родителя в один 3-узел, уменьшая число детей родителя на один — недостача поднимается вверх и в итоге поглощается, а опустевший корень заменяется единственным ребёнком. Все внешние листья остаются на одной глубине. <math>\blacksquare</math>

	'''Оценка сложности.''' Высота <math>O(\log n)</math>, на каждом уровне <math>O(1)</math> работы (сравнения, один раскол или слияние) — операции за <math>O(\log n)</math>. Число расщеплений при вставке амортизированно <math>O(1)</math> (аргумент счётчика: узел можно расщепить лишь после того, как его заполняли вставками).		'''Оценка сложности.''' Высота <math>O(\log n)</math>, на каждом уровне <math>O(1)</math> работы (сравнения, один раскол или слияние) — операции за <math>O(\log n)</math>. Число расщеплений при вставке амортизированно <math>O(1)</math> (аргумент счётчика: узел можно расщепить лишь после того, как его заполняли вставками).

СВ: /* Трассировка примера */

2026-10-25T20:06:08Z

Трассировка примера

← Предыдущая		Версия 20:06, 25 октября 2026
Строка 428:		Строка 428:
	! Шаг !! Ключ !! Действие !! Дерево (в порядке возрастания)		! Шаг !! Ключ !! Действие !! Дерево (в порядке возрастания)
	\|-		\|-
	\| 1 \|\| 10 \|\| первый ~~лист~~ \|\| <code>[10]</code>		\| 1 \|\| 10 \|\| первый узел \|\| <code>[10]</code>
	\|-		\|-
	\| 2 \|\| 20 \|\| в ~~лист~~ <code>[10]</code> \|\| `[10 \|\| 20]`		\| 2 \|\| 20 \|\| в последний внутренний узел <code>[10]</code> \|\| <code>[10 \| 20]</code>
	\|-		\|-
	\| 3 \|\| 5 \|\| в ~~лист `~~[10 \|\| 20]` → расщепление \|\| корень <code>[10]</code>, дети <code>[5]</code>, <code>[20]</code>		\| 3 \|\| 5 \|\| в последний внутренний узел <code>[10 \| 20]</code> → расщепление \|\| корень <code>[10]</code>, дети <code>[5]</code>, <code>[20]</code>
	\|-		\|-
	\| 4 \|\| 15 \|\| спуск к <code>[20]</code> (между 10 и 20) \|\| корень <code>[10]</code>, дети <code>[5]</code>, `[15 \|\| 20]`		\| 4 \|\| 15 \|\| спуск к <code>[20]</code> (между 10 и 20) \|\| корень <code>[10]</code>, дети <code>[5]</code>, <code>[15 \| 20]</code>
	\|-		\|-
	\| 5 \|\| 25 \|\| в ~~лист `~~[15 \|\| 20]` → расщепление \|\| корень `[10 \|\| 20]<code>, дети </code>[5]<code>, </code>[15]<code>, </code>[25]`		\| 5 \|\| 25 \|\| в последний внутренний узел <code>[15 \| 20]</code> → расщепление \|\| корень <code>[10 \| 20]</code>, дети <code>[5]</code>, <code>[15]</code>, <code>[25]</code>
	\|-		\|-
	\| 6 \|\| 30 \|\| в ~~лист~~ <code>[25]</code> \|\| корень `[10 \|\| 20]<code>, дети </code>[5]<code>, </code>[15]<code>, </code>[25 \|\| 30]`		\| 6 \|\| 30 \|\| в последний внутренний узел <code>[25]</code> \|\| корень <code>[10 \| 20]</code>, дети <code>[5]</code>, <code>[15]</code>, <code>[25 \| 30]</code>
	\|}		\|}

	На шаге 3 расщепился ~~лист~~, на шаге 5 — ~~лист~~, а его средний ключ (20) поднялся в корень, превратив его в 3-узел; высота не менялась. Все ключи выходят в порядке возрастания, <code>validate()</code> подтверждает инварианты.		На шаге 3 расщепился последний внутренний узел, на шаге 5 — последний внутренний узел, а его средний ключ (20) поднялся в корень, превратив его в 3-узел; высота не менялась. Все ключи выходят в порядке возрастания, <code>validate()</code> подтверждает инварианты.

	== Корректность и оценка сложности ==		== Корректность и оценка сложности ==

СВ: /* Реализация на C++ */

2026-10-25T20:05:21Z

Реализация на C++

← Предыдущая		Версия 20:05, 25 октября 2026
Строка 231:		Строка 231:
	K keys[2];		K keys[2];
	Node* child[3] = {nullptr, nullptr, nullptr};		Node* child[3] = {nullptr, nullptr, nullptr};
	bool leaf = true;		bool leaf = true; // последний внутренний узел; внешние листья не хранятся
	};		};

Строка 393:		Строка 393:
	* При переполнении узел временно содержит три ключа; расщепление оставляет по одному ключу в двух узлах и поднимает средний.		* При переполнении узел временно содержит три ключа; расщепление оставляет по одному ключу в двух узлах и поднимает средний.
	* Наследование ребёнка <code>child[i+1]</code> при вставке ключа — частый источник ошибок; сверяйтесь с псевдокодом.		* Наследование ребёнка <code>child[i+1]</code> при вставке ключа — частый источник ошибок; сверяйтесь с псевдокодом.
	* <code>validate</code> проверяет все три инварианта, включая одну глубину листьев.		* <code>validate</code> проверяет все три инварианта, включая одну глубину внешних листьев.
			* В коде внешние листья не хранятся: <code>leaf == true</code> означает последний внутренний узел, а его дети — внешние листья. Глубина в <code>validate</code> считается по последним внутренним узлам (на 1 меньше глубины внешних листьев) и не влияет на проверку баланса.
	* Удаление реализуется тем же рекурсивным приёмом с «подъёмом недостачи», но содержит больше случаев (заимствование/слияние).		* Удаление реализуется тем же рекурсивным приёмом с «подъёмом недостачи», но содержит больше случаев (заимствование/слияние).

СВ: /* Операция: удаление (Delete) */

2026-10-25T20:03:58Z

Операция: удаление (Delete)

← Предыдущая		Версия 20:03, 25 октября 2026
Строка 177:		Строка 177:
	'''Пошаговое описание.'''		'''Пошаговое описание.'''

	# Найти ключ; если он во внутреннем узле, заменить его ключом-предшественником из ~~листа~~ (как в BST).		# Найти ключ; если он во внутреннем узле, заменить его ключом-предшественником из последнего внутреннего узла (как в BST).
	# Удалить ключ из ~~листа~~.		# Удалить ключ из последнего внутреннего узла.
	# Если ~~лист~~ опустел: - у соседа '''справа/слева есть 3-узел''' — заимствовать: перебросить ключ через родителя; - у соседей только 2-узлы — слить узел с соседом, опустив ключ родителя.		# Если последний внутренний узел опустел: - у соседа '''справа/слева есть 3-узел''' — заимствовать: перебросить ключ через родителя; - у соседей только 2-узлы — слить узел с соседом, опустив ключ родителя.
	# Если родитель потерял ребёнка и опустел — повторить пункт 3 выше.		# Если родитель потерял ребёнка и опустел — повторить пункт 3 выше.
	# Если корень опустел — сделать его единственного ребёнка новым корнем (высота −1).		# Если корень опустел — сделать его единственного ребёнка новым корнем (высота −1).

	'''Инвариант.''' Свойства порядка и одна глубина листьев сохраняются; временным нарушением может быть лишь недостача ключей в одном узле.		'''Инвариант.''' Свойства порядка и одна глубина внешних листьев сохраняются; временным нарушением может быть лишь недостача ключей в одном узле.

	'''Псевдокод (схема).'''		'''Псевдокод (схема).'''

	<syntaxhighlight lang="text" ~~line~~>		<syntaxhighlight lang="text">
	Алгоритм Delete(T, k)		Алгоритм Delete(T, k)
	найти ключ k в узле z		1 найти ключ k в узле z
	if k во внутреннем узле		2 if k во внутреннем узле
	заменить k его предшественником из ~~листа~~; z ← этот ~~лист~~		3 заменить k его предшественником из последнего внутреннего узла; z ← этот узел
	удалить k из z		4 удалить k из z
	while z опустел и z ≠ root[T]		5 while z опустел и z ≠ root[T]
	p ← parent[z]		6 p ← parent[z]
	if у соседа z есть три ребёнка # 3-узел		7 if у соседа z есть три ребёнка # 3-узел
	заимствовать ключ у соседа через p (перераспределение)		8 заимствовать ключ у соседа через p (перераспределение)
	break		9 break
	else		10 else
	слить z с соседом, опустив разделяющий ключ из p		11 слить z с соседом, опустив разделяющий ключ из p
	z ← p # недостача поднялась выше		12 z ← p # недостача поднялась выше
	if root[T] опустел		13 if root[T] опустел
	root[T] ← единственный ребёнок root[T] # высота −1		14 root[T] ← единственный ребёнок root[T] # высота −1
	</syntaxhighlight>		</syntaxhighlight>

	Сложность: O(log n) времени; слияние/заимствование — O(1), повторов не более высоты.		Сложность: O(log n) времени; слияние/заимствование — O(1), повторов не более высоты.

	Корректность: каждое действие восстанавливает степень узлов, сохраняя одну глубину листьев.		Корректность: каждое действие восстанавливает степень узлов, сохраняя одну глубину внешних листьев.

	'''Крайние случаи.''' Удаление последнего ключа корня~~-листа~~ — дерево пустеет. Удаление отсутствующего ключа — no-op.		'''Крайние случаи.''' Удаление последнего ключа корня — последнего внутреннего узла — дерево пустеет. Удаление отсутствующего ключа — no-op.

	[[Файл:tree23-04-delete.svg\|frame\|none\|700px\|Рис. 4. Опустевший 2-узел восстанавливают заимствованием у соседа-3-узла или слиянием с соседом; слияние может подняться до корня и уменьшить высоту.]]		[[Файл:tree23-04-delete.svg\|frame\|none\|700px\|Рис. 4. Опустевший 2-узел восстанавливают заимствованием у соседа-3-узла или слиянием с соседом; слияние может подняться до корня и уменьшить высоту.]]

СВ: /* Операция: вставка (Insert) */

2026-10-25T20:03:14Z

Операция: вставка (Insert)

← Предыдущая		Версия 20:03, 25 октября 2026
Строка 114:		Строка 114:
	=== Операция: вставка (Insert) ===		=== Операция: вставка (Insert) ===

	'''Идея.''' Спуститься до ~~листа~~ и вставить ключ; при переполнении узла — '''расщепить''' его, подняв средний ключ в родителя (рекурсивно вверх).		'''Идея.''' Спуститься до последнего внутреннего узла и вставить ключ; при переполнении узла — '''расщепить''' его, подняв средний ключ в родителя (рекурсивно вверх).

	'''Пошаговое описание.'''		'''Пошаговое описание.'''

	# Спуск до ~~листа~~ по ключу.		# Спуск до последнего внутреннего узла по ключу.
	# Вставка ключа в ~~лист~~ (~~лист~~ временно может стать 4-узлом с тремя ключами).		# Вставка ключа в последний внутренний узел (он временно может стать 4-узлом с тремя ключами).
	# Если ключей стало три — расщепление: крайние остаются в двух 2-узлах, средний поднимается.		# Если ключей стало три — расщепление: крайние остаются в двух 2-узлах, средний поднимается.
	# Если переполнился родитель — повторить расщепление выше.		# Если переполнился родитель — повторить расщепление выше.
	# Если расщепился корень — создать новый корень; высота растёт на 1.		# Если расщепился корень — создать новый корень; высота растёт на 1.

	'''Инвариант.''' После каждого шага дерево остаётся 2-3 деревом (порядок, степень, одна глубина листьев); нарушением может быть лишь временное переполнение одного узла.		'''Инвариант.''' После каждого шага дерево остаётся 2-3 деревом (порядок, степень, одна глубина внешних листьев); нарушением может быть лишь временное переполнение одного узла.

	'''Псевдокод (рекурсивный, возвращает «подъём» при переполнении).'''		'''Псевдокод (рекурсивный, возвращает «подъём» при переполнении).'''

	<syntaxhighlight lang="text" ~~line~~>		<syntaxhighlight lang="text">
	Алгоритм Insert(T, k)		Алгоритм Insert(T, k)
	(overflow, mid, right) ← Insert-Rec(root[T], k)		1 (overflow, mid, right) ← Insert-Rec(root[T], k)
	if overflow # расщепился корень		2 if overflow # расщепился корень
	newRoot ← новый узел с ключом mid		3 newRoot ← новый узел с ключом mid
	child[newRoot][0] ← root[T]; child[newRoot][1] ← right		4 child[newRoot][0] ← root[T]; child[newRoot][1] ← right
	root[T] ← newRoot # высота +1		5 root[T] ← newRoot # высота +1

	Алгоритм Insert-Rec(node, k) # возвращает (overflow, mid, right)		Алгоритм Insert-Rec(node, k) # возвращает (overflow, mid, right)
	if ~~leaf[~~node]		6 if все дети node — внешние листья
	вставить k в keys[node] (с сохранением порядка)		7 вставить k в keys[node] (с сохранением порядка)
	if num[node] ≤ 2		8 if num[node] ≤ 2
	return (false, NIL, NIL)		9 return (false, NIL, NIL)
	keys[node] ← keys[node][0] # левый 2-узел		10 keys[node] ← keys[node][0] # левый 2-узел
	right ← ~~лист~~ с ключом keys[node][2] # правый 2-узел		11 right ← 2-узел с ключом keys[node][2] # правый 2-узел
	return (true, keys[node][1], right) # средний ключ — вверх		12 return (true, keys[node][1], right) # средний ключ — вверх
	i ← 0		13 i ← 0
	while i < num[node] and keys[node][i] < k		14 while i < num[node] and keys[node][i] < k
	i ← i + 1		15 i ← i + 1
	(overflow, mid, right) ← Insert-Rec(child[node][i], k)		16 (overflow, mid, right) ← Insert-Rec(child[node][i], k)
	if not overflow		17 if not overflow
	return (false, NIL, NIL)		18 return (false, NIL, NIL)
	вставить mid в keys[node] (позиция i) и right в child[node] (позиция i+1)		19 вставить mid в keys[node] (позиция i) и right в child[node] (позиция i+1)
	if num[node] ≤ 2		20 if num[node] ≤ 2
	return (false, NIL, NIL)		21 return (false, NIL, NIL)
	left ← 2-узел с keys[node][0]		22 left ← 2-узел с keys[node][0]
	rightNode ← 2-узел с keys[node][2]		23 rightNode ← 2-узел с keys[node][2]
	return (true, keys[node][1], rightNode)		24 return (true, keys[node][1], rightNode)
	</syntaxhighlight>		</syntaxhighlight>

Строка 161:		Строка 161:

	Корректность: расщепление заменяет один узел двумя на том же уровне, поэтому глубина		Корректность: расщепление заменяет один узел двумя на том же уровне, поэтому глубина
	листьев не меняется; новый корень увеличивает глубину сразу всех листьев.		внешних листьев не меняется; новый корень увеличивает глубину сразу всех внешних листьев.


	'''Разбор на примере.''' Вставка 20 в 3-узел <code>[15 \| 25]</code> даёт временный 4-узел <code>[15 \| 20 \| 25]</code>, который расщепляется: ключ 20 поднимается, а 15 и 25 образуют два 2-узла (рис. 2). Если при этом переполнился и родитель, расщепление идёт выше; расщепление корня повышает высоту (рис. 3).		'''Разбор на примере.''' Вставка 20 в 3-узел <code>[15 \| 25]</code> даёт временный 4-узел <code>[15 \| 20 \| 25]</code>, который расщепляется: ключ 20 поднимается, а 15 и 25 образуют два 2-узла (рис. 2). Если при этом переполнился и родитель, расщепление идёт выше; расщепление корня повышает высоту (рис. 3).

	'''Крайние случаи.''' Вставка в пустое дерево — единственный ~~лист~~. Вставка дубликата — либо игнорируется, либо хранится счётчик повторов.		'''Крайние случаи.''' Вставка в пустое дерево — единственный внутренний узел с двумя внешними листьями. Вставка дубликата — либо игнорируется, либо хранится счётчик повторов.

	[[Файл:tree23-02-insert-split.svg\|frame\|none\|700px\|Рис. 2. Вставка в 3-узел: временный 4-узел расщепляется, средний ключ поднимается в родителя.]]		[[Файл:tree23-02-insert-split.svg\|frame\|none\|700px\|Рис. 2. Вставка в 3-узел: временный 4-узел расщепляется, средний ключ поднимается в родителя.]]

СВ: /* Операция: поиск (Search) */

2026-10-25T20:02:27Z

Операция: поиск (Search)

← Предыдущая		Версия 20:02, 25 октября 2026
Строка 90:		Строка 90:
	'''Псевдокод.'''		'''Псевдокод.'''

	<syntaxhighlight lang="text" ~~line~~>		<syntaxhighlight lang="text">
	Алгоритм Search(T, k)		Алгоритм Search(T, k)
	cur ← root[T]		1 cur ← root[T]
	while cur ≠ NIL		2 while cur ≠ NIL
	i ← 0		3 i ← 0
	while i < num[cur] and keys[cur][i] < k		4 while i < num[cur] and keys[cur][i] < k
	i ← i + 1		5 i ← i + 1
	if i < num[cur] and keys[cur][i] = k		6 if i < num[cur] and keys[cur][i] = k
	return cur		7 return cur
	if leaf[cur]		8 if leaf[cur]
	return NIL		9 return NIL
	cur ← child[cur][i]		10 cur ← child[cur][i]
	return NIL		11 return NIL
			</syntaxhighlight>

	Сложность: O(log n) — не длиннее высоты.		Сложность: O(log n) — не длиннее высоты.

	Корректность: выбор ребёнка следует порядку ключей; свойство порядка гарантирует,		Корректность: выбор ребёнка следует порядку ключей; свойство порядка гарантирует,
	что при наличии k спуск приведёт к нему.		что при наличии k спуск приведёт к нему.
	~~</syntaxhighlight>~~

	'''Крайние случаи.''' Ключ меньше всех — спуск в <code>child[0]</code>; больше всех — в последнего ребёнка.		'''Крайние случаи.''' Ключ меньше всех — спуск в <code>child[0]</code>; больше всех — в последнего ребёнка.

СВ: /* Мотивация и интуиция */

2026-10-25T20:00:54Z

Мотивация и интуиция

← Предыдущая		Версия 20:00, 25 октября 2026
Строка 51:		Строка 51:
	== Мотивация и интуиция ==		== Мотивация и интуиция ==

	Двоичное дерево поиска простое, но легко вырождается в список. Сбалансированные BST ([[АВЛ-дерево\|АВЛ]], [[Красно-чёрное дерево\|КЧ]]) чинят это поворотами и хранением баланса. 2-3 дерево предлагает другой подход: '''разрешить узлам хранить больше одного ключа'''. Как только узлу разрешено иметь три ребёнка, дереву становится «тесно» вырождаться: у внутренних узлов минимум '''два''' ребёнка, а значит, высота уже не может превысить <math>\log_2 n</math>.		Двоичное дерево поиска простое, но легко вырождается в список. Сбалансированные BST ([[АВЛ-дерево\|АВЛ]], [[Красно-чёрное дерево\|КЧ]]) чинят это поворотами и хранением баланса. 2-3 дерево предлагает другой подход: '''разрешить узлам хранить больше одного ключа'''. Как только узлу разрешено иметь три ребёнка, дереву становится «тесно» вырождаться: у внутренних узлов минимум '''два''' ребёнка, а значит, высота уже не может превысить <math>\log_2(n+1)</math>.

	Ключевая идея — '''локальность балансировки'''. Когда ~~лист~~ переполняется (в него попадает третий ключ), узел временно становится 4-узлом и '''расщепляется''': средний ключ уходит в родителя, а крайние образуют два 2-узла. Баланс восстанавливается локально, а если переполнится родитель — расщепление продолжается вверх. Единственный случай, когда высота меняется, — расщепление корня. Аналогично удаление «разгружает» узел заимствованием у соседа или слиянием.		Ключевая идея — '''локальность балансировки'''. Когда последний внутренний узел переполняется (в него попадает третий ключ), узел временно становится 4-узлом и '''расщепляется''': средний ключ уходит в родителя, а крайние образуют два 2-узла. Баланс восстанавливается локально, а если переполнится родитель — расщепление продолжается вверх. Единственный случай, когда высота меняется, — расщепление корня. Аналогично удаление «разгружает» узел заимствованием у соседа или слиянием.

	Так 2-3 дерево поддерживает идеальную балансировку '''структурно''', без единого поля высоты или цвета: инварианты формы гарантируют <math>\Theta(\log n)</math> сами по себе. Это делает 2-3 деревья удобной учебной моделью и мостиком к B-деревьям и красно-чёрным деревьям.		Так 2-3 дерево поддерживает идеальную балансировку '''структурно''', без единого поля высоты или цвета: инварианты формы гарантируют <math>\Theta(\log n)</math> сами по себе. Это делает 2-3 деревья удобной учебной моделью и мостиком к B-деревьям и красно-чёрным деревьям.

СВ: /* Определения */

2026-10-25T20:00:06Z

Определения

← Предыдущая		Версия 20:00, 25 октября 2026
Строка 39:		Строка 39:
	# '''все листья находятся на одной глубине''' (дерево идеально сбалансировано).		# '''все листья находятся на одной глубине''' (дерево идеально сбалансировано).

	'''2-узел''' — узел с одним ключом и двумя детьми. '''3-узел''' — узел с двумя ключами и тремя детьми. '''Лист''' — внешний узел, не хранящий ключей (в ~~разных изложениях листьями называют~~ и ~~сами ключи)~~.		'''2-узел''' — узел с одним ключом и двумя детьми. '''3-узел''' — узел с двумя ключами и тремя детьми. '''Лист''' — внешний узел, не хранящий ключей. В этой статье ключи хранятся только во внутренних узлах, а все внешние листья лежат на одной глубине; в компактной реализации внешние листья не хранятся, и флаг <code>leaf</code> означает последний внутренний узел.

	'''Высота <math>h</math>.''' Внутренний узел имеет не менее двух детей, поэтому в дереве высоты <math>h</math> не менее <math>2^h</math> листьев, откуда <math>h \le \log_2 n</math>. С другой стороны, не более трёх детей даёт <math>h \ge \log_3 n</math>.		'''Высота <math>h</math>.''' Внутренний узел имеет не менее двух детей, поэтому в дереве высоты <math>h</math> не менее <math>2^h</math> внешних листьев, откуда <math>h \le \log_2 L</math>. С другой стороны, не более трёх детей даёт <math>h \ge \log_3 L</math>.

	'''Соответствие.''' 2-3 дерево — это B-дерево порядка (степени) 3. Обобщение узлов до «2, 3 или 4 детей» даёт [[2-3-4 дерево]], а через кодировку 3-узлов красными рёбрами — красно-чёрное дерево.		'''Соответствие.''' 2-3 дерево — это B-дерево порядка (степени) 3. Обобщение узлов до «2, 3 или 4 детей» даёт [[2-3-4 дерево]], а через кодировку 3-узлов красными рёбрами — красно-чёрное дерево.

	'''Обозначения.''' <math>n</math> — число ключей; <math>h</math> — высота; <math>\log</math> — двоичный, если не оговорено.		'''Обозначения.''' <math>n</math> — число ключей; <math>L</math> — число внешних листьев; <math>h</math> — высота; <math>\log</math> — двоичный, если не оговорено.

	[[Файл:tree23-01-structure.svg\|frame\|none\|700px\|Рис. 1. 2-узлы и 3-узлы; все листья на одной глубине. Высота заключена между <math>\log_3 n</math> и <math>\log_2 n</math>.]]		[[Файл:tree23-01-structure.svg\|frame\|none\|700px\|Рис. 1. 2-узлы и 3-узлы; все листья на одной глубине. Высота заключена между <math>\log_3 L</math> и <math>\log_2 L</math>.]]

	== Мотивация и интуиция ==		== Мотивация и интуиция ==

СВ: /* TL;DR */

2026-10-25T19:59:04Z

TL;DR

← Предыдущая		Версия 19:59, 25 октября 2026
Строка 1:		Строка 1:
	== TL;DR ==		== TL;DR ==

	2-3 дерево (2-3 tree) — сбалансированное дерево поиска, в котором '''каждый внутренний узел имеет двух или трёх детей''' и хранит один или два ключа, а '''все листья лежат на одной глубине'''. Благодаря тому, что у каждого узла не меньше двух детей, высота не превосходит <math>\log_2 n</math>, а благодаря тому, что не больше трёх, — не меньше <math>\log_3 n</math>; дерево всегда идеально сбалансировано без хранения полей баланса. Вставка добавляет ключ в ~~лист~~ и при переполнении '''расщепляет''' узел, поднимая средний ключ в родителя; удаление '''заимствует''' ключ у брата-3-узла или '''сливает''' узлы. Все операции работают за <math>O(\log n)</math>, а расщепления при вставке — амортизированно <math>O(1)</math>. 2-3 дерево — частный случай B-дерева (порядок 3) и родоначальник идеи, из которой выросли [[2-3-4-дерево\|2-3-4 деревья]] и [[Красно-чёрное дерево\|красно-чёрные деревья]].		2-3 дерево (2-3 tree) — сбалансированное дерево поиска, в котором '''каждый внутренний узел имеет двух или трёх детей''' и хранит один или два ключа, а '''все внешние листья лежат на одной глубине'''. Благодаря тому, что у каждого узла не меньше двух детей, высота не превосходит <math>\log_2(n+1)</math>, а благодаря тому, что не больше трёх, — не меньше <math>\log_3(n+1)</math>; дерево всегда идеально сбалансировано без хранения полей баланса. Вставка добавляет ключ в последний внутренний узел и при переполнении '''расщепляет''' узел, поднимая средний ключ в родителя; удаление '''заимствует''' ключ у брата-3-узла или '''сливает''' узлы. Все операции работают за <math>O(\log n)</math>, а расщепления при вставке — амортизированно <math>O(1)</math>. 2-3 дерево — частный случай B-дерева (порядок 3) и родоначальник идеи, из которой выросли [[2-3-4-дерево\|2-3-4 деревья]] и [[Красно-чёрное дерево\|красно-чёрные деревья]].

	{\| class="wikitable"		{\| class="wikitable"
Строка 15:		Строка 15:
	\| Балансировка \|\| Идеальная: все листья на одной глубине		\| Балансировка \|\| Идеальная: все листья на одной глубине
	\|-		\|-
	\| Высота \|\| <math>\log_3 n \le h \le \log_2 n</math>		\| Высота \|\| <math>\log_3(n+1) \le h \le \log_2(n+1)</math>
	\|-		\|-
	\| Поиск \|\| <math>O(\log n)</math>		\| Поиск \|\| <math>O(\log n)</math>
Строка 25:		Строка 25:
	\| Память \|\| <math>O(n)</math>; узел хранит 1–2 ключа и 2–3 ссылки, поля баланса не нужны		\| Память \|\| <math>O(n)</math>; узел хранит 1–2 ключа и 2–3 ссылки, поля баланса не нужны
	\|-		\|-
	\| Родственники \|\| 2-3-4 дерево, B-дерево, [[Красно-чёрное дерево\|красно-чёрное дерево]] (соответствие)		\| Родственники \|\| [[2-3-4-дерево]], [[B-дерево]], [[Красно-чёрное дерево\|красно-чёрное дерево]] (соответствие)
	\|-		\|-
	\| Где встречается \|\| учебная основа B-деревьев; идея используется в индексах СУБД и файловых систем		\| Где встречается \|\| учебная основа B-деревьев; идея используется в индексах СУБД и файловых систем