67 lines
3.5 KiB
Markdown
67 lines
3.5 KiB
Markdown
#структура_данных
|
||
|
||
![[Pasted image 20250115090212.png]]
|
||
|
||
> АВЛ-деревья являются деревьями BST, которые балансируют себя с помощью поворотов; это гарантирует, что их высота будет равна $O(log(n))$
|
||
|
||
АВЛ-деревья составляют разновидность самобалансируемых [[Бинарное дерево поиска (Binary Search Tree - BST)]]. Это означает, что АВЛ-деревья сохраняют высоту $O(log(n))$.
|
||
|
||
|
||
АВЛ-дерево обеспечивает нужную высоту O(log n), которая достигается
|
||
самобалансировкой и поворотами.
|
||
|
||
|
||
|
||
Аббревиатура АВЛ образована от фамилий ученых, придумавших эту структуру: Адельсон-Вельский и Ландис
|
||
|
||
|
||
***
|
||
|
||
## Поворот дерева
|
||
|
||
![[Pasted image 20250115090415.png]]
|
||
Дерево не сбалансировано — одна сторона длиннее другой.
|
||
|
||
Мы выполняем поворот влево, начиная с несбалансированного дерева
|
||
с корневым узлом A и заканчивая сбалансированным деревом с корневым
|
||
узлом B.
|
||
|
||
После поворота АВЛ-деревья сами перебалансируются
|
||
|
||
Чтобы дерево знало, когда требуется самобалансировка, оно должно хра-
|
||
нить дополнительную информацию. В каждом узле хранится один или два
|
||
вида информации: значение высоты или значение, которое иногда называют
|
||
коэффициентом балансировки. Этот коэффициент должен быть равен –1,
|
||
0 или 1.
|
||
|
||
![[Pasted image 20250115090550.png]]
|
||
|
||
Коэффициент балансировки сообщает, какой дочерний узел выше и на-
|
||
сколько. По коэффициенту балансировки дерево может определить, когда
|
||
следует проводить перебалансировку. Значение 0 означает, что дерево
|
||
сбалансировано. Со значениями –1 или 1 тоже все нормально, потому что,
|
||
напомним, АВЛ-деревья не обязаны быть идеально сбалансированы: раз-
|
||
ность 1 допустима.
|
||
Но если коэффициент балансировки падает ниже –1 или поднимается
|
||
выше 1, дерево нуждается в перебалансировке.
|
||
|
||
![[Pasted image 20250115090706.png]]
|
||
|
||
### Пример
|
||
при добавлении узла 2
|
||
![[Pasted image 20250115090829.png]]
|
||
после балансировки
|
||
![[Pasted image 20250115090921.png]]
|
||
|
||
|
||
АВЛ-деревья хороши, если требуется сбалансированное дерево BST
|
||
|
||
|
||
Связанные темы:
|
||
- [[Дерево (Tree)]]
|
||
- [[Бинарное дерево поиска (Binary Search Tree - BST)]]
|
||
- [[Бинарное дерево (Binary tree)]]
|
||
- [[Граф (Graph)]]
|
||
|
||
Источники:
|
||
- [[Адитья Бхаргава - Грокаем Алгоритмы]] |