АВЛ-дерево - История изменений

СВ в 22:06, 25 октября 2026

2026-10-25T22:06:17Z

← Предыдущая		Версия 22:06, 25 октября 2026
Строка 137:		Строка 137:
	! Случай !! Форма (ключи) !! Что делают !! Итог		! Случай !! Форма (ключи) !! Что делают !! Итог
	\|-		\|-
	\| '''LL''' \|\| <math>z < y < x</math> по левому-левому пути \|\| правый поворот вокруг <math>z</math> \|\| <math>y</math> — корень		\| '''LL''' \|\| <math>x < y < z</math> по левому-левому пути \|\| правый поворот вокруг <math>z</math> \|\| <math>y</math> — корень
	\|-		\|-
	\| '''RR''' \|\| правая-правая цепочка \|\| левый поворот вокруг <math>z</math> \|\| средний — корень		\| '''RR''' \|\| правая-правая цепочка \|\| левый поворот вокруг <math>z</math> \|\| средний — корень
Строка 209:		Строка 209:
	Сложность: O(log n) времени, O(1) памяти; не более одного поворота (одинарного или двойного).		Сложность: O(log n) времени, O(1) памяти; не более одного поворота (одинарного или двойного).

	Корректность: поворот в узле x восстанавливает \|BF(x)\| ≤ 1 и возвращает высоту поддерева к прежнему значению, поэтому выше ничего не нарушается.		Корректность: поворот в узле x восстанавливает \|BF(x)\| ≤ 1 и возвращает высоту
			поддерева к прежнему значению, поэтому выше ничего не нарушается.

	'''Разбор на примере.''' Вставка в пустое дерево ключей <math>10, 20, 30, 40, 50, 25</math> (рис. 4):		'''Разбор на примере.''' Вставка в пустое дерево ключей <math>10, 20, 30, 40, 50, 25</math> (рис. 4):
Строка 273:		Строка 274:
	'''Крайние случаи.''' Удаление листа — просто отцепляем. Удаление узла с одним ребёнком — ребёнок занимает место. Удаление корня — новым корнем становится ребёнок или <code>NIL</code>. Если ребёнок разбалансированного узла имеет баланс 0 (ситуация, невозможная при вставке, но возможная при удалении), достаточно одинарного поворота.		'''Крайние случаи.''' Удаление листа — просто отцепляем. Удаление узла с одним ребёнком — ребёнок занимает место. Удаление корня — новым корнем становится ребёнок или <code>NIL</code>. Если ребёнок разбалансированного узла имеет баланс 0 (ситуация, невозможная при вставке, но возможная при удалении), достаточно одинарного поворота.

	[[Файл:avl-05-delete-propagation.svg\|~~frame\|none~~\|700px\|Рис. 5. Слева — правило выбора поворота по балансу ребёнка. Справа — почему после поворота нужно продолжать вверх: высота поддерева уменьшилась, и баланс предка мог снова нарушиться.]]		[[Файл:avl-05-delete-propagation.svg\|thumb\|700px\|Рис. 5. Слева — правило выбора поворота по балансу ребёнка. Справа — почему после поворота нужно продолжать вверх: высота поддерева уменьшилась, и баланс предка мог снова нарушиться.]]

	=== Операция: поиск (search) ===		=== Операция: поиск (search) ===
Строка 302:		Строка 303:
	Полная реализация (C++17): итеративная вставка/удаление, ссылки на родителя, хранение высоты. Функция <code>validate()</code> проверяет BST-свойство, условие АВЛ, корректность высот и ссылок на родителей.		Полная реализация (C++17): итеративная вставка/удаление, ссылки на родителя, хранение высоты. Функция <code>validate()</code> проверяет BST-свойство, условие АВЛ, корректность высот и ссылок на родителей.

	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp" line>
	#include <iostream>		#include <iostream>
	#include <vector>		#include <vector>
