平衡一個AVL樹（C++）

Question

我有最困難的時間試圖找出如何平衡我的課的AVL樹。我知道了這個插入：

Node* Tree::insert(int d) 
{ 
    cout << "base insert\t" << d << endl; 
    if (head == NULL) 
     return (head = new Node(d)); 
    else 
     return insert(head, d); 
} 

Node* Tree::insert(Node*& current, int d) 
{ 
    cout << "insert\t" << d << endl; 
    if (current == NULL) 
     current = new Node(d); 
    else if (d < current->data) { 
     insert(current->lchild, d); 
     if (height(current->lchild) - height(current->rchild)) { 
      if (d < current->lchild->getData()) 
       rotateLeftOnce(current); 
      else 
       rotateLeftTwice(current); 
     } 
    } 
    else if (d > current->getData()) { 
     insert(current->rchild, d); 
     if (height(current->rchild) - height(current->lchild)) { 
      if (d > current->rchild->getData()) 
       rotateRightOnce(current); 
      else 
       rotateRightTwice(current); 
     } 
    } 

    return current; 
} 

我的計劃是有來電平衡（）檢查，看看樹的需求平衡，然後平衡需要。麻煩的是，我甚至無法弄清楚如何遍歷樹來找到正確的不平衡節點。我知道如何遞歸遍歷樹，但似乎無法將該算法轉化爲找到最低的不平衡節點。我在編寫迭代算法時也遇到了麻煩。任何幫助，將不勝感激。 :)

Answer 1

你可以在給定的點測量的一個分支height計算不平衡

（記得在高度（水平差）> = 2表示你的樹是不是平衡）

int Tree::Height(TreeNode *node){ 
    int left, right; 

    if(node==NULL) 
     return 0; 
    left = Height(node->left); 
    right = Height(node->right); 
    if(left > right) 
      return left+1; 
     else 
      return right+1; 
} 

根據不均勻，那麼你可以旋轉，必要

void Tree::rotateLeftOnce(TreeNode*& node){ 
    TreeNode *otherNode; 

    otherNode = node->left; 
    node->left = otherNode->right; 
    otherNode->right = node; 
    node = otherNode; 
} 


void Tree::rotateLeftTwice(TreeNode*& node){ 
    rotateRightOnce(node->left); 
    rotateLeftOnce(node); 
} 


void Tree::rotateRightOnce(TreeNode*& node){ 
    TreeNode *otherNode; 

    otherNode = node->right; 
    node->right = otherNode->left; 
    otherNode->left = node; 
    node = otherNode; 
} 


void Tree::rotateRightTwice(TreeNode*& node){ 
    rotateLeftOnce(node->right); 
    rotateRightOnce(node); 
} 

現在我們知道如何旋轉，可以說你要插入樹的值...首先，我們檢查樹是否爲空或不

TreeNode* Tree::insert(int d){ 
    if(isEmpty()){ 
     return (root = new TreeNode(d)); //Is empty when root = null 
    } 
    else 
     return insert(root, d);   //step-into the tree and place "d" 
} 

當樹不空我們使用遞歸遍歷樹，並獲得需要

TreeNode* Tree::insert(TreeNode*& node, int d_IN){ 
    if(node == NULL) // (1) If we are at the end of the tree place the value 
     node = new TreeNode(d_IN); 
    else if(d_IN < node->d_stored){ //(2) otherwise go left if smaller 
     insert(node->left, d_IN);  
     if(Height(node->left) - Height(node->right) == 2){ 
      if(d_IN < node->left->d_stored) 
       rotateLeftOnce(node); 
      else 
       rotateLeftTwice(node); 
     } 
    } 
    else if(d_IN > node->d_stored){ // (3) otherwise go right if bigger 
     insert(node->right, d_IN); 
     if(Height(node->right) - Height(node->left) == 2){ 
      if(d_IN > node->right->d_stored) 
       rotateRightOnce(node); 
      else 
       rotateRightTwice(node); 
     } 
    } 
    return node; 
} 

，你應該經常檢查平衡（如果需要做旋轉）當修改樹時，沒有一點等到樹結束的時候才結束。這只是複雜的事情......

---

UPDATE

。在你執行一個錯誤，在下面你沒有正確檢查樹是否是不平衡的代碼。您需要檢查高度是否等於2（因此不平衡）。因此，該代碼波紋管......

if (height(current->lchild) - height(current->rchild)) { ... 

if (height(current->rchild) - height(current->lchild)) {... 

應該成爲...

if (height(current->lchild) - height(current->rchild) == 2) { ... 

if (height(current->rchild) - height(current->lchild) == 2) {... 

---

一些資源

• AVL Tree ~ Imprementation in C++
• AVL Tree ~ Applet

Answer 2

等等，等等，等等。 每次插入東西時都不會檢查每個分支的「高度」，對嗎？

測量高度意味着橫穿所有的子分支。手段 - 每一個插入這樣的樹將花費O（N）。如果是這樣 - 你需要這樣一棵樹嗎？您也可以使用排序後的數組：它提供O（N）插入/刪除和O（log N）搜索。

一個正確的AVL處理算法必須在每個節點存儲左右高度差。然後，在每次操作（插入/刪除）後 - 您必須確保所有受影響的節點都不會太多不平衡。要做到這一點，你要做所謂的「旋轉」。在他們期間你不要實際上重新測量高度。您不必：每次輪換都會通過一些可預測的值來改變受影響節點的平衡。

Answer 3

轉到http://code.google.com/p/self-balancing-avl-tree/，如ADD所有常用操作，刪除的落實，加上CONCAT和分裂

Answer 4

註釋掉的代碼是正確的旋轉上和左旋轉，下面是我的工作的權利和旋轉，我工作的左旋轉。我認爲，在旋轉上述邏輯的反轉：

void rotateRight(Node *& n){ 
    //Node* temp = n->right; 
    //n->right = temp->left; 
    //temp->left = n; 
    //n = temp; 
    cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE RIGHT}}}}}}}}}}}}}}}}}}}}}" << endl; 
    Node *temp = n->left; 
    n->left = temp->right; 
    temp->right = n; 
    n = temp; 
} 

void rotateLeft(Node *& n){ 
    //Node *temp = n->left; 
    //n->left = temp->right; 
    //temp->right = n; 
    //n = temp; 
    cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE LEFT}}}}}}}}}}}}}}}}}}}}}" << endl; 
    Node* temp = n->right; 
    n->right = temp->left; 
    temp->left = n; 
    n = temp; 
}