กระจายต้นไม้ในโครงสร้างข้อมูล

play tree ถูกกำหนดให้เป็นแผนผังการค้นหาแบบไบนารีที่สมดุลในตัวเองพร้อมคุณสมบัติพิเศษที่องค์ประกอบที่เข้าถึงล่าสุดสามารถเข้าถึงได้อย่างรวดเร็วอีกครั้ง การดำเนินการพื้นฐาน เช่น การแทรก การค้นหา และการนำออกจะดำเนินการโดย splay tree ในเวลาตัดจำหน่าย O(log n) สำหรับการดำเนินการที่ไม่ใช่แบบสุ่มหลายๆ ลำดับ แผนผังต้นไม้ทำงานได้ดีกว่าแผนผังการค้นหาอื่นๆ แม้ว่าจะไม่ทราบรูปแบบเฉพาะของลำดับก็ตาม การดำเนินการปกติทั้งหมดบนทรีการค้นหาแบบไบนารีจะรวมเข้ากับการดำเนินการพื้นฐานเดียวที่เรียกว่า splaying

สมมติว่าสำหรับแต่ละโหนด a เราเก็บคีย์จำนวนจริง (a)

ในทรีค้นหาไบนารีซ้ายทรีย่อยของโหนดใด ๆ มีรายการที่มีค่า "คีย์" น้อยกว่าค่าของคีย์ (a) และทรีย่อยด้านขวาของโหนด a มีรายการที่มีค่า "คีย์" สูงกว่าค่าของคีย์ (a) .

ในแผนผังต้นไม้ เราจะค้นหารายการข้อความค้นหาก่อน เช่น a ในแผนผังการค้นหาแบบไบนารีปกติ— เปรียบเทียบรายการข้อความค้นหากับค่าในรูท ถ้าน้อยกว่านั้น ให้ค้นหาซ้ำในทรีย่อยด้านซ้าย ถ้าสูงกว่านั้น ให้ค้นหาซ้ำใน ทรีย่อยด้านขวา และถ้ามันเท่ากัน เราก็ทำเสร็จแล้ว จากนั้น พูดอย่างไม่เป็นทางการ เราจะดูบรรพบุรุษที่ต่อเนื่องกันทุกคู่ f a พูด b =parent(a) และ c =parent(b) และหมุนคู่ให้สำเร็จ ผลจากการหมุนเวียนเหล่านี้ a มาแทนที่ c.

ในกรณีที่ a มีบรรพบุรุษที่เหมาะสมเป็นจำนวนคี่ บรรพบุรุษของ a (ซึ่งเป็นลูกของราก) จะต้องได้รับการจัดการแยกกัน ในกรณีของเทอร์มินัล— เราจะหมุนขอบระหว่าง a และราก ขั้นตอนนี้แสดงเป็นขั้นตอนซิกแซก

หาก a และ b เป็นทั้งลูกทางซ้ายหรือทั้งสองลูกที่ถูกต้องของผู้ปกครองตามลำดับ ก่อนอื่นเราจะหมุนขอบระหว่าง b และพาเรนต์ c จากนั้นจึงเปลี่ยนขอบระหว่าง a และพาเรนต์ b ขั้นตอนนี้แสดงเป็นขั้นตอนซิกซิก

หาก a เป็นเด็กซ้าย (ตามลำดับขวา) และ b เป็นเด็กขวา (ตามลำดับซ้าย) ก่อนอื่นเราจะหมุนขอบระหว่าง a และ b จากนั้นระหว่าง a และ c ขั้นตอนนี้จะแสดงเป็นขั้นตอนซิกแซก