Строка 556:		Строка 557:
	== Корректность и оценка сложности ==		== Корректность и оценка сложности ==

	{{Лемма		'''Лемма 1 (минимальное число узлов).''' Обозначим <math>N(h)</math> минимальное число узлов АВЛ-дерева высоты <math>h</math>. Тогда
	~~\|about=~~минимальное число узлов
	~~\|statement=~~Обозначим <math>N(h)</math> минимальное число узлов АВЛ-дерева высоты <math>h</math>. Тогда <math display="block">N(0) = 1, \quad N(1) = 2, \quad N(h) = N(h-1) + N(h-2) + 1.</math>		<math display="block">N(0) = 1, \quad N(1) = 2, \quad N(h) = N(h-1) + N(h-2) + 1.</math>
	~~\|proof=~~Дерево высоты <math>h</math> имеет корень и два поддерева. Чтобы минимизировать число узлов, нужно, чтобы одно поддерево имело высоту <math>h-1</math>, а другое — не менее <math>h-2</math> (разность высот не превосходит 1, и одно из поддеревьев обязательно имеет высоту <math>h-1</math>, иначе высота дерева была бы меньше <math>h</math>). Минимумы слагаются: <math>N(h) = N(h-1) + N(h-2) + 1</math>. База очевидна.
	}}		''Доказательство.'' Дерево высоты <math>h</math> имеет корень и два поддерева. Чтобы минимизировать число узлов, нужно, чтобы одно поддерево имело высоту <math>h-1</math>, а другое — не менее <math>h-2</math> (разность высот не превосходит 1, и одно из поддеревьев обязательно имеет высоту <math>h-1</math>, иначе высота дерева была бы меньше <math>h</math>). Минимумы слагаются: <math>N(h) = N(h-1) + N(h-2) + 1</math>. База очевидна. <math>\blacksquare</math>
	{{Лемма
	~~\|about=~~связь с числами Фибоначчи		'''Лемма 2 (связь с числами Фибоначчи).''' <math>N(h) = F(h+3) - 1</math>, где <math>F_1 = F_2 = 1</math>.
	~~\|statement=~~<math>N(h) = F(h+3) - 1</math>, где <math>F_1 = F_2 = 1</math>.
	~~\|proof=~~Подстановкой: <math>F(h+3) - 1 = (F(h+2)-1) + (F(h+1)-1) + 1</math>, что совпадает с рекуррентностью <math>F(k) = F(k-1) + F(k-2)</math>; базы <math>N(0) = F(3)-1 = 1</math> и <math>N(1) = F(4)-1 = 2</math> сходятся.		''Доказательство.'' Подстановкой: <math>F(h+3) - 1 = (F(h+2)-1) + (F(h+1)-1) + 1</math>, что совпадает с рекуррентностью <math>F(k) = F(k-1) + F(k-2)</math>; базы <math>N(0) = F(3)-1 = 1</math> и <math>N(1) = F(4)-1 = 2</math> сходятся. <math>\blacksquare</math>
	}}
	{{Теорема		'''Теорема (оценка высоты).''' Высота АВЛ-дерева с <math>n</math> узлами удовлетворяет <math>h \le 1.44\,\log_2(n+2)</math>.
	~~\|about=~~оценка высоты
	~~\|statement=~~Высота АВЛ-дерева с <math>n</math> узлами удовлетворяет <math>h \le 1.44\,\log_2(n+2)</math>.		''Доказательство.'' Так как <math>n \ge N(h) = F(h+3) - 1</math> и <math>F(k) \ge \varphi^{\,k}/\sqrt5</math> (стандартная оценка чисел Фибоначчи через золотое сечение <math>\varphi</math>), получаем
	~~\|proof=~~Так как <math>n \ge N(h) = F(h+3) - 1</math> и <math>F(k) \ge \varphi^{\,k}/\sqrt5</math> (стандартная оценка чисел Фибоначчи через золотое сечение <math>\varphi</math>), получаем

	<math display="block">n + 1 \ge \frac{\varphi^{\,h+3}}{\sqrt5}		<math display="block">n + 1 \ge \frac{\varphi^{\,h+3}}{\sqrt5}
	\;\Longrightarrow\;		\;\Longrightarrow\;
	h \le \log_\varphi\!(\sqrt5\,(n+1)) - 3		h \le \log_\varphi\!\bigl(\sqrt5\,(n+1)\bigr) - 3
	= \frac{\log_2(\sqrt5\,(n+1))}{\log_2\varphi} - 3 \le 1.44\,\log_2(n+2).</math>		= \frac{\log_2(\sqrt5\,(n+1))}{\log_2\varphi} - 3
	}}		\le 1.44\,\log_2(n+2). \;\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(\log n)</math> шагов спуска. Вставка и удаление проходят путь до корня, выполняя <math>O(1)</math> работы на уровень: <math>O(\log n)</math> времени и <math>O(1)</math> дополнительной памяти. При '''вставке''' поворот один, потому что он восстанавливает прежнюю высоту поддерева; при '''удалении''' поворот уменьшает высоту, поэтому балансировка может подниматься до корня — до <math>O(\log n)</math> поворотов.
