ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้

ในวิทยาการคอมพิวเตอร์ ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ (อังกฤษ: self-balancing binary search tree) คือต้นไม้ค้นหาแบบทวิภาคที่สามารถรักษาความสูง (จำนวนชั้นที่อยู่ต่ำกว่าราก) ของตนให้เตี้ยอยู่ตลอดเวลา เพื่อทำให้การค้นหาข้อมูล การใส่ข้อมูล การลบข้อมูลในต้นไม้ทำได้อย่างมีประสิทธิภาพอยู่เสมอ แม้จะมีต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้บางแบบ เช่นต้นไม้สเปลย์ ซึ่งไม่ได้ปรับให้ต้นไม้เตี้ยตลอดเวลาแต่ประสิทธิภาพเมื่อวิเคราะห์แบบถัวเฉลี่ยได้ประสิทธิภาพเท่ากัน

ภาพตัวอย่างของต้นไม้ที่ไม่สมดุล

ภาพต้นไม้เดียวกับภาพด้านบนแต่ปรับสมดุลแล้ว

โครงสร้างข้อมูลที่นิยมในการอิมพลีเมนต์ต้นไม้ลักษณะนี้ยกตัวอย่างเช่น , ต้นไม้แดงดำ, ต้นไม้สเปลย์ เป็นต้น

ภาพรวม

การดำเนิการกับต้นไม้ค้นหาแบบทวิภาคส่วนใหญ่ไม่ว่าจะเป็นการค้นหาข้อมูล การใส่ข้อมูล การลบข้อมูล ประสิทธิภาพของการดำเนินการนั้นล้วนขั้นอยู่กับความสูงของต้นไม้ ดังนั้นการรักษาให้ต้นไม้นั้นมีประสิทธิภาพในการดำเนินการดี นั่นคือการลดความสูงของต้นไม้ลงเท่าที่จะทำได้ โดยต้นไม้ทวิภาคที่มีความสูง h จะมีปมได้ไม่เกิน 2⁰+2¹+···+2^h = 2^h+1-1 ปม หากต้นไม้มี n ปม และมีความสูง h จะได้ว่า:

${\displaystyle 2^{h+1}-1\geq n}$

ดังนั้น :

${\displaystyle h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor }$

นั่นคือ อย่างน้อยที่สุดความสูงของต้นไม้ทวิภาคที่มี n ปม คือ ฟังก์ชันพื้นของ log₂ (n)

แต่หากไม่มีการปรับสมดุลของต้นไม้ค้นหาแบบทวิภาคแล้ว จะมีบางกรณีที่ทำให้ความสูงของต้นไม้มีค่าเท่ากับจำนวนปม ยกตัวอย่างเช่นหากใส่ข้อมูลที่ผ่านการเรียงลำดับเข้าไปในต้นไม้แล้ว ลักษณะของต้นไม้จะดูเหมือนกับรายการโยงที่มี n ปมเสียมากกว่า ในเชิงเปรียบเทียบหาก n = 1,000,000 ต้นไม้ค้นหาแบบทวิภาคที่ไม่ได้ปรับสมดุลอาจมีความสูงถึง 1,000,000 เปรียบเทียบกับต้นไม้ค้นหาแบบทวิภาคที่ปรับสมดุลเพื่อลดความสูงแล้วนั้นจะมีความสูงไม่เกิน ${\displaystyle \lfloor \log _{2}(n)\rfloor =19}$

การนำมาใช้งาน

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

อ้างอิง

1. Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. . Section 6.2.3: Balanced Trees, pp.458-481.
2. Sleator, Daniel D.; Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees" (PDF), Journal of the ACM (Association for Computing Machinery), 32 (3): 652–686, doi:10.1145/3828.3835

ดูเพิ่ม

• ต้นไม้ค้นหาแบบทวิภาค

แหล่งข้อมูลอื่น

• Dictionary of Algorithms and Data Structures: Height-balanced binary search tree
• GNU libavl, a LGPL-licensed library of binary tree implementations in C, with documentation