Структура данных и алгоритмы - деревья AVL

Что, если вход в двоичное дерево поиска поступает отсортированным (по возрастанию или по убыванию) образом? Тогда это будет выглядеть так -

Несбалансированный BST

Наблюдается, что производительность BST в худшем случае наиболее близка к алгоритмам линейного поиска, то есть Ο (n). В данных в реальном времени мы не можем предсказать структуру данных и их частоту. Таким образом, возникает необходимость сбалансировать существующий BST.

Названные в честь их изобретателя Adelson , Velski & Landis , деревья AVL представляют собой бинарное дерево поиска с балансировкой высоты. Дерево AVL проверяет высоту левого и правого поддеревьев и гарантирует, что разница не превышает 1. Эта разница называется коэффициентом баланса .

Здесь мы видим, что первое дерево сбалансировано, а следующие два дерева не сбалансированы -

Несбалансированные деревья AVL

Во втором дереве левое поддерево C имеет высоту 2, а правое поддерево имеет высоту 0, поэтому разница составляет 2. В третьем дереве правое поддерево A имеет высоту 2, а левое отсутствует, поэтому оно равно 0 и снова разница 2. Дерево AVL допускает разницу (коэффициент баланса) только в 1.

 BalanceFactor = height(left-sutree) − height(right-sutree)

Если разница в высоте левого и правого поддеревьев превышает 1, дерево уравновешивается с использованием некоторых методов поворота.

AVL Rotations

Чтобы сбалансировать себя, дерево AVL может выполнять следующие четыре вида вращений:

  • Левый поворот
  • Правое вращение
  • Вращение влево-вправо
  • Вращение вправо-влево

Первые два вращения - это одиночные вращения, а следующие два вращения - двойные вращения. Чтобы иметь несбалансированное дерево, нам нужно, по крайней мере, дерево высоты 2. С этим простым деревом, давайте разберемся с ними один за другим.

Левое вращение

Если дерево становится неуравновешенным, когда узел вставляется в правое поддерево правого поддерева, мы выполняем одиночное вращение влево -

Левое вращение

В нашем примере узел A стал несбалансированным, поскольку узел вставлен в правое поддерево правого поддерева A. Мы выполняем вращение влево, делая A левым поддеревом B.

Правое вращение

Дерево AVL может стать несбалансированным, если узел вставлен в левое поддерево левого поддерева. Затем дерево нуждается в правильном вращении.

Правое вращение

Как изображено, несбалансированный узел становится правым потомком своего левого потомка, выполняя правое вращение.

Вращение вправо-влево

Двойные повороты - немного сложная версия уже объясненных версий поворотов. Чтобы понять их лучше, мы должны принять к сведению каждое действие, выполненное во время вращения. Давайте сначала проверим, как выполнить вращение влево-вправо. Поворот влево-вправо - это комбинация вращения влево, за которым следует поворот вправо.

состояние действие
Правое вращение Узел был вставлен в правое поддерево левого поддерева. Это делает C несбалансированным узлом. Эти сценарии заставляют дерево AVL выполнять вращение влево-вправо.
Левое вращение Сначала мы выполняем левый поворот на левом поддереве C. Это делает A , левое поддерево B.
Левое вращение Узел C все еще не сбалансирован, однако теперь это происходит из-за левого поддерева левого поддерева.
Правое вращение Теперь мы повернем дерево вправо, сделав B новым корневым узлом этого поддерева. C теперь становится правым поддеревом своего собственного левого поддерева.
Сбалансированное дерево Avl Дерево теперь сбалансировано.

Вращение вправо-влево

Второй тип двойного вращения - вращение вправо-влево. Это комбинация правого вращения с последующим левым вращением.

состояние действие
Левое поддерево Правое поддерево Узел был вставлен в левое поддерево правого поддерева. Это делает A несбалансированным узлом с коэффициентом баланса 2.
Поддерево правого поворота Сначала мы выполняем правое вращение вдоль узла C , делая C правым поддеревом своего собственного левого поддерева B. Теперь B становится правильным поддеревом A.
Правильное несбалансированное дерево Узел A все еще не сбалансирован из-за правого поддерева своего правого поддерева и требует левого поворота.
Левое вращение Поворот влево выполняется путем создания B новым корневым узлом поддерева. A становится левым поддеревом своего правого поддерева B.
Сбалансированное дерево AVL Дерево теперь сбалансировано.