Строка 582:		Строка 581:
	'''Инвариант-аргумент для поворота.''' Одинарный поворот в разбалансированном узле <math>x</math> восстанавливает <math>\|\text{BF}(x)\| \le 1</math>: если левое поддерево было выше на 2, а его ребёнок имел баланс <math>\ge 0</math>, то после правого поворота высоты детей нового корня различаются не более чем на 1, а общая высота поддерева равна прежней (до вставки). Двойной поворот сначала превращает зигзаг в цепочку, затем выправляет её. В обоих случаях BST-порядок сохраняется, так как переставляются только связи, а среднее поддерево перевешивается, как в псевдокоде.		'''Инвариант-аргумент для поворота.''' Одинарный поворот в разбалансированном узле <math>x</math> восстанавливает <math>\|\text{BF}(x)\| \le 1</math>: если левое поддерево было выше на 2, а его ребёнок имел баланс <math>\ge 0</math>, то после правого поворота высоты детей нового корня различаются не более чем на 1, а общая высота поддерева равна прежней (до вставки). Двойной поворот сначала превращает зигзаг в цепочку, затем выправляет её. В обоих случаях BST-порядок сохраняется, так как переставляются только связи, а среднее поддерево перевешивается, как в псевдокоде.

	[[Файл:avl-06-height-bound.svg\|~~thumb~~\|700px\|Рис. 6. Минимальные АВЛ-деревья высот 0–3 содержат <math>1, 2, 4, 7</math> узлов. Рост числа узлов как степень <math>\varphi</math> даёт оценку <math>h \le 1.44\log_2(n+2)</math>.]]		[[Файл:avl-06-height-bound.svg\|frame\|none\|700px\|Рис. 6. Минимальные АВЛ-деревья высот 0–3 содержат <math>1, 2, 4, 7</math> узлов. Рост числа узлов как степень <math>\varphi</math> даёт оценку <math>h \le 1.44\log_2(n+2)</math>.]]

	== Сравнение с альтернативами ==		== Сравнение с альтернативами ==
Строка 601:		Строка 600:
	\|}		\|}

	[[Файл:avl-07-complexity.svg\|~~thumb~~\|700px\|Рис. 7. Худшая высота при <math>n = 10^6</math>: АВЛ <math>\le 29</math>, красно-чёрное <math>\le 40</math>, B-дерево с <math>t=32</math> — около 4, вырожденное BST — до <math>10^6</math>.]]		[[Файл:avl-07-complexity.svg\|frame\|none\|700px\|Рис. 7. Худшая высота при <math>n = 10^6</math>: АВЛ <math>\le 29</math>, красно-чёрное <math>\le 40</math>, B-дерево с <math>t=32</math> — около 4, вырожденное BST — до <math>10^6</math>.]]

	'''Вердикт.''' АВЛ-дерево даёт меньшую высоту, а значит, меньше обращений к памяти при поиске — это важно для читающих нагрузок. Красно-чёрное дерево при чуть большей высоте делает заметно меньше перестроек при записи, поэтому побеждает в контейнерах общего назначения. Для данных на диске выбирают B-деревья, для неупорядоченного доступа — хеш-таблицы.		'''Вердикт.''' АВЛ-дерево даёт меньшую высоту, а значит, меньше обращений к памяти при поиске — это важно для читающих нагрузок. Красно-чёрное дерево при чуть большей высоте делает заметно меньше перестроек при записи, поэтому побеждает в контейнерах общего назначения. Для данных на диске выбирают B-деревья, для неупорядоченного доступа — хеш-таблицы.

