Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Структуры и алгоритмы обработки данных на ЭВМ АВЛ-дерево
Содержание
- 1. Структуры и алгоритмы обработки данных на ЭВМ АВЛ-дерево
- 2. Дать определение АВЛ-дерева;Рассмотреть способы балансировки АВЛ-дерева;Научиться выполнять
- 3. АВЛ–дерево - это структура данных, изобретенная советскими
- 4. Пример АВЛ-дерева
- 5. struct Tree{ int Value; Tree *Right, *Left;};Структура АВЛ-дереваВ рассматриваемых примерах программная структура АВЛ-дерева будет иметь следующий вид:
- 6. Балансировка АВЛ-дерева LL - вращениеСуществует 4 вида
- 7. Tree* LL_Rotation(Tree* T2 ){ Tree* T1;
- 8. Балансировка АВЛ-дерева RR - вращениеДанная ситуация возникает
- 9. Балансировка АВЛ-дерева RR - вращениеДанная ситуация возникает
- 10. Балансировка АВЛ-дерева LR - вращениеДанная ситуация возникает
- 11. Балансировка АВЛ-дерева LR – вращение (продолжение)Шаг 2:
- 12. Балансировка АВЛ-дерева RL - вращениеДанная ситуация возникает
- 13. Балансировка АВЛ-дерева RL – вращение (продолжение)Шаг 2:
- 14. Построение АВЛ-дереваРассмотрим процесс построения АВЛ-дерева, состоящего из
- 15. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 16. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 17. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 18. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 19. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 20. Построение АВЛ-дереваРазбалансировка в узле 1 Выполняем RL-поворот.
- 21. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 22. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 23. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 24. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 25. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 26. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 27. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 28. Построение АВЛ-дереваРазбалансировка в узле 1 Выполняем RR-поворот.
- 29. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 30. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 31. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 32. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 33. Построение АВЛ-дереваРазбалансировка в узле 7 Выполняем LR-поворот.
- 34. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 35. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 36. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 37. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 38. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 138>3
- 39. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 138>7
- 40. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 138
- 41. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 138
- 42. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 43. Построение АВЛ-дереваРазбалансировка в узле 15 Выполняем LL-поворот.
- 44. Построение АВЛ-дерева5>31, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 45. Построение АВЛ-дерева5
- 46. Построение АВЛ-дерева5>41, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 47. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 48. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 136>3
- 49. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 136
- 50. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 136>4
- 51. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 136>5
- 52. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 53. Построение АВЛ-дереваРазбалансировка в узле 4 Выполняем RR-поворот.
- 54. Построение АВЛ-дерева11>31, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 55. Построение АВЛ-дерева11>71, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 56. Построение АВЛ-дерева11>91, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 57. Построение АВЛ-дерева11
- 58. Построение АВЛ-дерева11
- 59. Построение АВЛ-дереваРазбалансировка в узле 3 Выполняем RR-поворот.
- 60. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 1313>7
- 61. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 1313>9
- 62. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 1313
- 63. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 1313>11
- 64. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
- 65. Построение АВЛ-дереваРазбалансировка в узле 15 Выполняем LR-поворот.
- 66. Построение АВЛ-дерева1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13. Построение завершено.
- 67. Алгоритм удаления узла из АВЛ-дерева схож с
- 68. Удаление узла из АВЛ-дерева (случай 1)Если узел
- 69. Удаление узла из АВЛ-дерева (случай 2)Если удаляемый
- 70. Удаление узла из АВЛ-дерева (случай 2)Удаляем узел 2 и переносим на его место узел 1.
- 71. Удаление узла из АВЛ-дерева (случай 3)Если удаляемый
- 72. Удаление узла из АВЛ-дерева (случай 3)Самый правый
- 73. Удаление узла из АВЛ-дерева (случай 3)Необходимо устранить разбалансировку в узле 8, выполнив RR-поворот.
- 74. Удаление узла из АВЛ-дерева (случай 4)Те же
- 75. Удаление узла из АВЛ-дерева (случай 4)1) Переместим
- 76. Удаление узла из АВЛ-дерева (случай 4)Удаление завершено.81
- 77. Рассмотрели определение и программную структуру АВЛ-дерева;Научились выполнять
- 78. Спасибо за внимание!
- 79. Скачать презентанцию
Дать определение АВЛ-дерева;Рассмотреть способы балансировки АВЛ-дерева;Научиться выполнять построение АВЛ-дерева;Научиться выполнять операции поиска, добавления, удаления узла из АВЛ-дерева.Задачи
Слайды и текст этой презентации
Слайд 2Дать определение АВЛ-дерева;
Рассмотреть способы балансировки АВЛ-дерева;
Научиться выполнять построение АВЛ-дерева;
Научиться выполнять
операции поиска, добавления, удаления узла из АВЛ-дерева.
Слайд 3АВЛ–дерево - это структура данных, изобретенная советскими математиками:
Г.М. Андельсон-Вельским и
Е.М. Ландисом. АВЛ – дерево является частным случаем двоичного дерева
поиска, для которого определено следующее условие: каждый узел дерева имеет коэффициент сбалансированности, который должен удовлетворять условию | h(Rtree) - h(Ltree) | ≤ 1, где h(Ltree) и h(Rtree) – высоты левого и правого поддеревьев соответственно. Т.е. коэффициент сбалансированности для каждого узла дерева должен принимать одно из трех значений {-1,0,1}. Если, хотя бы для одного узла это условие не выполняется, то дерево не является сбалансированным по АВЛ и необходима его балансировка. Кроме того, поскольку АВЛ-дерево является бинарным деревом поиска, то для каждого его узла должно выполняться условие: значения в левом поддереве должны быть меньше значения этого узла, а значения в правом поддереве должны быть больше значения данного узла.Сложность операций поиска, добавления, удаления узла в АВЛ-дереве составляет порядка О(log N), где N – количество элементов дерева.
Определение
Слайд 5struct Tree
{
int Value;
Tree *Right, *Left;
};
Структура АВЛ-дерева
В рассматриваемых примерах программная структура
АВЛ-дерева будет иметь следующий вид:
Слайд 6Балансировка АВЛ-дерева
LL - вращение
Существует 4 вида ситуаций в которых необходима
балансировка АВЛ-дерева, как правило, такие ситуации возникают по причине добавления
или удаления узла из АВЛ-дерева. Рассмотрим первую из них.Данная ситуация возникает когда дерево имеет «перевес» в левом поддереве левого потомка узла дерева, в этом случае необходимо провести балансировку малым левым вращением или LL-вращением (Left-Left Rotation).
Коэффициенты сбалансированности
Слайд 7 Tree* LL_Rotation(Tree* T2 ){
Tree* T1;
T1 = T2->Left;
T2->Left = T1->Right;
T1->Right = T2;
return T1; }
Балансировка
АВЛ-дерева
LL - вращениеСуществует 4 вида ситуаций в которых необходима балансировка АВЛ-дерева, как правило, такие ситуации возникают по причине добавления или удаления узла из АВЛ-дерева. Рассмотрим первую из них.
Данная ситуация возникает когда дерево имеет «перевес» в левом поддереве левого потомка узла дерева, в этом случае необходимо провести балансировку малым левым вращением или LL-вращением (Left-Left Rotation).
Коэффициенты сбалансированности
Слайд 8Балансировка АВЛ-дерева
RR - вращение
Данная ситуация возникает когда дерево имеет «перевес»
в правом поддереве правого потомка узла дерева, в этом случае
необходимо провести балансировку малым правым вращением или RR-вращением (Right-Right Rotation).0
1
2
Слайд 9Балансировка АВЛ-дерева
RR - вращение
Данная ситуация возникает когда дерево имеет «перевес»
в правом поддереве правого потомка узла дерева, в этом случае
необходимо провести балансировку малым правым вращением или RR-вращением (Right-Right Rotation).0
1
2
Tree* RR_Rotation (Tree* T1 ){
Tree* T2;
T2 = T1->Right;
T1->Right = T2->Left;
T2->Left = T1;
return T2; }
Слайд 10Балансировка АВЛ-дерева
LR - вращение
Данная ситуация возникает когда дерево имеет «перевес»
в правом поддереве левого потомка узла дерева, в этом случае
необходимо провести балансировку комбинацией малого правого (RR) и малого левого (LL) вращений, такой способ балансировки называется лево-правым вращением (Left-Right-Rotation)7
1
5
0
1
-2
7
5
1
0
-2
-1
Шаг 1: RR - вращение
Tree* LR_Rotation(Tree* T3)
{
T3->Left = RR_Rotation(T3->Left );
return LL_Rotation(T3);
}
Слайд 11Балансировка АВЛ-дерева
LR – вращение (продолжение)
Шаг 2: LL - вращение
Tree* LR_Rotation(Tree*
T3)
{
T3->Left = RR_Rotation(T3->Left );
return LL_Rotation(T3);
}
Слайд 12Балансировка АВЛ-дерева
RL - вращение
Данная ситуация возникает когда дерево имеет «перевес»
в левом поддереве правого потомка узла дерева, в этом случае
необходимо провести балансировку комбинацией малого левого (LL) и малого правого (RR) вращений, такой способ балансировки называется право-левым вращением (Right-Left-Rotation)1
7
5
0
-1
2
Шаг 1: LL - вращение
Tree* RL_Rotation(Tree* T1) {
T1->Right = LL_Rotation(T1->Right );
return RR_Rotation(T1);
}
Слайд 13Балансировка АВЛ-дерева
RL – вращение (продолжение)
Шаг 2: RR - вращение
Tree* RL_Rotation(Tree*
T1) {
T1->Right = LL_Rotation(T1->Right );
return RR_Rotation(T1);
}
Слайд 14Построение АВЛ-дерева
Рассмотрим процесс построения АВЛ-дерева, состоящего из последовательности чисел:
1, 15,
7, 2, 3, 4, 9, 8, 5, 6, 11, 13
Слайд 67Алгоритм удаления узла из АВЛ-дерева схож с алгоритмом удаления узла
из обычного бинарного дерева поиска, с единственным отличием: в АВЛ-дереве,
после удаления узла может потребоваться дополнительная балансировка.Существует 4 основных ситуации, возникающих при удаления узла из АВЛ – дерева, рассмотрим первую из них:
Случай 1: Удаление листа
Удаление узла из АВЛ-дерева
Слайд 68Удаление узла из АВЛ-дерева
(случай 1)
Если узел не имеет потомков, т.е.
является листом, то он просто удаляется, без каких-либо дополнительных операций.
Удалим узел 6.
Слайд 69Удаление узла из АВЛ-дерева
(случай 2)
Если удаляемый узел имеет только одно
поддерево, то потомственный ему узел, включая все поддерево просто переносится
(перевешивается) на место удаляемого узла. Удалим узел 2.
Слайд 71Удаление узла из АВЛ-дерева
(случай 3)
Если удаляемый узел имеет два поддерева,
то в левом поддереве, удаляемого узла, ищется узел с наибольшим
значением (самый правый узел). Если найденный узел является листом, то он просто переносится на место удаляемого узла. Удалим узел 9..
Слайд 72Удаление узла из АВЛ-дерева
(случай 3)
Самый правый узел в левом поддереве
узла 9 - это 8. Узел 8 является листом, поэтому
просто переносим узел 8 на место удаляемого узла 9.
Слайд 73Удаление узла из АВЛ-дерева
(случай 3)
Необходимо устранить разбалансировку в узле 8,
выполнив RR-поворот.
Слайд 74Удаление узла из АВЛ-дерева
(случай 4)
Те же условия, что и в
случае 3, только узел с наибольшим значением (самый правый узел)
имеет левое поддерево (правое поддерево он не может иметь, т.к. он является самым правым). Рассмотрим этот случай на примере удаления узла 7.8
1
Слайд 75Удаление узла из АВЛ-дерева
(случай 4)
1) Переместим найденный узел 5 на
место удаляемого узла 7, как мы это делали в случае
3. 2) Переместим (перевесим) узел 4 (левое поддерево узла 5) на место узла 5, как мы это делали в случае 2.8
1
1)
2)
Слайд 77Рассмотрели определение и программную структуру АВЛ-дерева;
Научились выполнять построение АВЛ-дерева;
Научились осуществлять
поиск элемента в АВЛ-дереве на примерах операций добавления, удаления элемента;
Научились
выполнять операции добавления, удаления узла из АВЛ-дерева.Выводы
