เมนูนำทาง
ต้นไม้สเปลย์ การสร้างบริการของต้นไม้สเปลย์สำหรับการเพิ่มและการลบนั้น splay treeจะสร้างบริการไม่แตกต่างจากต้นไม้ค้นหาแบบทวิภาค เพียงแต่หลังจากทำบริการต่างๆนั้นแล้วเราจะต้องหมุนปมเพื่อให้ปมที่เพิ่งใช้บริการเสร็จขึ้นไปเป็นราก กระบวนการนี้เราเรียกว่า splay
การหมุนปมขึ้นไปเป็นรากนั้นทำได้ ต้องเก็บรูปแบบ (pattern) ความสัมพันธ์ของปมต่างๆจากตัวของรากจนถึงปมที่จะเพิ่งใช้บริการโดยรูปแบบ ที่ต้องเก็บไว้มีสามวิธีคือ
ซึ่งการจัดการหมุนปมนั้นจะแตกต่างกันขึ้นอยู่กับรูปแบบการไหลนั้นคือ
รูปแบบ | รูปภาพการหมุน |
---|---|
zig-zig | |
zig-zag | |
zig |
สำหรับการลบนั้นจะแตกต่างจากการลบในต้นไม้ค้นหาแบบทวิภาคทั่วไปสักเล็กน้อย คือต้อง splay ปมที่จะลบขึ้นมาเป็นรากก่อน จำตำแหน่งของต้นไม้ย่อยด้านซ้ายและต้นไม้ย่อยด้านขวาของรากไว้ และทำรากให้เป็น null ต้นไม้จะขาดสองท่อน หลังจากนี้มีวิธีทำสองแบบคือจากต้นไม้ย่อยด้านขวา ให้ค้นหาปมที่น้อยสุด (ซึ่งอยู่ซ้ายสุด) ปมนั้นจะขึ้นมาเป็นรากของต้นไม้ด้านขวาแทนด้วยการ splay เนื่องจากเป็นปมที่น้อยที่สุดจึงไม่มีต้นไม้ย่อยด้านซ้าย ก็นำต้นไม้ย่อยทางด้านซ้ายของรากที่ถูกลบไปแล้วที่เราเก็บตำแหน่งไว้มาต่อแทน หรือจะทำในทางกลับกันคือจากต้นไม้ย่อยด้านซ้าย ให้ค้นหาปมที่น้อยสุด (ซึ่งอยู่ขวาสุด) ปมนั้นจะขึ้นมาเป็นรากของต้นไม้ด้านซ้ายแทนด้วยการ splay เนื่องจากเป็นปมที่มากที่สุดจึงไม่มีต้นไม้ย่อยด้านขวาก็นำต้นไม้ย่อยทางด้านขวาของรากที่ถูกลบไปแล้ว ที่เราเก็บตำแหน่งไว้มาต่อแทน ก็จะได้ splay tree ที่ลบสมาชิกตัวนั้นออกนั้นเอง
เมนูนำทาง
ต้นไม้สเปลย์ การสร้างบริการของต้นไม้สเปลย์ใกล้เคียง
ต้นไม้ตัดสินใจ ต้นไม้ของพ่อ ต้นไม้แบบที ต้นไม้แห่งการรู้ถึงความดีและความชั่ว ต้นไม้ (ทฤษฎีกราฟ) ต้นไม้เงินต้นไม้ทอง ต้นไม้ (โครงสร้างข้อมูล) ต้นไม้สเปลย์ ต้นไม้แดงดำ ต้นไม้ 2–3–4แหล่งที่มา
WikiPedia: ต้นไม้สเปลย์