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

จากวิกิพีเดีย สารานุกรมเสรี
ภาพตัวอย่างของต้นไม้ที่ไม่สมดุล
ภาพต้นไม้เดียวกับภาพด้านบนแต่ปรับสมดุลแล้ว

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

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

ภาพรวม[แก้]

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

ดังนั้น :

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

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

การนำมาใช้งาน[แก้]

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

อ้างอิง[แก้]

  1. 1.0 1.1 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.
  2. Sleator, Daniel D.; Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees", Journal of the ACM (Association for Computing Machinery) 32 (3): 652–686, doi:10.1145/3828.3835 

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

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