โปรแกรม C++ เพื่อใช้งาน Splay Tree

นี่คือโปรแกรม C++ เพื่อใช้ Splay Tree

คำอธิบายคลาส:

เริ่มคลาส SplayTree มีฟังก์ชัน:สร้างฟังก์ชัน Splay() เพื่อใช้งาน splay tree จากบนลงล่าง ที่นี่ head.rch ชี้ไปที่ต้นไม้ด้านซ้าย และ head.lch ชี้ไปที่ต้นไม้ด้านขวา สร้างลิงค์ไปยังทรีขวา สร้างลิงค์ไปยังต้นไม้ด้านซ้าย ประกอบต้นไม้ซ้ายกลางและขวา สร้างฟังก์ชัน Insert() เพื่อแทรกโหนดลงในทรี ถ้า root->k>=คีย์ทั้งหมดจะเป็น root→lch Else ถ้า root->k <=all keys จะเป็น root→rch Else Return root.End

คำอธิบายคลาสและรหัสเทียม:

เริ่มต้น สร้างโครงสร้างเพื่อประกาศตัวแปร k และ lch ตัวชี้ลูกด้านซ้าย และ rch ตัวชี้ลูกด้านขวา สร้างคลาส SplayTree :สร้างฟังก์ชัน RR_Rotate เพื่อหมุนไปทางขวา สร้างฟังก์ชัน LL_Rotate เพื่อหมุนไปทางซ้าย สร้างฟังก์ชัน Splay เพื่อใช้งานแผนผังจากบนลงล่าง ที่นี่ head.rch ชี้ไปที่ต้นไม้ด้านซ้าย และ head.lch ชี้ไปที่ต้นไม้ด้านขวา สร้างลิงค์ไปยังทรีขวา สร้างลิงค์ไปยังต้นไม้ด้านซ้าย ประกอบต้นไม้ซ้ายกลางและขวา สร้างฟังก์ชัน New_Node() เพื่อสร้างโหนดในแผนผัง สร้างฟังก์ชัน Insert() เพื่อแทรกโหนดลงในทรี ถ้า root→k>=คีย์ทั้งหมดจะเป็น root→lch Else ถ้า root->k>=all คีย์จะเป็น root→rch Else Return root สร้างฟังก์ชัน Delete() เพื่อลบโหนดออกจากทรี สร้างฟังก์ชัน Search() เพื่อค้นหาโหนดในแผนผัง สร้างฟังก์ชัน InOrder() สำหรับการข้ามผ่าน InOrder ของทรี สร้างฟังก์ชัน main() และเรียกใช้ฟังก์ชันแบบเลือกตามตัวเลือกสิ้นสุด

โค้ดตัวอย่าง

