스플레이 트리를 구현하기 위한 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