- •Деревья. Бинарные деревья.
- •Прошивка бинарных деревьев
- •Нисходящий обход с прошивкой
- •Смешанный обход с прошивкой
- •Представление любого
- •алгоритм
- •Сбалансированные
- •операции
- •Показатель
- •Включение
- •виды балансировки
- •Удаление
- •Балансировка через массив
- •Красно-черные деревья
- •RB- бинарное дерево со след свойствами
- •Преимущества RB
- •реализация
- •Приложения деревьев
- •Алгоритм Хаффмана
Деревья. Бинарные деревья.
Прошивка бинарных деревьев
►замена по определенному правилу пустых указателей на потомков указателями на последующие узлы, соответствующие обходу
►N
►( N+1) NULL
►"нити"
Нисходящий обход с прошивкой
|
1 |
|
4 |
|
|
|
|
|
2 |
|
|
3 |
|
5 |
7 |
|
|
6 |
|
|
|
|
Смешанный обход с прошивкой
3 6
2 |
5 |
7 |
1 4
Представление любого
дерева, леса бинарными деревьями.
a
b c d
e f g h i k
алгоритм
►В каждом узле оставить только ветвь к старшему сыну;
►2. Соединить горизонтальными ребрами всех братьев одного отца;
►3 Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых
сыновей, а горизонтальные – правых
►корни всех поддеревьев леса соединить горизонтальными связями.
b |
|
a |
g |
h |
|
c |
|
i |
|
d |
e |
|
f |
k l m |
Сбалансированные
деревья AVL-деревья
Дерево является
СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев
различается не более чем на 1.
Адельсоном-Вельским и Ландисом АВЛ-дерево AVL-дерево
операции
►Вставить новый элемент ►Удалить заданный элемент ►Поиск заданного элемента
Показатель
сбалансированногсти
► Левое (L) - узел левоперевешивающий, если самый длинный путь по ее левому поддереву на единицу больше самого длинного пути по ее правому поддереву
► Сбалансированное (B) - равны наиболее длинные пути по обеим ее поддеревьям
► Правое (R) - узел правоперевешивающий, если самый длинный путь по ее правому поддереву на единицу больше самого длинного пути по ее левому поддереву