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

**ต้นไม้สเปลย์** () เป็นต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับตัวเอง (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** เป็นหมุนปมตามปกติให้ลูกขึ้นมา

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

## อ้างอิง

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

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