0

私が開発したAVLツリーを使用するためのコードを投稿します。挿入方法、avlinsert方法は以下のとおりです。私はこのコードを紙で開発しましたが、テストされていませんが、これが機能することを願っています。私が議論したい主な問題は、ノードが最初にコードを見るバランスファクターです。このようにして、私が何を求めようとしているのかが明確になります。だからここにコードがあります：

    treeNode* avlinsert(treeNode* tree, int info)
    {
        treeNode* newNode=new treeNode;
        newNode->setinfo(info);
        newNode->setbalance(0);
        treeNode* p,*q;
        bool duplicate=false;
        p=q=tree;
        stack s; //I have made this stack already and now I am using it here.
        //Now the the while loop block will check for duplicate nodes, this block prevents the duplicate insertion.
        while (q!=NULL)
        {
            p=q;
            if (info < p -> getinfo())
                q=p->getleft();
            else if (info>p->getinfo())
                q=p->getright();
            else
            {
                duplicate=true;
                cout<<"Trying to insert duplicate";
                break;
            }
        }//while loop ended.
        //Now checking for duplicates.
        if (duplicate)
            return tree;
        p=q=tree;
        //Now below is the main block of while loop which calculates the balance factors of nodes and helps in inserting nodes at proper positions.
        while (q!=NULL)
        {
            p=q;
            if (info < p -> getinfo())
            {
                p->setbalance(p -> getbalance()+1);
                s.push(p);//pushing into stack
                q=p->getleft();
            }

            else if (info > p -> getinfo())
            {

                p->setbalance(p->getbalance()-1);
                q=p->getright();
            }

        }//while loop ended
        //Now the below code block will actually inserts nodes.
        if (info < p -> getinfo())
            p->setleft(newNode);
        else if (info > p -> getinfo())
            p->setright(newNode);
        //After this insertion we need to check the balance factor of the nodesand perform the approprite rotations.

        while (!s.isempty())
        {
            treeNode node;
            node=s.pop();
            int balance;
            balance=node.getbalance();
            if (balance==2)
            {
                s.Makeempty();   // We have found the node whoes balance factor is violating avl condition so we don't need other nodes in the stack, therefor we are making stack empty.
                treeNode* k1,*k3;
                k1=&node; //This is the node whoes balance factor is violating AVL condition.
                k3=&(k1 -> getleft()); //Root of the left subtree of k1.
                //Identifying the cases of insertion
                if (info < k3 -> getinfo())  //This is the case of insertion in left subtree of  left child of k1 here we need single right rotation.
                    root=Rightrotation(k1);  //Here root is the private data member.

                //Next case is the insertion in right subtree of left child of k1.
                if (info > k3 ->getinfo())
                    root=LeftRightrotation(k1);
            }//end of if statement.
        }//while loop ended

これはコード全体ではありませんが、私がやろうとしていることを示すには十分です。このコードで、挿入中（2番目のwhileループブロック）にノードのバランス係数を設定していることがわかりました。OK、これで結構です。しかし、この挿入の後、回転を実行する必要があります。回転のコードもありますが、主な問題は、ノードが回転するときに、回転のコードでノードのバランス係数をリセットする必要があることです。これが私の問題です。どうすればいいですか？そして、コードスニペットは何でしょうか？

4

1 に答える 1

1

「...ローテーションのコードでノードのバランス係数をリセットする必要があります。」

ローテーションのコード内に何かを追加したい場合は、助けを得るためにローテーション関数のコードも投稿する必要があります。

それ以外の場合、ローテーション後に各ノードのバランス係数を更新するだけの場合は、この再帰関数が役立ちます (呼び出してツリーのルート ノードを渡すだけです)。

int updateBalanceFactors(treeNode *node)
{
    if(node == NULL)
        return 0;
    node->setbalance(updateBalanceFactors(node->getright()) - updateBalanceFactors(node->getleft()));
    return ((node->getbalance() < 0 ? -node->getbalance() : node->getbalance()) + 1);
}

また、コードにいくつかのエラーを見つけましたが、プログラムを実行しようとするとエラーが見つかると確信しています。次の点に注意してください。

  1. スタックの実装がどのように機能するかはわかりませんが、スタックにポインターをプッシュしてから、オブジェクトをポップすることがわかります。

    s.push(p);

    ツリーノード ノード = s.pop();

  2. AVL ツリーの左側のサブツリーをトラバースするときにのみノードをスタックにプッシュし、右側に移動するときはプッシュしません。何故ですか？

  3. newNode をツリーに挿入するときは、newNode の左右の子を NULL に設定することを忘れないでください (コンストラクターで既に行っているかもしれませんが、よくわかりません)。

  4. 通常、AVL ツリーでは、ノードの左側のサブツリーが右側のサブツリーよりも高い場合、そのノードのバランス係数は負になります。コードでそれを変更したい場合があります。そのままにしておきたい場合は、再帰関数を変更する必要があります。

  5. 最後になりましたが、バランス係数が 2 に等しいかどうかを確認します (ツリーに回転が必要な場合)。バランス係数も負の値を取ることができることに注意してください (左のサブツリーが右のサブツリーよりも高い場合)。

皆様、新年あけましておめでとうございます ：-）

于 2009-12-31T20:38:03.037 に答える