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

ในวิทยาการคอมพิวเตอร์ ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ () คือต้นไม้ค้นหาแบบทวิภาคที่สามารถรักษาความสูง (จำนวนชั้นที่อยู่ต่ำกว่าราก) ของตนให้เตี้ยอยู่ตลอดเวลาDonald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458-481. เพื่อทำให้การค้นหาข้อมูล การใส่ข้อมูล การลบข้อมูลในต้นไม้ทำได้อย่างมีประสิทธิภาพอยู่เสมอ แม้จะมีต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้บางแบบ เช่นต้นไม้สเปลย์ ซึ่งไม่ได้ปรับให้ต้นไม้เตี้ยตลอดเวลาแต่ประสิทธิภาพเมื่อวิเคราะห์แบบถัวเฉลี่ยได้ประสิทธิภาพเท่ากัน

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

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

ดังนั้น :

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

แต่หากไม่มีการปรับสมดุลของต้นไม้ค้นหาแบบทวิภาคแล้ว จะมีบางกรณีที่ทำให้ความสูงของต้นไม้มีค่าเท่ากับจำนวนปม ยกตัวอย่างเช่นหากใส่ข้อมูลที่ผ่านการเรียงลำดับเข้าไปในต้นไม้แล้ว ลักษณะของต้นไม้จะดูเหมือนกับรายการโยงที่มี n ปมเสียมากกว่า ในเชิงเปรียบเทียบหาก n = 1,000,000 ต้นไม้ค้นหาแบบทวิภาคที่ไม่ได้ปรับสมดุลอาจมีความสูงถึง 1,000,000 เปรียบเทียบกับต้นไม้ค้นหาแบบทวิภาคที่ปรับสมดุลเพื่อลดความสูงแล้วนั้นจะมีความสูงไม่เกิน 

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

 อ้างอิง 

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

 แหล่งข้อมูลอื่น 
 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

หมวดหมู่:ต้นไม้ (โครงสร้างข้อมูล)
หมวดหมู่:ต้นไม้แบบทวิภาค