СВ: /* Источники */

2026-10-08T21:28:35Z

Источники

← Предыдущая		Версия 21:28, 8 октября 2026
Строка 664:		Строка 664:
	# Wikipedia: AVL tree. URL: https://en.wikipedia.org/wiki/AVL_tree.		# Wikipedia: AVL tree. URL: https://en.wikipedia.org/wiki/AVL_tree.

	[[Category:Алгоритмы и структуры данных \| Деревья поиска]]		[[Category:Алгоритмы и структуры данных]]
			[[Category:Деревья поиска]]

СВ: /* Источники */

2026-10-08T21:27:56Z

Источники

← Предыдущая		Версия 21:27, 8 октября 2026
Строка 663:		Строка 663:
	# Guibas L. J., Sedgewick R. A Dichromatic Framework for Balanced Trees // FOCS. — 1978 ''(проверено)''; Bayer R. Symmetric Binary B-Trees // Acta Informatica. — 1972. — Vol. 1, No. 4. — P. 290–306.		# Guibas L. J., Sedgewick R. A Dichromatic Framework for Balanced Trees // FOCS. — 1978 ''(проверено)''; Bayer R. Symmetric Binary B-Trees // Acta Informatica. — 1972. — Vol. 1, No. 4. — P. 290–306.
	# Wikipedia: AVL tree. URL: https://en.wikipedia.org/wiki/AVL_tree.		# Wikipedia: AVL tree. URL: https://en.wikipedia.org/wiki/AVL_tree.

			[[Category:Алгоритмы и структуры данных \| Деревья поиска]]

СВ: /* Устройство */

2026-10-07T18:40:19Z

Устройство

← Предыдущая		Версия 18:40, 7 октября 2026
Строка 74:		Строка 74:
	\text{BF}(x) = h(\text{left}[x]) - h(\text{right}[x]).</math>		\text{BF}(x) = h(\text{left}[x]) - h(\text{right}[x]).</math>

	[[Файл:avl-01-structure.svg\|~~thumb~~\|700px\|Рис. 1. Слева допустимое АВЛ-дерево: у всех узлов <math>\|\text{BF}\| \le 1</math>. Справа цепочка из трёх узлов: у корня 30 левое поддерево выше правого на 2, <math>\text{BF}(30) = +2</math> — нарушение, требующее поворота.]]		[[Файл:avl-01-structure.svg\|frame\|none\|700px\|Рис. 1. Слева допустимое АВЛ-дерево: у всех узлов <math>\|\text{BF}\| \le 1</math>. Справа цепочка из трёх узлов: у корня 30 левое поддерево выше правого на 2, <math>\text{BF}(30) = +2</math> — нарушение, требующее поворота.]]

	== Операции и алгоритмы ==		== Операции и алгоритмы ==

СВ: /* Операции и алгоритмы */

2026-10-07T18:39:56Z

Операции и алгоритмы

← Предыдущая		Версия 18:39, 7 октября 2026
Строка 129:		Строка 129:
	<code>Left-Rotate</code> — зеркальная операция.		<code>Left-Rotate</code> — зеркальная операция.

	[[Файл:avl-02-single-rotations.svg\|~~thumb~~\|700px\|Рис. 2. Случай LL (левая цепочка) выправляется правым поворотом, случай RR (правая цепочка) — левым. Средний по ключу узел становится корнем, у всех узлов BF возвращается к 0.]]		[[Файл:avl-02-single-rotations.svg\|frame\|none\|700px\|Рис. 2. Случай LL (левая цепочка) выправляется правым поворотом, случай RR (правая цепочка) — левым. Средний по ключу узел становится корнем, у всех узлов BF возвращается к 0.]]

	'''Четыре случая.''' Первый узел на пути вверх, где <math>\|\text{BF}\| = 2</math>, называется '''разбалансированным'''. Его лечат так:		'''Четыре случая.''' Первый узел на пути вверх, где <math>\|\text{BF}\| = 2</math>, называется '''разбалансированным'''. Его лечат так:
