https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL

• Is invented by Adelson-Velskii and Landis (AVL).
• An AVL is a height-balanced BST.
• Designed for improving the search efficiency of a [[10 Binary Search Tree|BST]] by rotating it to become balanced.

Requirements

จริง ๆ มันก็เป็น Binary Search Tree นั่นแหละนะ แต่แค่มีการ Rotation ให้มัน Efficiently ในการ Search

• An AVL has the following requirements
  • It must be a BST
  • the difference between heights of left and right subtrees cannot be more than one for all nodes.
    • i.e. the balance factor ($H_L - H_R$) of each node in AVL must be either -1, 0, 1

Examples

Tree which are not AVLs

Tree which are AVLs

Operations of AVL

• Insertion, deletion, and searching of AVL are similar to those of BST
• When the structure becomes unbalanced, apply appropriate rotations to keep it balanced.
• Disadvantage คือ ต้อง apply rotation

Constructing an AVL from an unbalanced BST

• Find a balance factor of each node
• Find unbalanced subtrees that fits to the following 4 cases
  • Left of Left— A subtree of a tree that is left high has also become left high
    
  • Right of Right— A subtree of a tree that is right high has also become right high
    
  • Right of Left— A subtree of a tree that is left high has also become right high
    
  • Left of Right— A subtree of a tree that is right high has also become left high
    

Left of Left

• ทำให้สุดท้ายได้เป็น Hat-shaped
  

Right of Right

Right of Left

Left of Right

Constructing an AVL from the sequential data

ต้อง Fix the structure as soon as it becomes unbalanced → เอามาทีละ 3 ๆ

Big-O Analysis of an AVL of size $n$

• เนื่องจากพอมันเป็น Nearly Completed/Completed BST เนี่ย สุดท้าย Big-O ที่ได้ทั้งหมดมันก็จะเป็น $O(\log n)$ ได้มาจาก Height ของ Tree