স্প্লে ট্রি বাস্তবায়নের জন্য C++ প্রোগ্রাম

এটি স্প্লে ট্রি বাস্তবায়নের জন্য একটি C++ প্রোগ্রাম।

শ্রেণির বিবরণ:

Begin class SplayTree-এর ফাংশন রয়েছে:টপ-ডাউন স্প্লে ট্রি বাস্তবায়ন করতে একটি ফাংশন Splay() তৈরি করুন। এখানে head.rch বাম গাছের দিকে নির্দেশ করে এবং head.lch ডান গাছের দিকে নির্দেশ করে। ডান গাছের একটি লিঙ্ক তৈরি করুন। বাম গাছের একটি লিঙ্ক তৈরি করুন। বাম, মধ্য এবং ডান গাছ একত্রিত করুন। একটি ফাংশন Insert() তৈরি করুন গাছে নোড সন্নিবেশ করতে। যদি রুট->কে>=সব কী রুট হয় 
শ্রেণির বর্ণনা এবং সিউডোকোড:
 ভেরিয়েবল k এবং বাম চাইল্ড পয়েন্টার lch এবং ডান চাইল্ড পয়েন্টার rch ঘোষণা করতে একটি কাঠামো তৈরি করুন। একটি ক্লাস স্প্লেট্রি তৈরি করুন :ডানদিকে ঘোরাতে একটি ফাংশন RR_Rotate তৈরি করুন। বাম দিকে ঘোরাতে একটি ফাংশন LL_Rotate তৈরি করুন। টপ-ডাউন স্প্লে ট্রি বাস্তবায়নের জন্য একটি ফাংশন স্প্লে তৈরি করুন। এখানে head.rch বাম গাছের দিকে নির্দেশ করে এবং head.lch ডান গাছের দিকে নির্দেশ করে। ডান গাছের একটি লিঙ্ক তৈরি করুন। বাম গাছের একটি লিঙ্ক তৈরি করুন। বাম, মধ্য এবং ডান গাছ একত্রিত করুন। ট্রিতে নোড তৈরি করতে একটি ফাংশন New_Node() তৈরি করুন। একটি ফাংশন Insert() তৈরি করুন গাছে নোড সন্নিবেশ করতে। যদি root→k>=সব কী হবে রুট→lch অন্যথায় যদি root->k>=সব কী হবে রুট→rch অন্যথায় রিটার্ন রুট। গাছ থেকে নোড মুছে ফেলার জন্য Delete() ফাংশন তৈরি করুন। ট্রিতে নোড অনুসন্ধান করতে একটি ফাংশন Search() তৈরি করুন। গাছের InOrder ট্রাভার্সালের জন্য একটি ফাংশন InOrder() তৈরি করুন। একটি ফাংশন main() তৈরি করুন এবং পছন্দ অনুযায়ী সিলেক্টিভ ফাংশন কল করুন 
উদাহরণ কোড
 