Строка 219:		Строка 219:
	* <math>25</math>: <math>\text{BF}(20) = -2</math>, при этом <math>\text{BF}(40) = +1</math> (случай RL) → двойной поворот: правый вокруг 40, затем левый вокруг 20; корнем поддерева становится 30.		* <math>25</math>: <math>\text{BF}(20) = -2</math>, при этом <math>\text{BF}(40) = +1</math> (случай RL) → двойной поворот: правый вокруг 40, затем левый вокруг 20; корнем поддерева становится 30.

	[[Файл:avl-04-insert-trace.svg\|~~thumb~~\|700px\|Рис. 4. Состояния после балансировки при вставке <math>10, 20, 30, 40, 50, 25</math>. Видны случай RR (панели 2–3) и случай RL с двойным поворотом (панель 4).]]		[[Файл:avl-04-insert-trace.svg\|frame\|none\|700px\|Рис. 4. Состояния после балансировки при вставке <math>10, 20, 30, 40, 50, 25</math>. Видны случай RR (панели 2–3) и случай RL с двойным поворотом (панель 4).]]

	'''Крайние случаи.''' Вставка в пустое дерево — новый узел сразу корень. Вставка ключа, который уже есть, — отклоняется. Случай, когда перевес уходит в одну сторону цепочкой, немедленно исправляется одинарным поворотом.		'''Крайние случаи.''' Вставка в пустое дерево — новый узел сразу корень. Вставка ключа, который уже есть, — отклоняется. Случай, когда перевес уходит в одну сторону цепочкой, немедленно исправляется одинарным поворотом.
Строка 273:		Строка 273:
	'''Крайние случаи.''' Удаление листа — просто отцепляем. Удаление узла с одним ребёнком — ребёнок занимает место. Удаление корня — новым корнем становится ребёнок или <code>NIL</code>. Если ребёнок разбалансированного узла имеет баланс 0 (ситуация, невозможная при вставке, но возможная при удалении), достаточно одинарного поворота.		'''Крайние случаи.''' Удаление листа — просто отцепляем. Удаление узла с одним ребёнком — ребёнок занимает место. Удаление корня — новым корнем становится ребёнок или <code>NIL</code>. Если ребёнок разбалансированного узла имеет баланс 0 (ситуация, невозможная при вставке, но возможная при удалении), достаточно одинарного поворота.

	[[Файл:avl-05-delete-propagation.svg\|~~thumb~~\|700px\|Рис. 5. Слева — правило выбора поворота по балансу ребёнка. Справа — почему после поворота нужно продолжать вверх: высота поддерева уменьшилась, и баланс предка мог снова нарушиться.]]		[[Файл:avl-05-delete-propagation.svg\|frame\|none\|700px\|Рис. 5. Слева — правило выбора поворота по балансу ребёнка. Справа — почему после поворота нужно продолжать вверх: высота поддерева уменьшилась, и баланс предка мог снова нарушиться.]]

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

СВ: /* Операции и алгоритмы */

2026-10-07T18:38:59Z

Операции и алгоритмы

← Предыдущая		Версия 18:38, 7 октября 2026
Строка 146:		Строка 146:
	\|}		\|}

	[[Файл:avl-03-double-rotations.svg\|~~thumb~~\|700px\|Рис. 3. Случаи LR и RL — «зигзаги». Их выправляют два поворота подряд; медиана по ключу становится корнем поддерева.]]		[[Файл:avl-03-double-rotations.svg\|frame\|none\|700px\|Рис. 3. Случаи LR и RL — «зигзаги». Их выправляют два поворота подряд; медиана по ключу становится корнем поддерева.]]

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

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

