平衡AVL樹

Question

我在平衡AVL樹方面遇到了問題。我已經搜索了高低的步驟，以便如何平衡它們，並且我無法得到任何有用的東西。

我知道有4種：

• 單左旋轉
• 單權流轉
• 雙左 - 右旋轉
• 雙右向左旋轉

但我只是不能得到如何選擇其中之一和將哪個節點應用於！

任何幫助將不勝感激！

Answer 1

這是Java實現，你會得到的算法存在的想法：

private Node<T> rotate(Node<T> n) { 
    if(n.getBf() < -1){ 
      if(n.getRight().getBf() <= 0){ 
       return left(n);   
      } 
      if(n.getRight().getBf() > 0){ 
       return rightLeft(n); 
      } 
    } 
    if(n.getBf() > 1){ 
      if(n.getLeft().getBf() >= 0){ 
       return right(n); 
      } 
      if(n.getLeft().getBf() < 0){ 
       return leftRight(n); 
      } 
    } 
    return n; 
} 

4個旋轉的單獨的方法在這裏：

/** 
* Performs a left rotation on a node 
* 
* @param n The node to have the left rotation performed on 
* @return The new root of the subtree that is now balanced due to the rotation 
*/ 
private Node<T> left(Node<T> n) { 
    if(n != null){ 
     Node<T> temp = n.getRight(); 
     n.setRight(temp.getLeft()); 
     temp.setLeft(n); 
     return temp; 
    } 
    return n; 
} 

/** 
* Performs a right rotation on a node 
* 
* @param n The node to have the right rotation performed on 
* @return The new root of the subtree that is now balanced due to the rotation 
*/ 
private Node<T> right(Node<T> n) { 
    if(n != null){ 
     Node<T> temp = n.getLeft(); 
     n.setLeft(temp.getRight()); 
     temp.setRight(n); 
     return temp; 
    } 
    return n; 
} 

/** 
* Performs a left right rotation on a node 
* 
* @param n The node to have the left right rotation performed on 
* @return The new root of the subtree that is now balanced due to the rotation 
*/ 
private Node<T> leftRight(Node<T> n) { 
    n.setLeft(left(n.getLeft())); 
    Node<T> temp = right(n); 
    return temp; 
} 

/** 
* Performs a right left rotation on a node 
* 
* @param n The node to have the right left rotation performed on 
* @return The new root of the subtree that is now balanced due to the rotation 
*/ 
private Node<T> rightLeft(Node<T> n) { 
    n.setRight(right(n.getRight())); 
    Node<T> temp = left(n); 
    return temp; 
} 

Answer 2

AVL樹中的關鍵不變量是每個節點的平衡因子是-1,0或+1。這裏，「平衡因子」是左側和右側子樹之間高度的差異。 +1表示左側子樹比右側子樹高一個，-1表示左側子樹比右側子樹短一些，0表示子樹的大小相同。這些信息通常緩存在每個節點中。

當您獲得平衡因子爲-2或+2的節點時，您需要進行旋轉。下面是當旋轉是必要的一個可能的設置：

  u (-2) 
     /\ 
     A v (-1) 
     /\ 
      B C 

如果我們填寫這些樹的高度，我們得到

  u h + 2 
     /\ 
    h-1 A v h + 1 
     /\ 
     h-1 B C h 

如果發生這種情況，做一個單一的右旋轉產量

  v h+1 
     /\ 
    h u C h 
    /\ 
h-1 A B h-1 

嘿！樹是平衡的。這棵樹的鏡像也可以用一個左旋轉來解決。

所有AVL樹的旋轉都可以簡單地通過枚舉小範圍內的可能的平衡因子，然後確定在每一步應該應用哪些旋轉來確定。我會把這個作爲練習留給讀者。 :-)如果你只是想查找答案，Wikipedia article on AVL trees有一個很好的圖片，總結了可能需要應用的所有旋轉。

希望這會有所幫助！