スプレーツリーを実装するC++プログラム

これは、スプレーツリーを実装するためのC++プログラムです。

クラスの説明：

Begin
   class SplayTree has the functions:
      Create a function Splay() to implement top-down splay tree.
      Here head.rch points to the Left tree and head.lch points to the right tree.
      Create a link to Right tree.
      Create a link to Left tree.
      Assemble left, middle and right tree.
   Create a function Insert() to insert nodes into the tree.
      If root->k >= all keys will be the root→lch
      Else if
      root->k <=all keys will be the root→rch
      Else
      Return root.
End

クラスの説明と擬似コード：

Begin
   Create a structure s to declare variable k and left child pointer lch and right child pointer rch.
   Create a class SplayTree :
      Create a function RR_Rotate to rotate to the right.
      Create a function LL_Rotate to rotate to the left.
      Create a function Splay to implement top-down splay tree.
      Here head.rch points to the Left tree and head.lch
      points to the right tree.
      Create a link to Right tree.
      Create a link to Left tree.
      Assemble left, middle and right tree.
   Create a function New_Node() to create nodes in the tree.
   Create a function Insert() to insert nodes into the tree.
      If root→k >= all keys will be the root→lch
      Else if
      root->k >=all keys will be the root→rch
      Else
      Return root.
   Create a function Delete() to delete nodes from the tree.
   Create a function Search() to search the nodes in the tree.
   Create a function InOrder() for InOrder traversal of the tree.
   Create a function main(), and perform selective function calls as per choice.
End

サンプルコード

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct s//node declaration
{
   int k;  
   s* lch;
   s* rch;
};
class SplayTree
{
   public:
   s* RR_Rotate(s* k2)
   {
      s* k1 = k2->lch;
      k2->lch = k1->rch;
      k1->rch = k2;
      return k1;
   }
   s* LL_Rotate(s* k2)
   {
      s* k1 = k2->rch;
      k2->rch = k1->lch;
      k1->lch = k2;
      return k1;
   }
   s* Splay(int key, s* root)
   {
      if (!root)
      return NULL;
      s header;
      header.lch= header.rch = NULL;
      s* LeftTreeMax = &header;
      s* RightTreeMin = &header;
      while (1)
      {
         if (key < root->k)
         {
            if (!root->lch)
            break;
            if (key< root->lch->k)
            {
               root = RR_Rotate(root);
               if (!root->lch)
               break;
            }
            RightTreeMin->lch= root;
            RightTreeMin = RightTreeMin->lch;
            root = root->lch;
            RightTreeMin->lch = NULL;
         }
         else if (key> root->k)
         {
            if (!root->rch)
            break;
            if (key > root->rch->k)
            {
               root = LL_Rotate(root);
               if (!root->rch)
               break;
            }
            LeftTreeMax->rch= root;
            LeftTreeMax = LeftTreeMax->rch;
            root = root->rch;
            LeftTreeMax->rch = NULL;
         }
         else
         break;
      }
      LeftTreeMax→rch = root->lch;
      RightTreeMin→lch = root->rch;
      root->lch = header.rch;
      root->rch = header.lch;
      return root;
   }
   s* New_Node(int key)
   {
      s* p_node = new s;
      if (!p_node)
      {
         fprintf(stderr, "Out of memory!\n");
         exit(1);
      }
      p_node->k = key;
      p_node->lch = p_node->rch = NULL;
      return p_node;
   }
   s* Insert(int key, s* root)
   {
      static s* p_node = NULL;
      if (!p_node)
      p_node = New_Node(key);
      else
      p_node->k = key;
      if (!root)
      {
         root = p_node;
         p_node = NULL;
         return root;
      }
      root = Splay(key, root);
      if (key < root->k)
      {
         p_node->lch= root->lch;
         p_node->rch = root;
         root->lch = NULL;
         root = p_node;
      }
      else if (key > root->k)
      {
         p_node->rch = root->rch;
         p_node->lch = root;
         root->rch = NULL;
         root = p_node;
      }
      else
      return root;
      p_node = NULL;
      return root;
   }
   s* Delete(int key, s* root)//delete node
   {
      s* temp;
      if (!root)//if tree is empty
      return NULL;
      root = Splay(key, root);
      if (key != root->k)//if tree has one item
      return root;
      else
      {
         if (!root->lch)
         {
            temp = root;
            root = root->rch;
         }
         else
         {
            temp = root;
            root = Splay(key, root->lch);
            root->rch = temp->rch;
         }
         free(temp);
         return root;
      }
   }
   s* Search(int key, s* root)//seraching
   {
      return Splay(key, root);
   }
   void InOrder(s* root)//inorder traversal
   {
      if (root)
      {
         InOrder(root->lch);
         cout<< "key: " <<root->k;
         if(root->lch)
         cout<< " | left child: "<< root->lch->k;
         if(root->rch)
         cout << " | right child: " << root->rch->k;
         cout<< "\n";
         InOrder(root->rch);
      }
   }
};
int main()
{
   SplayTree st;
   s *root;
   root = NULL;
   st.InOrder(root);
   int i, c;
   while(1)
   {
      cout<<"1. Insert "<<endl;
      cout<<"2. Delete"<<endl;
      cout<<"3. Search"<<endl;
      cout<<"4. Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch©//perform switch operation
      {
         case 1:
            cout<<"Enter value to be inserted: ";
            cin>>i;
            root = st.Insert(i, root);
            cout<<"\nAfter Insert: "<<i<<endl;
            st.InOrder(root);
            break;
         case 2:
            cout<<"Enter value to be deleted: ";
            cin>>i;
            root = st.Delete(i, root);
            cout<<"\nAfter Delete: "<<i<<endl;
            st.InOrder(root);
            break;
         case 3:
            cout<<"Enter value to be searched: ";
            cin>>i;
            root = st.Search(i, root);
            cout<<"\nAfter Search "<<i<<endl;
            st.InOrder(root);
            break;
         case 4:
            exit(1);
         default:
            cout<<"\nInvalid type! \n";
      }
   }
   cout<<"\n";
   return 0;
}

出力

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 7
After Insert: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 6
After Insert: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 4
After Insert: 4
key: 4 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 5
After Insert: 5
key: 4
key: 5 | left child: 4 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 3
After Insert: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 2
After Insert: 2
key: 2 | right child: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 3
Enter value to be searched: 2
After Search 2
key: 2 | right child: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 2
Enter value to be deleted: 3
After Delete: 3
key: 2 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 4