20

クラスの 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;
}

私の計画は、balance() の呼び出しでツリーのバランスが必要かどうかを確認し、必要に応じてバランスを取ることでした。問題は、ツリーをトラバースして正しい不均衡ノードを見つける方法さえ理解できないことです。ツリーを再帰的にトラバースする方法は知っていますが、そのアルゴリズムを変換して、最も低い不均衡なノードを見つけることができないようです。反復アルゴリズムの作成にも問題があります。どんな助けでも大歓迎です。:)

4

4 に答える 4

28

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

ツリーを変更するときは常にバランスをチェックする(必要に応じてローテーションを行う) 必要があります。それは物事を複雑にするだけです...

アップデート

実装に誤りがあります。以下のコードでは、ツリーが不均衡であるかどうかを正しくチェックしていません。高さが 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) {...

いくつかのリソース

于 2010-11-18T21:50:09.510 に答える
11

待って、待って、待って。何かを挿入するたびに、すべてのブランチの「高さ」を実際にチェックするわけではありませんね。

高さを測定することは、すべてのサブブランチを横断することを意味します。手段-そのようなツリーへのすべての挿入はO（N）の費用がかかります。もしそうなら-あなたはそのような木が何を必要としますか？ソートされた配列を使用することもできます。これにより、O（N）の挿入/削除とO（log N）の検索が可能になります。

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

于 2010-11-18T22:08:54.910 に答える
1

goto http://code.google.com/p/self-balancing-avl-tree/、追加、削除などのすべての通常の操作に加えて、連結と分割が実装されています

于 2012-07-12T22:48:25.057 に答える
1

コメント アウトされているのは、上を右回転するコードと左回転を左回転するコードです。下は、作業中の右回転と作業中の左回転です。上記の回転のロジックは逆になっていると思います。

 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;
}
于 2012-07-24T02:24:10.287 に答える