AVL Tree  (Adelson-Velskii and Landis)

n  เป็น Binary Search Tree ที่อยู่ภายใต้เงื่อนไขของความสมดุล (Balance Condition)

n  Depth ของ Tree เป็น O(Log N)

n  ค่า Height ของ Subtree ด้านซ้ายและด้านขวาต่างกันได้ไม่เกิน 1

AVL Tree Operations

n  การดำเนินการบน AVL Tree มักใช้เวลาเป็น O(Log N)

n  การ Insert ในบางกรณีซึ่งต้องการการ Update เพื่อ Balance ของ Node บาง Node ที่อยู่บน path ขึ้นไปถึง Root

n  การ Update การ Balance ของ Tree นี้ทำได้ด้วยการRotation (การหมุน)  

n  Single Rotation

n  Double Rotation

AVL Tree Rotation

&  ni เป็น Node ที่ต้องการจัดสมดุลใหม่หรือการ Rebalance โดยเห็นได้ว่าการเสียสมดุลของ Tree จะเกิดได้จาก 4 กรณี

&  LL – Insert into left subtree of the left child

&  RR – Insert into right subtree of the right child

&  LR – Insert into right subtree of the left subtree of the node

&  RL – Insert into left subtree of the right subtree of the node

Single Rotation

n  สำหรับ LL และ RR การ Insert เกิดที่ด้านนอก (Outside) ของ Tree (ซ้าย-ซ้าย, ขวา-ขวา)

&  Rebalance ได้ด้วย Single Rotation

&  LL – Insert ที่ X ทำให้ k2 เสียสมดุล

&  RR - Insert ที่ Z ทำให้ k1 เสียสมดุล

& Node 23 ทำให้ subtree ด้านซ้ายของ 16 มี height= 2 ขณะที่ subtree ด้านขวาของ 16 มี height= 0

&        Rebalance Node 16 ด้วย Single Rotation

& AVL TREE เมื่อมี Tree ที่ไม่สมดุลจะเกิดการหมุนเพื่อให้สมดุลซึ่งมี 4 วิธี

 1. การหมุนซ้าย : โหนดทางขวามากกว่าซ้าย ยกโหนดที่อยู่ขวาขึ้นมา

 2. การหมุนขวา  : โหนดทางซ้ายมากกว่าขวา ยกโหนดที่อยู่ซ้ายขึ้นมา

 3. การหมุนขวาไปซ้าย : หมุนขวาก่อน แล้วค่อยหมุนซ้าย

 4. การหมุนซ้ายไปขวา : หมุนซ้ายก่อน แล้วค่อยหมุนขวา