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; 
} 

私の計画は、（バランスをとるための呼び出しを持っていることでした）木がバランスをとる必要があり、必要に応じて、その後バランスをとるかどうかを確認します。問題は、正しいアンバランスノードを見つけるためにツリーをどのようにトラバースするのか把握できないことです。再帰的にツリーをたどる方法はわかっていますが、そのアルゴリズムを最小の不平衡ノードを見つけることに変換することはできません。私はまた、繰り返しアルゴリズムを書くのに問題があります。どんな助けもありがとう。 :)（2は、あなたのツリーはバランスがとれていないことを意味し、高さ（レベルの差を覚えている）> =）

Answer 1

あなたがアンバランスに

を計算するために与えられた時点で、枝のheightを測定することができ

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（ログN）検索が行われます。

正しいAVL処理アルゴリズムは、の各ノードに左右の高さの差を格納する必要があります。次に、すべての操作（挿入/削除）後に、影響を受けるノードのどれもアンバランスすぎないようにする必要があります。これを行うには、いわゆる「回転」を行います。それらの間に実際に高さを再測定しないでください。すべてのローテーションによって、影響を受けるノードのバランスが予測可能な値だけ変更されます。

Answer 3

後藤 http://code.google.com/p/self-balancing-avl-tree/、などのすべての通常の操作は、削除、追加が実装されている

、プラス連結及びコメントアウト

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; 
}