2026-10-04T20:03:00Z

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

← Предыдущая		Версия 20:03, 4 октября 2026
Строка 569:		Строка 569:
	\|about=оценка высоты		\|about=оценка высоты
	\|statement=Высота АВЛ-дерева с <math>n</math> узлами удовлетворяет <math>h \le 1.44\,\log_2(n+2)</math>.		\|statement=Высота АВЛ-дерева с <math>n</math> узлами удовлетворяет <math>h \le 1.44\,\log_2(n+2)</math>.
	}}		\|proof=Так как <math>n \ge N(h) = F(h+3) - 1</math> и <math>F(k) \ge \varphi^{\,k}/\sqrt5</math> (стандартная оценка чисел Фибоначчи через золотое сечение <math>\varphi</math>), получаем
	~~'''Доказательство.'''~~Так как <math>n \ge N(h) = F(h+3) - 1</math> и <math>F(k) \ge \varphi^{\,k}/\sqrt5</math> (стандартная оценка чисел Фибоначчи через золотое сечение <math>\varphi</math>), получаем

	<math display="block">n + 1 \ge \frac{\varphi^{\,h+3}}{\sqrt5}		<math display="block">n + 1 \ge \frac{\varphi^{\,h+3}}{\sqrt5}
	\;\Longrightarrow\;		\;\Longrightarrow\;
	h \le \log_\varphi\!~~\bigl~~(\sqrt5\,(n+1)~~\bigr~~) - 3		h \le \log_\varphi\!(\sqrt5\,(n+1)) - 3
	= \frac{\log_2(\sqrt5\,(n+1))}{\log_2\varphi} - 3		= \frac{\log_2(\sqrt5\,(n+1))}{\log_2\varphi} - 3 \le 1.44\,\log_2(n+2).</math>
	\le 1.44\,\log_2(n+2).
	}}		}}


	'''Следствия.''' Поиск, минимум/максимум и поиск преемника выполняют <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(\log n)</math> шагов спуска. Вставка и удаление проходят путь до корня, выполняя <math>O(1)</math> работы на уровень: <math>O(\log n)</math> времени и <math>O(1)</math> дополнительной памяти. При '''вставке''' поворот один, потому что он восстанавливает прежнюю высоту поддерева; при '''удалении''' поворот уменьшает высоту, поэтому балансировка может подниматься до корня — до <math>O(\log n)</math> поворотов.

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

2026-10-04T20:00:31Z

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

← Предыдущая		Версия 20:00, 4 октября 2026
Строка 569:		Строка 569:
	\|about=оценка высоты		\|about=оценка высоты
	\|statement=Высота АВЛ-дерева с <math>n</math> узлами удовлетворяет <math>h \le 1.44\,\log_2(n+2)</math>.		\|statement=Высота АВЛ-дерева с <math>n</math> узлами удовлетворяет <math>h \le 1.44\,\log_2(n+2)</math>.
	~~\|proof=~~Так как <math>n \ge N(h) = F(h+3) - 1</math> и <math>F(k) \ge \varphi^{\,k}/\sqrt5</math> (стандартная оценка чисел Фибоначчи через золотое сечение <math>\varphi</math>), получаем		}}
			'''Доказательство.'''Так как <math>n \ge N(h) = F(h+3) - 1</math> и <math>F(k) \ge \varphi^{\,k}/\sqrt5</math> (стандартная оценка чисел Фибоначчи через золотое сечение <math>\varphi</math>), получаем

	<math display="block">n + 1 \ge \frac{\varphi^{\,h+3}}{\sqrt5}		<math display="block">n + 1 \ge \frac{\varphi^{\,h+3}}{\sqrt5}

СВ: Новая страница: «== TL;DR == АВЛ-дерево (AVL tree) — первое в истории сбалансированное двоичное дерево поиска, в к...»

2026-10-04T19:59:06Z

Новая страница: «== TL;DR == АВЛ-дерево (AVL tree) — первое в истории сбалансированное двоичное дерево поиска, в к...»

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