#include #include #include নেমস্পেস ব্যবহার করে std;struct s//node declaration{int k; s*lch; s* rch;}; ক্লাস SplayTree{ পাবলিক:s* RR_Rotate(s* k2) { s* k1 =k2->lch; k2->lch =k1->rch; k1->rch =k2; k1 ফেরত; } s* LL_Rotate(s* k2) { s* k1 =k2->rch; k2->rch =k1->lch; k1->lch =k2; k1 ফেরত; } s* Splay(int কী, s* root) { if (!root) NULL ফেরত দেয়; s হেডার; header.lch=header.rch =NULL; s* LeftTreeMax =&header; s* RightTreeMin =&header; যখন (1) { if (কী k) { if (!root->lch) বিরতি; if (keylch->k) { root =RR_Rotate(root); যদি (!root->lch) বিরতি; } RightTreeMin->lch=root; RightTreeMin =RightTreeMin->lch; root =root->lch; RightTreeMin->lch =NULL; } else if (key> root->k) { if (!root->rch) break; যদি (কী> রুট->আরচ->কে) { রুট =LL_Rotate(root); যদি (!root->rch) ভেঙ্গে যায়; } LeftTreeMax->rch=root; LeftTreeMax =LeftTreeMax->rch; root =root->rch; LeftTreeMax->rch =NULL; } অন্যথা বিরতি; } LeftTreeMax→rch =root->lch; RightTreeMin→lch =root->rch; root->lch =header.rch; root->rch =header.lch; রিটার্ন রুট; } s* New_Node(int key) { s* p_node =new s; যদি (!p_node) { fprintf(stderr, "আউট অফ মেমরি!\n"); প্রস্থান (1); } p_node->k =কী; p_node->lch =p_node->rch =NULL; রিটার্ন 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 =কী; যদি (!root) { root =p_node; p_node =NULL; রিটার্ন রুট; } root =Splay(কী, root); যদি (কী k) { p_node->lch=root->lch; p_node->rch =root; root->lch =NULL; root =p_node; } অন্যথায় যদি (কী> রুট->কে) { p_node->rch =root->rch; p_node->lch =root; root->rch =NULL; root =p_node; } else রিটার্ন রুট; p_node =NULL; রিটার্ন রুট; } s* Delete(int key, s* root)//মোছা নোড { s* temp; যদি (! root)// যদি গাছ খালি থাকে তাহলে NULL রিটার্ন করুন; root =Splay(কী, root); যদি (কী!=রুট->কে)//যদি গাছের একটি আইটেম রিটার্ন রুট থাকে; else { if (!root->lch) { temp =root; root =root->rch; } else { temp =root; root =Splay(কী, root->lch); root->rch =temp->rch; } বিনামূল্যে (তাপ); রিটার্ন রুট; } } s* অনুসন্ধান (int কী, s* রুট)//সেরাচিং { রিটার্ন স্প্লে(কী, রুট); } void InOrder(s* root)//inorder traversal { if (root) { InOrder(root->lch); cout<<"কী:" <k; if(root->lch) cout<<" | বাম সন্তান:"<lch->k; if(root->rch) cout <<" | ডান সন্তান:" <rch->k; cout<<"\n"; InOrder(root->rch); } }};int main(){ SplayTree st; s *মূল; root =NULL; st.InOrder(root); int i, c; while(1) { cout<<"1. ঢোকান "<>c; সুইচ ©// সুইচ অপারেশন সম্পাদন করুন { কেস 1:cout<<" সন্নিবেশ করার মান লিখুন:"; cin>>i; root =st.Insert(i, root); cout<<"\n সন্নিবেশ করার পর:"<>i; root =st.Delete(i, root); cout<<"\nমোছার পর:"<>i; root =st.Search(i, root); cout<<"\nঅনুসন্ধানের পর "< 
আউটপুট
 <পূর্ব>1. সন্নিবেশ 2. মুছে ফেলুন3. অনুসন্ধান4. প্রস্থান করুন আপনার পছন্দটি লিখুন:1 সন্নিবেশ করার মান লিখুন:7 সন্নিবেশ করার পরে:7key:71. সন্নিবেশ২। মুছে ফেলুন3. অনুসন্ধান4. প্রস্থান করুন আপনার পছন্দ লিখুন:1 সন্নিবেশ করা হবে মান লিখুন:6 সন্নিবেশ করার পর:6key:6 | ডান শিশু:7key:71. Insert2. মুছে ফেলুন3. অনুসন্ধান4. প্রস্থান করুন আপনার পছন্দ লিখুন:1 সন্নিবেশ করা হবে মান লিখুন:4 সন্নিবেশ করার পর:4key:4 | ডান শিশু:6key:6 | ডান শিশু:7key:71. Insert2. মুছে ফেলুন3. অনুসন্ধান4. প্রস্থান করুন আপনার পছন্দটি লিখুন:1 সন্নিবেশ করার মান লিখুন:5 সন্নিবেশ করার পর:5key:4key:5 | বাম সন্তান:4 | ডান শিশু:6key:6 | ডান শিশু:7key:71. Insert2. মুছে ফেলুন3. অনুসন্ধান4. প্রস্থান করুন আপনার পছন্দটি লিখুন:1 সন্নিবেশ করার মান লিখুন:3 সন্নিবেশ করার পর:3key:3 | ডান শিশু:4key:4 | ডান শিশু:5key:5 | ডান শিশু:6key:6 | ডান শিশু:7key:71. Insert2. মুছে ফেলুন3. অনুসন্ধান4. প্রস্থান করুন আপনার পছন্দ লিখুন:1 সন্নিবেশ করা হবে মান লিখুন:2 সন্নিবেশ করার পর:2key:2 | ডান সন্তান:3key:3 | ডান শিশু:4key:4 | ডান শিশু:5key:5 | ডান শিশু:6key:6 | ডান শিশু:7key:71. Insert2. মুছে ফেলুন3. অনুসন্ধান4. প্রস্থান করুন আপনার পছন্দটি লিখুন:3 অনুসন্ধান করার জন্য মান লিখুন:2 পরে অনুসন্ধান করুন 2কী:2 | ডান সন্তান:3key:3 | ডান শিশু:4key:4 | ডান শিশু:5key:5 | ডান শিশু:6key:6 | ডান শিশু:7key:71. Insert2. মুছে ফেলুন3. অনুসন্ধান4. প্রস্থান করুন আপনার পছন্দটি লিখুন:2 মুছে ফেলার মান লিখুন:3 মুছে ফেলার পরে:3key:2 | ডান শিশু:4key:4 | ডান শিশু:5key:5 | ডান শিশু:6key:6 | ডান শিশু:7key:71. Insert2. মুছে ফেলুন3. অনুসন্ধান4. আপনার পছন্দের প্রস্থান করুন:4