Копание в деревьях AVL

Дерево AVL — это тип самобалансирующегося бинарного дерева. Он назван в честь его авторов: Адельсон-Вельски и Ландис. В дереве AVL для каждого узла разница в высоте между левым и правым поддеревьями не может быть больше единицы.

Чтобы гарантировать это, он проверяет после каждого добавления, что дерево все еще сбалансировано. Если нет, выполняются дополнительные операции. Эти операции называются вращениями.

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

Левый поворот на узле N описывается так:

  • Возьмем правого потомка N, назовем его Y
  • Возьмите левого потомка Y, назовите его Z

  • Замените левого потомка Y на N

  • Замените правого потомка N на Z

В виде псевдокода это будет выглядеть так:

function rotate_left(node: TreeNode)
  let y = node.right
  let z = y.left
  y.left = node
  node.right = z
  node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
  y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
  return y

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

Правое вращение следует тому же принципу:

  • Возьмем левого потомка N, назовем его Y
  • Возьмите правого ребенка Y, назовите его Z
  • Замените правого потомка Y на N
  • Замените левого потомка N на Z
function rotate_right(node: TreeNode)
  let y = node.left
  let z = y.right
  y.right = node
  node.left = z
  node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
  y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
  return y

Знание того, какие операции выполнять

После каждой вставки мы проверяем, сбалансировано ли дерево. Если это не так, мы находим первый узел над вставленным узлом, который не сбалансирован.

Назовем вставленный узел N, а несбалансированный узел U.

Сначала мы проверяем коэффициент баланса U. Для этого мы вычисляем разницу в высоте между его левым и правым поддеревьями.

Назовем эту разницу высот D.

Тогда, если D > 1, это означает, что левое поддерево длиннее правого, дисбаланс в левой части. Интуитивно мы можем подумать, что нам нужно сделать поворот вправо. Но это не так просто. Мы можем быть в двух случаях: случай «влево-влево», когда нам нужно будет выполнить только правое вращение, или случай «влево-вправо», когда мы сначала должны выполнить левое вращение, а затем правое вращение.

То же самое и с D ‹ -1.

Работа с левыми делами

В левых случаях мы знаем, что дисбаланс находится на левой стороне дерева.

Назовем C левым потомком U.

Левый левый корпус

Когда значение C больше, чем N, это означает, что N будет в левом поддереве C. Мы называем это «лево-левым случаем». Это означает, что, начиная с несбалансированного узла U, вы должны взять левого потомка, а затем снова левого потомка, чтобы оказаться на правильном пути к N.

В случае Left Left дисбаланс полностью расположен на левой стороне дерева. Таким образом, это можно исправить, выполнив правый поворот на несбалансированном узле U.

Левый правый корпус

Когда значение C меньше, чем значение N, это означает, что N будет находиться в правом поддереве C. Мы называем это «лево-правым случаем». Это означает, что, начиная с несбалансированного узла U, вы должны взять левого потомка, а затем правого потомка, чтобы оказаться на правильном пути к N.

В случае Left Right дисбаланс находится в левой части дерева, но в правом поддереве C. Прежде чем исправить дисбаланс, нам нужно повернуть дерево на C влево, чтобы дисбаланс вернулся на Левый левый случай.

После этого мы можем выполнить правый поворот на U и снова сбалансировать наше дерево.

Работа с правильными делами

В правильных случаях мы знаем, что дисбаланс находится на правой стороне дерева.

Назовем C правым потомком U.

Правильный случай

Когда значение C ниже, чем значение N, N будет находиться в правом поддереве C. Мы называем это «правильным правильным случаем». Это означает, что, начиная с несбалансированного узла U, вы должны взять правого потомка, а затем снова правильного потомка, чтобы оказаться на правильном пути к N.

В случае Right Right дисбаланс полностью расположен на правой стороне дерева. Таким образом, это можно исправить, выполнив левое вращение на несбалансированном узле U.

Правый левый случай

Точно так же в случае правого левого C больше, чем N, поэтому несбалансированное сначала справа, а затем слева.

Это означает, что нам сначала нужно сделать правое вращение на C, а затем левое вращение на U, чтобы исправить дисбаланс.

В коде

Чтобы сделать это в коде, это будет выглядеть так:

function get_height(node:TreeNode)
  if node == null
    return 0
  endif
  return node.height


function get_balance(node: TreeNode, value: int)
  if node == null
    return 0
  endif
  return get_height(node.left) - get_height(node.right)

function rebalance(node: TreeNode)
  let balance = get_balance(node)
  if balance > 1                 // we are in the left cases
    if value < node.left.value   // we are in the left left case
      return rotate_right(node)
    else                         // we are in the left right case
      node.left = rotate_left(node.left)
      return rotate_right(node)
    endif
  endif

  if balance <-1                 // we are in the right cases
    if value > node.right.value  // we are in the right right case
      return rotate_left(node)
    else                         // we are in the right left case
      node.right = rotate_right(node.right)
      return rotate_left(node)
    endif
  endif
  return node                    // any other cases

function insert(node: TreeNode, value: int)
  if node == null
    return new TreeNode(value)
  else if value < node.value
    node.left = insert(node.left, value)
  else
    node.right = insert(node.right, value)
  endif

  node.height = 1 + max(get_height(node.left), get_height(node.right))
  return rebalance(node, value)

Вот и все для дерева AVL, спасибо за чтение, увидимся в следующем!

Читайте также из этой же серии:



Двоичное дерево поиска
Теперь, когда мы знаем о двоичном поиске, давайте углубимся в дерево двоичного поиска!quentin-musy.medium.com





Сбалансированные бинарные деревья
Давайте погрузимся в прекрасный мир сбалансированных бинарных деревьев!quentin-musy.medium.com