เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
|
ป้ายระบุ: แก้ไขจากอุปกรณ์เคลื่อนที่ แก้ไขจากเว็บสำหรับอุปกรณ์เคลื่อนที่ |
|
{{ต้องการอ้างอิง}}
{{กล่องข้อมูล โครงสร้างข้อมูล
| ชื่อ = ต้นไม้สเปลย์
| ภาพ =
| description =
| order = เรียงจากน้อยไปมาก
| same = ไม่อนุญาตให้ซ้ำ
| findi = -
| finde = O (log n) (โดยถัวเฉลี่ย)
| access = O (log n) (โดยถัวเฉลี่ย)
| empty = ทำให้รากเป็น null
| emptytime = O (1)
| parent = ต้นไม้ค้นหาแบบทวิภาค
| children = -
}}
'''ต้นไม้สเปลย์'''<ref>สมชาย ประสิทธิ์จูตระกูล, การออกแบบและวิเคราะห์อัลกอริทึม, พิมพ์ครั้งที่ 4</ref> ({{lang-en|Splay tree}}) เป็น[[ต้นไม้ค้นหาแบบทวิภาค]]ที่มีโครงสร้างปรับตัวเอง (self-adjusting tree) ได้คือ สามารถปรับโครงสร้างทุกครั้งที่เรียกใช้บริการ ตั้งแต่การเพิ่ม การลบ หรือแม้กระทั่งการค้นหาเอง โดยจะนำปมต้นไม้ที่ถูกใช้บริการขึ้นมาเป็นรากแทน สำหรับต้นไม้สเปลย์ ถูกคิดค้นขึ้นโดย Daniel Sleator และ Robert Tarjan
== ลักษณะของ splay tree ==
splay tree เป็นต้นไม้ที่มีลักษณะเด่นที่ปรับโครงสร้างทุกครั้งที่เรียกใช้บริการตั้งแต่การเพิ่ม ลบ หรือแม้แต่ค้นหา โดยนอกจากที่จะนำปมต้นไม้ที่ถูกใช้บริการขึ้นมาเป็นรากแล้ว ตัวโครงสร้างต้นไม้เมื่อถูกใช้บริการมากขึ้นเรื่อยๆ จะค่อยปรับสู่ต้นไม้ที่มีลักษณะเตี้ยและแผ่ขยายออกได้ (splay) จึงเป็นที่มาของชื่อต้นไม้ว่าต้นไม้สเปลย์
|
