ต้นไม้สเปลย์

ต้นไม้สเปลย์สมชาย ประสิทธิ์จูตระกูล, การออกแบบและวิเคราะห์อัลกอริทึม, พิมพ์ครั้งที่ 4 () เป็นต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับตัวเอง (self-adjusting tree) ได้คือ สามารถปรับโครงสร้างทุกครั้งที่เรียกใช้บริการ ตั้งแต่การเพิ่ม การลบ หรือแม้กระทั่งการค้นหาเอง โดยจะนำปมต้นไม้ที่ถูกใช้บริการขึ้นมาเป็นรากแทน สำหรับต้นไม้สเปลย์ ถูกคิดค้นขึ้นโดย Daniel Sleator และ Robert Tarjan

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

 จุดเด่นของ splay tree 
จุดเด่นของต้นไม้สเปลย์ที่ชัดเจนคือการปรับให้ปมที่เพิ่งถูกใช้บริการขึ้นมาเป็นราก แม้กระทั่งบริการการค้น ซึ่งทำให้การค้นหาข้อมูลที่เพิ่งค้นไปใหม่ๆ นั้นรวดเร็วขึ้น ซึ่งตั้งสมมติฐานที่ว่า  ธรรมชาติของการค้นข้อมูลโดยทั่วไป ข้อมูลที่ถูกค้นไม่ได้มีความถี่การค้นเท่ากันหมด แต่ข้อมูลใดที่ถูกค้นเยอะๆ ก็จะมีโอกาสถูกค้นบ่อยๆด้วย ดังนั้นการทำให้ข้อมูลที่ค้นบ่อยๆไปอยู่ตำแหน่งบนๆ ของ splay tree ก็จะทำให้การค้นในอนาคตรวดเร็วมากขึ้น

 บริการที่มักจะมี 
 การเพิ่ม การลบ การค้นหา

 ความเร็วที่ใช้ในการทำงาน 
ความเร็วที่ใช้ในการทำงานขึ้นอยู่กับว่าข้อมูลที่จะค้นหานั้น ถูกใช้บ่อยหรือไม่ ถ้าถูกใช้บ่อยจะค้นหาได้อย่างรวดเร็ว ถึงอย่างไรก็ดี เนื่องจากต้นไม้ถูกทำให้ค่อนข้างเตี้ย การเข้าถึงข้อมูลโดยถัวเฉลี่ยเมื่อใช้บริการนานๆและข้อมูลหลายๆตัวไม่ซ้ำกัน จะใช้เวลาโดยถัวเฉลี่ยเป็น O(log n)

 ประเภทข้อมูลที่ใช้สร้างต้นไม้สเปลย์ 
ปมของ splay treeนั้นจะไม่แตกต่างจากปมของต้นไม้ค้นหาทวิภาคแบบปกติเลย นี่เป็นจุดเด่นอีกอย่างหนึ่งของ splay tree ซึ่งไม่ต้องใช้การเก็บข้อมูลเสริมในปม ในการจัดการกับการช่วยประกันความเร็วของการบริการ แต่ตัวต้นไม้นอกจากที่จะต้องเก็บรากแล้ว ยังต้องเก็บการจัดเรียงตัวเพื่อใช้ในการหมุนปมด้วย

 การสร้างบริการของต้นไม้สเปลย์ 
สำหรับการเพิ่มและการลบนั้น  splay treeจะสร้างบริการไม่แตกต่างจากต้นไม้ค้นหาแบบทวิภาค เพียงแต่หลังจากทำบริการต่างๆนั้นแล้วเราจะต้องหมุนปมเพื่อให้ปมที่เพิ่งใช้บริการเสร็จขึ้นไปเป็นราก กระบวนการนี้เราเรียกว่า splay

 splay 
การหมุนปมขึ้นไปเป็นรากนั้นทำได้ ต้องเก็บรูปแบบ (pattern) ความสัมพันธ์ของปมต่างๆจากตัวของรากจนถึงปมที่จะเพิ่งใช้บริการโดยรูปแบบ ที่ต้องเก็บไว้มีสามวิธีคือ
 zig-zig เป็นความสัมพันธ์แบบปู่-พ่อ-หลาน มีแนวเดียวกัน (ซ้าย-ซ้าย หรือ ขวา-ขวา) 
 zig-zag เป็นความสัมพันธ์แบบปู่-พ่อ-หลาน มีแนวต่างกัน  (ซ้าย-ขวา หรือ ขวา-ซ้าย)
 zig เป็นความสัมพันธ์แบบ พ่อ-ลูก (เป็นเศษในระดับเลขคี่ตอนสุดท้าย)

ซึ่งการจัดการหมุนปมนั้นจะแตกต่างกันขึ้นอยู่กับรูปแบบการไหลนั้นคือ
 zig-zig จะต้องหมุนปมพ่อก่อนแล้วจึงหมุนปมหลาน
 zig-zag จะหมุนปมหลานสองที
 zig เป็นหมุนปมตามปกติให้ลูกขึ้นมา

รูปแบบรูปภาพการหมุนzig-zigไฟล์:Zigzig.gifzig-zagไฟล์:Zigzag.gifzigไฟล์:splay_tree_zig.svg

 ข้อแม้เกี่ยวกับการลบ 
สำหรับการลบนั้นจะแตกต่างจากการลบในต้นไม้ค้นหาแบบทวิภาคทั่วไปสักเล็กน้อย คือต้อง splay ปมที่จะลบขึ้นมาเป็นรากก่อน จำตำแหน่งของต้นไม้ย่อยด้านซ้ายและ
ต้นไม้ย่อยด้านขวาของรากไว้ และทำรากให้เป็น null ต้นไม้จะขาดสองท่อน หลังจากนี้มีวิธีทำสองแบบคือจากต้นไม้ย่อยด้านขวา ให้ค้นหาปมที่น้อยสุด (ซึ่งอยู่ซ้ายสุด) ปมนั้นจะขึ้นมาเป็นรากของต้นไม้ด้านขวาแทนด้วยการ splay เนื่องจากเป็นปมที่น้อยที่สุดจึงไม่มีต้นไม้ย่อยด้านซ้าย ก็นำต้นไม้ย่อยทางด้านซ้ายของรากที่ถูกลบไปแล้วที่เราเก็บตำแหน่งไว้มาต่อแทน หรือจะทำในทางกลับกันคือ
จากต้นไม้ย่อยด้านซ้าย ให้ค้นหาปมที่น้อยสุด (ซึ่งอยู่ขวาสุด) ปมนั้นจะขึ้นมาเป็นรากของต้นไม้ด้านซ้ายแทนด้วยการ splay เนื่องจากเป็นปมที่มากที่สุดจึงไม่มีต้นไม้ย่อยด้านขวาก็นำต้นไม้ย่อยทางด้านขวาของรากที่ถูกลบไปแล้ว ที่เราเก็บตำแหน่งไว้มาต่อแทน ก็จะได้ splay tree ที่ลบสมาชิกตัวนั้นออกนั้นเอง

 อ้างอิง 

 ดูเพิ่ม 
 ต้นไม้เอวีแอล
 ทรีพ
 ต้นไม้แดงดำ

หมวดหมู่:ต้นไม้แบบทวิภาค