ต้นไม้บาน

จากวิกิพีเดีย สารานุกรมเสรี

ต้นไม้บาน (SplayTree)
ความสำคัญของลำดับ	เรียงจากน้อยไปมาก
การซ้ำกันของสมาชิก	ไม่อนุญาตให้ซ้ำ
เวลาที่ใช้ค้นหาตามดัชนี	-
เวลาที่ใช้ค้นหาตามค่า	O (log n) (โดยถัวเฉลี่ย)
เวลาที่ใช้ในการเข้าถึง	O (log n) (โดยถัวเฉลี่ย)
การทำให้ว่าง	ทำให้รากเป็น null
เวลาที่ใช้ทำให้ว่าง	O (1)
โครงสร้างต้นแบบ	ต้นไม้ค้นหาแบบทวิภาค
โครงสร้างที่นำไปใช้	-

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

เนื้อหา 1 ลักษณะของต้นไม้บาน 2 จุดเด่นของต้นไม้บาน 3 บริการที่มักจะมี 4 ความเร็วที่ใช้ในการทำงาน 5 ประเภทข้อมูลที่ใช้สร้างต้นไม้บาน 6 การสร้างบริการของต้นไม้บาน 6.1 splay 6.2 ข้อแม้เกี่ยวกับการลบ 7 ดูเพิ่ม

[แก้] ลักษณะของต้นไม้บาน

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

[แก้] จุดเด่นของต้นไม้บาน

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

[แก้] บริการที่มักจะมี

• การเพิ่ม การลบ การค้นหา

[แก้] ความเร็วที่ใช้ในการทำงาน

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

[แก้] ประเภทข้อมูลที่ใช้สร้างต้นไม้บาน

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

[แก้] การสร้างบริการของต้นไม้บาน

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

[แก้] splay

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

1. zig-zig เป็นความสัมพันธ์แบบปู่-พ่อ-หลาน มีแนวเดียวกัน (ซ้าย-ซ้าย หรือ ขวา-ขวา)
2. zig-zag เป็นความสัมพันธ์แบบปู่-พ่อ-หลาน มีแนวต่างกัน (ซ้าย-ขวา หรือ ขวา-ซ้าย)
3. zig เป็นความสัมพันธ์แบบ พ่อ-ลูก (เป็นเศษในระดับเลขคี่ตอนสุดท้าย)

ซึ่งการจัดการหมุนปมนั้นจะแตกต่างกันขึ้นอยู่กับรูปแบบการไหลนั้นคือ

1. zig-zig จะต้องหมุนปมพ่อก่อนแล้วจึงหมุนปมหลาน
2. zig-zag จะหมุนปมหลานสองที
3. zig เป็นหมุนปมตามปกติให้ลูกขึ้นมา

รูปแบบ	รูปภาพการหมุน
zig-zig
zig-zag
zig

[แก้] ข้อแม้เกี่ยวกับการลบ

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

[แก้] ดูเพิ่ม

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