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

Question

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

я рассмотрю его с левой ротационный

Таким образом, следующая ситуация проста:

 8 
    /\ 
    7 10 
/
    6 
/
3 

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

8 
/\ 
    6 10 
/\ 
3 7 

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

Следующий пример, где вещи становятся немного мохнатый, на мой взгляд:

 9 
    /\ 
    7 10 
/\ 
    6 8 
/
3 

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

 7 
    /\ 
    6 9 
//\ 
    3 8 10 

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

псевдокод:

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 

    } 

} 

Заранее спасибо!

Answer 1

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

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

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

 9 
    /\ 
    7 10 
/\ 
    6 8 

Давайте начнем с выписыванием разницы в факторах баланса, связанные с каждым узлом (это важно, чтобы 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 узла +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, а это значит, что нам нужно сделать поворот. Консалтинг Wikipedia's great table of all AVL tree rotations, мы видим, что мы находимся в том случае, когда мы имеем коэффициент баланса +2, где левый ребенок имеет коэффициент баланса +1. Это означает, что мы делаем правое вращение и потяните 7 выше 9, как показано здесь:

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

Et Voil & agrave ;! Дерево теперь сбалансировано.

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

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

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

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

---

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

 8 
    /\ 
    7 10 
/
    6 
/
3 

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