Структура данных и алгоритмы - деревья AVL
Что, если входные данные в двоичное дерево поиска поступают отсортированным (по возрастанию или по убыванию)? Тогда это будет выглядеть так -
Замечено, что производительность BST в худшем случае наиболее близка к алгоритмам линейного поиска, то есть (n). В данных в реальном времени мы не можем предсказать структуру данных и их частоту. Таким образом, возникает необходимость сбалансировать существующую BST.
Названный в честь своего изобретателя Adelson, Velski & Landis, AVL treesбинарное дерево поиска с балансировкой высоты. Дерево AVL проверяет высоту левого и правого поддеревьев и гарантирует, что разница не превышает 1. Эта разница называетсяBalance Factor.
Здесь мы видим, что первое дерево сбалансировано, а следующие два дерева не сбалансированы -
Во втором дереве левое поддерево C имеет высоту 2, а правое поддерево имеет высоту 0, поэтому разница равна 2. В третьем дереве правое поддерево Aимеет высоту 2, а слева отсутствует, поэтому он равен 0, а разница снова равна 2. Дерево AVL позволяет разнице (коэффициенту баланса) быть только 1.
BalanceFactor = height(left-sutree) − height(right-sutree)
Если разница в высоте левого и правого поддеревьев больше 1, дерево балансируется с помощью некоторых методов вращения.
AVL вращения
Чтобы сбалансировать себя, дерево AVL может выполнять следующие четыре вида вращения:
- Левое вращение
- Правое вращение
- Вращение влево-вправо
- Вращение вправо-влево
Первые два поворота - это одиночные вращения, а следующие два вращения - двойные вращения. Чтобы иметь несбалансированное дерево, нам нужно, по крайней мере, дерево высотой 2. Давайте разберемся с этим простым деревом по очереди.
Левое вращение
Если дерево становится несбалансированным, когда узел вставляется в правое поддерево правого поддерева, мы выполняем одно вращение влево -
В нашем примере узел Aстал несбалансированным, поскольку узел вставлен в правое поддерево правого поддерева A. Выполняем левый поворот, делаяA левое поддерево B.
Правое вращение
Дерево AVL может стать несбалансированным, если узел вставлен в левое поддерево левого поддерева. Затем дереву нужно повернуть вправо.
Как показано, несбалансированный узел становится правым потомком своего левого потомка, выполняя правое вращение.
Вращение влево-вправо
Двойные вращения - это немного сложная версия уже объясненных версий вращений. Чтобы лучше их понять, мы должны записывать каждое действие, выполняемое во время вращения. Давайте сначала проверим, как выполнять вращение влево-вправо. Вращение влево-вправо - это комбинация вращения влево с последующим вращением вправо.
состояние | Действие |
---|---|
|
Узел был вставлен в правое поддерево левого поддерева. Это делаетCнесбалансированный узел. Эти сценарии заставляют дерево AVL выполнять вращение влево-вправо. |
|
Сначала мы выполняем левый поворот на левом поддереве C. Это делаетA, левое поддерево B. |
|
Узел C все еще несбалансирован, однако теперь это из-за левого поддерева левого поддерева. |
|
Теперь мы повернем дерево вправо, сделав B новый корневой узел этого поддерева. C теперь становится правым поддеревом своего левого поддерева. |
|
Теперь дерево сбалансировано. |
Вращение вправо-влево
Второй тип двойного вращения - вращение вправо-влево. Это комбинация вращения вправо с последующим вращением влево.
состояние | Действие |
---|---|
|
Узел был вставлен в левое поддерево правого поддерева. Это делаетA, несбалансированный узел с коэффициентом балансировки 2. |
|
Сначала выполняем правый поворот по C узел, делая C правое поддерево своего левого поддерева B. Сейчас же,B становится правым поддеревом A. |
|
Узел A все еще несбалансирован из-за правого поддерева правого поддерева и требует поворота влево. |
|
Левый поворот выполняется путем B новый корневой узел поддерева. A становится левым поддеревом своего правого поддерева B. |
|
Теперь дерево сбалансировано. |