การสร้างสมดุลให้กับต้นไม้ (Balancing Tree)
เมื่อเราเพิ่มบัพใหม่หรือลบบัพในโครงสร้างต้นไม้ AVL ผลของการเพิ่มบัพหรือลบบัพอาจจะทำให้ต้นไม้ AVL เสียคุณสมบัติได้ และเมื่อต้นไม้มีการเสียคุณสมบัติ เราจะต้องสร้างสมดุลใหม่ (rebalance) ให้กับต้นไม้ การสร้างสมดุลใหม่ให้กับต้นไม้ AVL คือ การหมุนบัพ
การหมุน (Rotation) หมายถึง การจัดเรียงตัวใหม่ของบัพในต้นไม้ เพื่อทำให้โครงสร้างต้นไม้ไม่เสียคุณสมบัติ ซึ่งการหมุนมีหลักการ ดังนี้
- ยกบัพบางตัวขึ้นและกดบัพบางตัวให้ต่ำลง เพื่อสร้างความสมดุลให้แก่โครงสร้างต้น
ไม้
- หลังจากทำการหมุนแล้วจะต้องไม่ทำให้คุณสมบัติของต้นไม้ค้นหาแบบทวิภาคเสียไป
ด้วย คือบัพลูกทางซ้ายของบัพใด ๆ ในต้นไม้ จะต้องมีค่าน้อยกว่าบัพแม่ของบัพนั้น ในขณะที่บัพลูกทางขวาของบัพใดๆ จะต้องมีค่ามากกว่าบัพแม่ของบัพนั้น
การหมุนในโครงสร้างต้นไม้ AVL มีอยู่ 3 แบบ คือ
1. หมุนครั้งเดียวทางซ้าย (Single left rotation)
คือการหมุนแล้วทำให้บัพลูกทางขวาของบัพที่เสียคุณสมบัติถูกยกตัวขึ้นไปแทน
บัพที่เสียคุณสมบัติ ส่วนบัพที่เสียคุณสมบัติจะถูกกดลงและกลายมาเป็นบัพลูกทางซ้ายของบัพที่นำไปแทนที่บัพที่เสียคุณสมบัติ 1. หมุนครั้งเดียวทางขวา (Single right rotation) บัพที่เสียคุณสมบัติ ส่วนบัพที่เสียคุณสมบัติจะถูกกดลงมากลายเป็นบัพลูกทางขวาของบัพที่นำไปแทนที่บัพที่เสียคุณสมบัติ 2. การหมุนสองครั้ง (Double rotation) คือการหมุนให้กับบัพที่เสียคุณสมบัติ เพียงครั้งเดียวไม่ได้ ต้องทำการหมุนสองครั้ง โดยการหมุนทั้งสองครั้งนั้นจะใช้หลักการหมุนครั้งเดียวทั้งสองครั้ง ซึ่งการหมุนครั้งแรกอาจเป็นการหมุนครั้งเดียวทางซ้ายก่อนแล้วครั้งที่สองด้วยการหมุนครั้งเดียวทางขวาหรือครั้งแรกหมุนครั้งเดียวทางขวา ครั้งที่สองหมุนด้วยครั้งเดียวทางซ้าย ขึ้นอยู่กับลักษณะการเสียคุณสมบัติของบัพ คือการหมุนแล้วทำให้บัพลูกทางซ้ายของบัพที่เสียคุณสมบัติถูกยกตัวขึ้นไปแทน
