ต้นไม้เอวีแอล

จากลักษณะของต้นไม้ค้นหาแบบทวิภาคที่ได้นำเสนอมา ซึ่งมีประสิทธิภาพการทำงานเชิงเวลาของบริการต่าง ๆ ทั้งการค้นหา เพิ่ม และลบ ล้วนเป็น O(h) ทั้งสิ้น ใครจะใช้ต้นไม้ค้นหาแบบทวิภาคก็อาจจะเป็นห่วงว่า การทำงานจะเร็วจะช้าขึ้นกับลักษณะของต้นไม้  ถ้าโชคร้าย การค้นหา เพิ่ม ลบก็เป็น O(n) โชคดีก็เป็น O(log n) ถ้าเรายอมรับกับสภาพเช่นนี้ไม่ได้ ต้องการประกันประสิทธิภาพให้เป็น O(log n) ตลอด ก็ต้องประกันความสูงของต้นไม้ให้ h = O(log n) ตลอดเวลา หัวข้อนี้นำเสนอต้นไม้เอวีแอล (AVL tree) ซึ่งเป็นต้นไม้ค้นหาแบบทวิภาคที่ประกันความสูงได้ตามที่ต้องการ

วัตถุประสงค์

เพื่อให้ผู้เรียนสามารถ

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