Красиков И.А. ТУСУР 2015
Дать определение АВЛ-дерева; Рассмотреть способы балансировки АВЛ-дерева; Научиться выполнять построение АВЛ-дерева; Научиться выполнять операции поиска, добавления, удаления узла из АВЛ-дерева. Задачи
АВЛ–дерево - это структура данных, изобретенная советскими математиками: Г.М. Андельсон -Вельским и Е.М. Ландисом. АВЛ – дерево является частным случаем двоичного дерева поиска, для которого определено следующее условие: каждый узел дерева имеет коэффициент сбалансированности, который должен удовлетворять условию | h ( Rtree ) - h ( Ltree ) | ≤ 1, где h ( Ltree ) и h ( Rtree ) – высоты левого и правого поддеревьев соответственно. Т.е. коэффициент сбалансированности для каждого узла дерева должен принимать одно из трех значений {-1,0,1}. Если, хотя бы для одного узла это условие не выполняется, то дерево не является сбалансированным по АВЛ и необходима его балансировка. Кроме того, поскольку АВЛ-дерево является бинарным деревом поиска, то для каждого его узла должно выполняться условие: значения в левом поддереве должны быть меньше значения этого узла, а значения в правом поддереве должны быть больше значения данного узла. Сложность операций поиска, добавления, удаления узла в АВЛ-дереве составляет порядка О( log N ), где N – количество элементов дерева. Определение
3 7 0 9 2 1 5 8 11 13 15 4 6 0 0 0 0 -1 0 0 0 1 0
struct Tree { int Value; Tree *Right, *Left ; }; Структура АВЛ-дерева В рассматриваемых примерах программная структура АВЛ-дерева будет иметь следующий вид:
Существует 4 вида ситуаций в которых необходима балансировка АВЛ-дерева, как правило, такие ситуации возникают по причине добавления или удаления узла из АВЛ-дерева. Рассмотрим первую из них. Данная ситуация возникает когда дерево имеет «перевес» в левом поддереве левого потомка узла дерева, в этом случае необходимо провести балансировку малым левым вращением или LL- вращением ( Left-Left Rotation ). 7 5 1 0 -1 -2 7 5 1 0 0 0 Коэффициенты сбалансированности LL - вращение
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 ). 7 5 1 0 -1 -2 7 5 1 0 0 0 Коэффициенты сбалансированности
Данная ситуация возникает когда дерево имеет «перевес» в правом поддереве правого потомка узла дерева, в этом случае необходимо провести балансировку малым правым вращением или RR- вращением ( Right-Right Rotation ). 1 5 7 0 1 2 7 5 1 0 0 0 RR - вращение
Данная ситуация возникает когда дерево имеет «перевес» в правом поддереве правого потомка узла дерева, в этом случае необходимо провести балансировку малым правым вращением или RR- вращением ( Right-Right Rotation ). 1 5 7 0 1 2 7 5 1 0 0 0 Tree* RR_Rotation (Tree* T1 ){ Tree* T2; T2 = T1->Right; T1->Right = T2->Left; T2->Left = T1; return T2; }
Данная ситуация возникает когда дерево имеет «перевес» в правом поддереве левого потомка узла дерева, в этом случае необходимо провести балансировку комбинацией малого правого ( 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); }
7 5 1 0 -2 -1 Шаг 2 : LL - вращение Tree* LR_Rotation (Tree* T3) { T3->Left = RR_Rotation(T3->Left ); return LL_Rotation(T3); } 7 5 1 0 0 0
Данная ситуация возникает когда дерево имеет «перевес» в левом поддереве правого потомка узла дерева, в этом случае необходимо провести балансировку комбинацией малого левого ( LL ) и малого правого ( RR ) вращений, такой способ балансировки называется право-левым вращением ( Right-Left-Rotation) 1 7 5 0 - 1 2 1 5 7 0 2 1 Шаг 1: LL - вращение Tree* RL_Rotation (Tree* T1) { T1->Right = LL_Rotation(T1->Right ); return RR_Rotation(T1); }
Шаг 2 : RR - вращение Tree* RL_Rotation (Tree* T1) { T1->Right = LL_Rotation(T1->Right ); return RR_Rotation(T1); } 7 5 1 0 0 0 1 5 7 0 2 1
1 0 Рассмотрим процесс построения АВЛ-дерева, состоящего из последовательности чисел: 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый
1 0 Новый 15 15 >1 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 Новый 15 15 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 1 Новый 7 15 0 7 >1 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 1 Новый 7 15 0 7<15 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 1 Новый 7 15 0 7 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 2 15 -1 7 0 Разбалансировка в узле 1 Выполняем RL- поворот.
1 0 15 0 7 0 Новый 2 2 < 7 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 Новый 2 2 > 1 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 Новый 2 2 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 1 15 0 7 -1 2 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 3 3<7
1 1 15 0 7 -1 2 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 3 3 >1
1 1 15 0 7 -1 2 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 3 3>2
1 1 15 0 7 -1 2 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 3 3
1 2 15 0 7 -2 2 1 3 0 Разбалансировка в узле 1 Выполняем RR- поворот.
1 0 15 0 7 -1 2 0 3 0 Новый 4 4<7 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 -1 2 0 3 0 Новый 4 4>2 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 -1 2 0 3 0 Новый 4 4>3 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 -1 2 0 3 0 Новый 4 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 4
1 0 15 0 7 -2 2 1 3 1 4 0 Разбалансировка в узле 7 Выполняем L R- поворот.
1 0 15 0 7 0 2 -1 3 0 4 0 Новый 9 9>3 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 2 -1 3 0 4 0 Новый 9 9>7 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 2 -1 3 0 4 0 Новый 9 9<15 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 2 -1 3 0 4 0 Новый 9 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 9
1 0 15 -1 7 1 2 -1 3 1 4 0 Новый 8 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 9 0 8>3
1 0 15 -1 7 1 2 -1 3 1 4 0 Новый 8 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 9 0 8>7
1 0 15 -1 7 1 2 -1 3 1 4 0 Новый 8 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 9 0 8<15
1 0 15 -1 7 1 2 -1 3 1 4 0 Новый 8 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 9 0 8<9
1 0 15 -1 7 1 2 -1 3 1 4 0 Новый 8 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 9 0 8
1 0 15 -2 7 2 2 -1 3 2 4 0 9 -1 8 0 Разбалансировка в узле 15 Выполняем LL- поворот.
1 0 15 0 7 1 2 -1 3 1 4 0 9 0 8 0 Новый 5 5>3 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 1 2 -1 3 1 4 0 9 0 8 0 Новый 5 5<7 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 1 2 -1 3 1 4 0 9 0 8 0 Новый 5 5>4 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 1 2 -1 3 1 4 0 9 0 8 0 Новый 5 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 5
1 0 15 0 7 0 2 -1 3 1 4 1 9 0 8 0 Новый 6 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 5 0 6>3
1 0 15 0 7 0 2 -1 3 1 4 1 9 0 8 0 Новый 6 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 5 0 6<7
1 0 15 0 7 0 2 -1 3 1 4 1 9 0 8 0 Новый 6 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 5 0 6>4
1 0 15 0 7 0 2 -1 3 1 4 1 9 0 8 0 Новый 6 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 5 0 6>5
1 0 15 0 7 0 2 -1 3 1 4 1 9 0 8 0 Новый 6 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 5 0 6
1 0 15 0 7 -1 2 -1 3 2 4 2 9 0 8 0 5 1 6 0 Разбалансировка в узле 4 Выполняем RR- поворот.
1 0 15 0 7 0 2 -1 3 1 4 0 9 0 8 0 5 0 6 0 Новый 11 11>3 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 2 -1 3 1 4 0 9 0 8 0 5 0 6 0 Новый 11 11>7 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 2 -1 3 1 4 0 9 0 8 0 5 0 6 0 Новый 11 11>9 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 2 -1 3 1 4 0 9 0 8 0 5 0 6 0 Новый 11 11<15 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13
1 0 15 0 7 0 2 -1 3 1 4 0 9 0 8 0 5 0 6 0 Новый 11 11<15 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 11
1 0 15 -1 7 1 2 -1 3 2 4 0 9 1 8 0 5 0 6 0 11 0 Разбалансировка в узле 3 Выполняем RR- поворот.
1 0 15 -1 7 0 2 -1 3 0 4 0 9 1 8 0 5 0 6 0 11 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 13 13>7
1 0 15 -1 7 0 2 -1 3 0 4 0 9 1 8 0 5 0 6 0 11 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 13 13>9
1 0 15 -1 7 0 2 -1 3 0 4 0 9 1 8 0 5 0 6 0 11 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 13 13<15
1 0 15 -1 7 0 2 -1 3 0 4 0 9 1 8 0 5 0 6 0 11 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 13 13>11
1 0 15 -1 7 0 2 -1 3 0 4 0 9 1 8 0 5 0 6 0 11 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13 Новый 13 13
1 0 15 -2 7 1 2 -1 3 0 4 0 9 2 8 0 5 0 6 0 11 1 13 0 Разбалансировка в узле 15 Выполняем L R- поворот.
1 0 13 0 7 0 2 -1 3 0 4 0 9 1 8 0 5 0 6 0 11 0 15 0 1, 15, 7, 2, 3, 4, 9, 8, 5, 6, 11, 13. Построение завершено.
Алгоритм удаления узла из АВЛ-дерева схож с алгоритмом удаления узла из обычного бинарного дерева поиска, с единственным отличием: в АВЛ-дереве, после удаления узла может потребоваться дополнительная балансировка. Существует 4 основных ситуации, возникающих при удаления узла из АВЛ – дерева, рассмотрим первую из них: Случай 1: Удаление листа 1 0 13 0 7 0 2 -1 3 0 4 0 9 1 8 0 5 0 6 0 11 0 15 0 Удаление узла из АВЛ-дерева
Если узел не имеет потомков, т.е. является листом, то он просто удаляется, без каких-либо дополнительных операций. Удалим узел 6. 1 0 13 0 7 0 2 -1 3 0 4 0 9 1 8 0 5 0 6 0 11 0 15 0
Если удаляемый узел имеет только одно поддерево, то потомственный ему узел, включая все поддерево просто переносится (перевешивается) на место удаляемого узла. Удалим узел 2. 1 0 13 0 7 0 2 -1 3 0 4 0 9 1 8 0 5 -1 11 0 15 0
Удаляем узел 2 и переносим на его место узел 1. 1 0 13 0 7 0 2 -1 3 0 4 0 9 1 8 0 5 -1 11 0 15 0
Если удаляемый узел имеет два поддерева, то в левом поддереве, удаляемого узла, ищется узел с наибольшим значением (самый правый узел). Если найденный узел является листом, то он просто переносится на место удаляемого узла. Удалим узел 9. . 13 0 7 0 1 0 3 1 4 0 9 1 8 0 5 -1 11 0 15 0
С амый правый узел в левом поддереве узла 9 - это 8. Узел 8 является листом, поэтому просто переносим узел 8 на место удаляемого узла 9. 13 0 7 0 1 0 3 1 4 0 9 1 8 0 5 -1 11 0 15 0
Необходимо устранить разбалансировку в узле 8, выполнив RR- поворот. 13 0 7 0 1 0 3 1 4 0 8 2 5 -1 11 0 15 0
Те же условия, что и в случае 3, только узел с наибольшим значением (самый правый узел ) имеет левое поддерево (правое поддерево он не может иметь, т.к. он является самым правым). Рассмотрим этот случай на примере удаления узла 7. 15 0 7 0 1 0 3 1 4 0 13 -1 5 -1 11 0 8 1
1) Переместим найденный узел 5 на место удаляемого узла 7, как мы это делали в случае 3. 2) Переместим (перевесим) узел 4 (левое поддерево узла 5) на место узла 5, как мы это делали в случае 2. 15 0 7 0 1 0 3 1 4 0 13 -1 5 -1 11 0 8 1 1) 2 )
Удаление завершено. 15 0 5 1 1 0 3 0 13 -1 4 0 11 0 8 1
Рассмотрели определение и программную структуру АВЛ-дерева; Научились выполнять построение АВЛ-дерева; Научились осуществлять поиск элемента в АВЛ-дереве на примерах операций добавления, удаления элемента; Научились выполнять операции добавления, удаления узла из АВЛ-дерева. Выводы
Спасибо за внимание!
