यह स्प्ले ट्री को इम्प्लीमेंट करने के लिए एक C++ प्रोग्राम है।
क्लास विवरण:
Begin class SplayTree में फंक्शन हैं: टॉप-डाउन स्प्ले ट्री इम्प्लीमेंट करने के लिए Splay() फंक्शन बनाएं। यहां head.rch लेफ्ट ट्री की ओर इशारा करता है और head.lch राइट ट्री की ओर इशारा करता है। राइट ट्री का लिंक बनाएं। लेफ्ट ट्री का लिंक बनाएं। लेफ्ट, मिडल और राइट ट्री को असेंबल करें। नोड्स को ट्री में डालने के लिए Insert() फंक्शन बनाएं। यदि root->k >= सभी कुंजी root->lch होंगी Else if root->k <= सभी कुंजी root->rch होंगी Else Return root. End
क्लास विवरण और स्यूडोकोड:
Begin k वेरिएबल और लेफ्ट चाइल्ड पॉइंटर lch और राइट चाइल्ड पॉइंटर rch घोषित करने के लिए एक स्ट्रक्चर s बनाएं। एक क्लास SplayTree बनाएं: दाएं घुमाने के लिए RR_Rotate फंक्शन बनाएं। बाएं घुमाने के लिए LL_Rotate फंक्शन बनाएं। टॉप-डाउन स्प्ले ट्री इम्प्लीमेंट करने के लिए Splay फंक्शन बनाएं। यहां head.rch लेफ्ट ट्री की ओर इशारा करता है और head.lch राइट ट्री की ओर इशारा करता है। राइट ट्री का लिंक बनाएं। लेफ्ट ट्री का लिंक बनाएं। लेफ्ट, मिडल और राइट ट्री को असेंबल करें। ट्री में नोड्स बनाने के लिए New_Node() फंक्शन बनाएं। ट्री में नोड्स डालने के लिए Insert() फंक्शन बनाएं। यदि root->k >= सभी कुंजी root->lch होंगी Else if root->k >= सभी कुंजी root->rch होंगी Else Return root. ट्री से नोड्स हटाने के लिए Delete() फंक्शन बनाएं। ट्री में नोड्स खोजने के लिए Search() फंक्शन बनाएं। ट्री के इनऑर्डर ट्रैवर्सल के लिए InOrder() फंक्शन बनाएं। main() फंक्शन बनाएं, और पसंद के अनुसार सेलेक्टिव फंक्शन कॉल करें। End
उदाहरण कोड
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; struct s//नोड घोषणा { 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)//नोड हटाएं { s* temp; if (!root)//यदि ट्री खाली है return NULL; root = Splay(key, root); if (key != root->k)//यदि ट्री में एक आइटम है 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)//खोज रहे हैं { return Splay(key, root); } void InOrder(s* root)//इनऑर्डर ट्रैवर्सल { 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©//स्विच ऑपरेशन करें { 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
