Как вы знаете, где выполнять вращения в дереве AVL?

Итак, я сам изучаю деревья AVL, и я понимаю основную идею этого, но я просто хочу убедиться, что моя интуиция его реализации действительно:

Я рассмотрю его с левым вращением -

Итак, следующая ситуация проста:

Когда мы добавляем 3, дерево ребалансирует себя:

Но есть ли поворот, основанный на добавлении 3 или дисбалансе поддерева, внедренного в 7? Это даже основано на дисбалансе дерева, внедренного в 8?

В следующем примере, где, по-моему, все становится немного волосатым:

Итак, в этом случае поддерево в 7 отлично, когда добавляется 3, так что поддерево не нужно вращать. Однако дерево в 9 несбалансировано с добавлением 3, поэтому мы устанавливаем поворот на 9. Получаем:

Итак, при написании моего кода, который я скоро буду, будет ли следующий код, начиная с небольших поддеревьев, работающих до больших поддеревьев, делает трюк?

псевдокод:

function balanceTree(Node n){

  if (n is not null){

    balanceTree(n.rightchild);
    balanceTree(n.leftchild);
  }

  if (abs(balanceFactor(n))>1){

    rotateAsNeeded(n);// rotate based on balance factor

  }

}

Спасибо заранее!

Ответ 1

Псевдокод, который вы опубликовали, правильно сбалансирует дерево. Тем не менее, это слишком малоэффективно, чтобы быть практичным - обратите внимание, что вы рекурсивно изучаете все дерево, пытающееся выполнить операции по перебалансировке, что сделает все вставки и удаления временем O (n), уничтожив все выгоды от повышения эффективности сбалансированное дерево.

Идея, лежащая в основе деревьев AVL, заключается в том, что глобальное перебалансирование дерева может быть выполнено путем итеративного применения локальных вращений. Другими словами, когда вы делаете вставку или удаление и вам нужно делать вращения деревьев, эти вращения не будут отображаться в случайных точках в дереве. Они всегда будут отображаться на пути доступа, который вы использовали при вставке или удалении node.

Например, вам было интересно вставить значение 3 в это дерево:

Давайте начнем с написания разницы в коэффициентах баланса, связанных с каждым node (важно, чтобы узлы дерева AVL сохраняли эту информацию, поскольку это позволяет эффективно делать вставки и удаления):

           9(+1)
         /       \
       7 (0)    10 (0)
      / \
  6(0)   8(0)

Итак, теперь посмотрим, что будет, когда мы вставим 3. Это помещает здесь 3:

           9(+1?)
          /       \
        7 (0?)    10 (0)
       /   \
   6(0?)   8(0)
   /
 3(0)

Обратите внимание, что я пометил все узлы пути доступа с помощью?, так как мы больше не уверены, каковы их коэффициенты баланса. Поскольку мы вставили новый дочерний элемент для 6, это изменит коэффициент баланса для 6 node на +1:

           9(+1?)
          /       \
        7 (0?)    10 (0)
       /   \
   6(+1)   8(0)
   /
 3(0)

Аналогично, левое поддерево 7 выросло в высоту, поэтому его коэффициент баланса должен быть увеличен:

           9(+1?)
          /       \
        7 (+1)    10 (0)
       /   \
   6(+1)   8(0)
   /
 3(0)

Наконец, 9 левых поддеревьев выросли на единицу, что дает следующее:

           9(+2!)
          /       \
        7 (+1)    10 (0)
       /   \
   6(+1)   8(0)
   /
 3(0)

И здесь мы находим, что 9 имеет коэффициент баланса +2, а это значит, что нам нужно сделать поворот. Консалтинг Википедия - отличная таблица всех ролей деревьев AVL, мы видим, что мы находимся в том случае, когда мы имеем коэффициент баланса +2, где левый ребенок имеет коэффициент баланса +1. Это означает, что мы делаем правильное вращение и тянем 7 выше 9, как показано здесь:

        7(0)
       /   \
   6(+1)     9(0)
   /       /   \
 3(0)    8(0)   10 (0)

Et voil & agrave;! Теперь дерево сбалансировано.

Обратите внимание, что когда мы делали эту процедуру исправления, нам не нужно было просматривать все дерево. Вместо этого все, что нам нужно было сделать, это посмотреть путь доступа и проверить каждый node там. Как правило, при внедрении дерева AVL ваша процедура вставки будет выполнять следующие действия:

Если дерево равно null:
- Вставьте node с коэффициентом баланса 0.
- Верните, что высота дерева увеличилась на 1.
В противном случае:
- Если значение для вставки совпадает с текущим node, ничего не делать.
- В противном случае рекурсивно вставьте node в правильное поддерево и получите значение, которое изменило высота дерева.
- Измените коэффициент баланса этого node в зависимости от того, какая величина высоты поддерева изменилась.
- Если это задает последовательность вращений, выполните их.
- Возвращает полученное изменение высоты этого дерева.

Поскольку все эти операции являются локальными, общая выполняемая работа основана исключительно на длине пути доступа, которая в этом случае равна O (log n), поскольку деревья AVL всегда сбалансированы.

Надеюсь, это поможет!

PS: Вашим первоначальным примером было это дерево:

Обратите внимание, что это дерево на самом деле не является законным деревом AVL, так как коэффициент баланса корня node равен +2. Если вы последовательно поддерживаете баланс дерева с помощью алгоритма AVL, вы никогда не столкнетесь с этим случаем.