#include #include #include ใช้เนมสเปซ std;struct s//node ประกาศ{ 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; ส่วนหัวของ; header.lch=header.rch =NULL; s* LeftTreeMax =&ส่วนหัว; s* RightTreeMin =&header; ในขณะที่ (1) { if (คีย์ k) { if (!root->lch) แตก; ถ้า (คีย์ lch->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) แตก; ถ้า (คีย์> root->rch->k) { root =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) { s* p_node =ใหม่ s; if (!p_node) { fprintf(stderr, "หน่วยความจำไม่เพียงพอ!\n"); ทางออก(1); } p_node->k =คีย์; p_node->lch =p_node->rch =NULL; ส่งคืน p_node; } s* แทรก (คีย์ int, s* root) { สแตติก s* p_node =NULL; ถ้า (!p_node) p_node =New_Node (คีย์); อื่น p_node->k =คีย์; ถ้า (!root) { root =p_node; p_node =NULL; ส่งคืนรูต; } root =Splay (คีย์, รูท); ถ้า (คีย์ k) { p_node->lch=root->lch; p_node->rch =รูท; root->lch =NULL; รูท =p_node; } else if (คีย์> root->k) { p_node->rch =root->rch; p_node->lch =รูท; root->rch =NULL; รูท =p_node; } อื่นส่งคืนรูท; p_node =NULL; ส่งคืนรูต; } s* Delete (คีย์ int, s* root)//delete node { s* temp; if (!root)// ถ้าต้นไม้ว่างเปล่าให้คืนค่า NULL; รูท =Splay (คีย์, รูท); if (key !=root->k)//if tree มีหนึ่งรายการส่งคืน root; อื่น { if (!root->lch) { temp =root; root =root->rch; } อื่น ๆ { ชั่วคราว =รูท; รูท =Splay(คีย์, รูท->lch); root->rch =temp->rch; } ฟรี (ชั่วคราว); ส่งคืนรูต; } } s* ค้นหา (คีย์ int, รูท s*)//การค้นหา { return Splay (คีย์, รูท); } เป็นโมฆะ InOrder(s* root)//inorder traversal { if (root) { InOrder(root->lch); cout<<"คีย์:" <k; if(root->lch) cout<<" | ลูกซ้าย:"<lch->k; if(root->rch) cout <<" | right child:" <rch->k; ศาล<<"\n"; InOrder(root->rch); } }};int main(){ SplayTree st; s *ราก; รูท =NULL; st.InOrder(ราก); int ฉัน c; ในขณะที่(1) { cout<<"1. แทรก "<>ค; สวิตซ์©//ดำเนินการสวิตซ์ { กรณีที่ 1:cout<<"ป้อนค่าที่จะแทรก:"; ซิน>>ผม; root =st.Insert(i, root); cout<<"\nหลังจากแทรก:"<>ผม; รูท =st.Delete(i, รูท); cout<<"\nหลังจากลบ:"<>ผม; root =st.Search(i, root); cout<<"\nหลังจากค้นหา "< 
ผลลัพธ์
 <ก่อน>1. แทรก2. ลบ3. ค้นหา4. ออกป้อนตัวเลือกของคุณ:1ป้อนค่าที่จะแทรก:7หลังจากแทรก:7คีย์:71. แทรก2. ลบ3. ค้นหา4. ออกป้อนตัวเลือกของคุณ:1ป้อนค่าที่จะแทรก:6หลังจากแทรก:6คีย์:6 | ลูกขวา:7key:71. แทรก2. ลบ3. ค้นหา4. ออกป้อนตัวเลือกของคุณ:1ป้อนค่าที่จะแทรก:4หลังจากแทรก:4คีย์:4 | ลูกขวา:6คีย์:6 | ลูกขวา:7key:71. แทรก2. ลบ3. ค้นหา4. ออกป้อนตัวเลือกของคุณ:1ป้อนค่าที่จะแทรก:5หลังจากแทรก:5คีย์:4คีย์:5 | ลูกซ้าย:4 | ลูกขวา:6คีย์:6 | ลูกขวา:7key:71. แทรก2. ลบ3. ค้นหา4. ออกป้อนตัวเลือกของคุณ:1ป้อนค่าที่จะแทรก:3หลังจากแทรก:3คีย์:3 | ลูกขวา:4key:4 | ลูกที่ถูกต้อง:5key:5 | ลูกขวา:6คีย์:6 | ลูกขวา:7key:71. แทรก2. ลบ3. ค้นหา4. ออกป้อนตัวเลือกของคุณ:1ป้อนค่าที่จะแทรก:2หลังจากแทรก:2คีย์:2 | ลูกขวา:3key:3 | ลูกขวา:4key:4 | ลูกที่ถูกต้อง:5key:5 | ลูกขวา:6คีย์:6 | ลูกขวา:7key:71. แทรก2. ลบ3. ค้นหา4. ออกป้อนตัวเลือกของคุณ:3ป้อนค่าที่จะค้นหา:2หลังจากค้นหา 2คีย์:2 | ลูกขวา:3key:3 | ลูกขวา:4key:4 | ลูกที่ถูกต้อง:5key:5 | ลูกขวา:6คีย์:6 | ลูกขวา:7key:71. แทรก2. ลบ3. ค้นหา4. ออก ป้อนตัวเลือกของคุณ:2ป้อนค่าที่จะลบ:3หลังจากลบ:3คีย์:2 | ลูกขวา:4key:4 | ลูกที่ถูกต้อง:5key:5 | ลูกขวา:6คีย์:6 | ลูกขวา:7key:71. แทรก2. ลบ3. ค้นหา4. ออก ป้อนตัวเลือกของคุณ:4