2

OK、チェックしたい場合は、ここにスプレイアルゴリズムがあります。 スプレイアルゴリズム

これが私のスプレイ関数です:

template <class WA>
void SplayTree<WA>::Do_Splay(SplayNODE<WA> *temp)   //temp is the node which is to be splayed
{
    if (temp==root) //if temp is root then
    {   return;     }   //Do Nothing

    else if (root->left==temp || root->right==temp) //else if temp is a child of root
    {
        if (root->left==temp)   //if temp is left child of root then
        {
            Zig(root);  //perform ZIG
        }
        else if (root->right==temp) //else if temp is right child of root then
        {
            Zag(root);  //perform ZAG
        }
    }
    else    //if temp is some node lower in tree then
    {
        SplayNODE<WA> *father = findfather(temp, root);
        SplayNODE<WA> *grandfather = findfather(father, root);
        //cout<<"\n\tf = "<<father->key<<"\tgf = "<<grandfather->key;
        ////--------------------------------------------------------------------//-------////
        if ( grandfather->left == father)   //if father itself is left child
        {
            if(father->left == temp)    //if temp is left child of father then
            {       //CASE = ZIG ZIG
                cout<<"\tZig(father)---Zag(grandfather)";
                Zig(grandfather);   
                Zig(father);        
            }

            else if ( father->right == temp )   //if temp is right child of father then
            {       //CASE = ZIG ZAG
                cout<<"\tZig(father)---Zag(grandfather)";
                Zig(father);    
                Zag(grandfather);
            }
        }
        //--------------------------------------------------------------------//-------////
        if (grandfather->right == father)   //if father itself is right child
        {
            if(father->right == temp) 
            {       //CASE = ZAG ZAG
                cout<<"\tZag(grandfather)---Zag(father)";
                Zag(grandfather);
                Zag(father);
            }
            else if (father->left == temp)
            {       //CASE = ZAG ZIG
                cout<<"\tZag(father)---Zig(grandfather)";
                Zag(father);
                Zig(grandfather);
            }
        }
        ////--------------------------------------------------------------------//-------////
    }
}

以下は、ジグ(左に1回転)とザグ(右に1回転)の方法です。

template <class WA>
void SplayTree<WA>::Zig(SplayNODE<WA> * & k2)   //k2 is temp node where imbalance is present & we have to rotate it
{
    SplayNODE<WA> *k1 = k2->left;   //create copy of temp's left & store it in k1
    k2->left = k1->right;   //make k1's right child as temp's left child
    k1->right = k2; //make k1 as parent of temp node    
    k2 = k1;    //assign k1 as new temp node (this is done because temp was passed by reference)
}
//==============================//==============================//
template <class WA>
void SplayTree<WA>::Zag(SplayNODE<WA> * & k2)
{
    SplayNODE<WA> *k1 = k2->right;  //create copy of temp's right child & store it in k1
    k2->right = k1->left;   //store k1's left child as temp's right child
    k1->left = k2;  //make k2 as left child of k1
    k2 = k1;    //assign k1 as temp node (due to reference of k2)
}
//==============================//==============================//

&これが私のf**の問題です。まず、検索機能のみで表示します。つまり、特定のキーを持つノードが見つかった場合はスプレイします。

私の検索機能:

template <class WA>
SplayNODE<WA>* SplayTree<WA>::search(SplayNODE<WA> *temp, WA value) /////PVT DEFINITION
{
    SplayNODE<WA> *to_searched = 0; //created new node pointer in which address of required node will be saved
    if (temp!=0)    //if arg. given temp node is not empty, then
    {
        if (temp->key==value)   //if temp node has user-specified value then
        {   
            to_searched = temp;     //assign address of temp to to_searched node, which will be return @ the end
            Do_Splay(temp); //perform splay at node which is found
        }   
        if (to_searched==0) //if node is still empt then
        {   to_searched = search(temp->left, value);    }   //recursive call to search in left sub-tree of temps
        if (to_searched==0) //if node is still empt then
        {   to_searched = search(temp->right, value);   }   //recursive call to search in right sub-tree of temps
    }
    return to_searched; //Finally return the searched node
}
//==============================//==============================//

ノードがrootの子である場合、以下は正常に機能します。-ジグシングル-ザグシングルしかし、シングルノードをダウンさせるとすぐに問題が発生します。私はこれらのことのどれもうまく実行することができません。 ジグジグ-ジグザグ-ザグザグ-ザグジグ

これがサンプルツリーです。(ジグジグケース)

        20
       /  \
     10   25
    /  \
   5   15

5を検索すると、答えは次のようになります。

 5
  \
  10
    \
    20
   /  \
  15  25

しかし、私の出力は次のようになります。

   20
  /  \
15   25

何が問題なのか理解できません。これを100回ドライランしましたが。:( すべての助けをいただければ幸いです。よろしくお願いします。

4

1 に答える 1

0

アルゴリズムの変更とTry...

{"X は右-左の孫ですか?"} ---YES---> {p を中心に右回転、g を中心に左回転}

{"X は左右の孫ですか?"} ---YES---> {p を中心に左回転、g を中心に右回転}

于 2013-01-12T06:01:12.030 に答える