 # Everything you need to know about AVL Trees! • The height of a non existing tree is -1.
• The height of a tree T with only one node (root) is 0
• Heights of the trees above are: 0, 1, 2, 3, 4 respectively.

The Height Balance Property

• The BP (Balance Property) has to be within the range [-1, 0, 1]
• Unbalanced Tree: if balance factor of any node falls outside [-1,0,1]
• Balanced Tree: for every node, left height & right height differ by most 1.
• Balance Factor of leaf nodes is 0, because the don?t have any children.

Running Time

• Search: O(logn) ? BST on a Sorted Array
• Add: O(n) ? we will need to implement Insertion Sort
• Remove: O(n) ? even if the search is O(logn), we will still need to close the gap after deletion therefore its O(n) times.

How do we determine if a Tree is an AVL tree?

We determine by calculating the balance factor on each node. If the the balance factor on any given node is outside the range [-1,0,1], then it is not an AVL Tree.

Let?s calculate the balance factor of each node to determine if its an AVL Tree. BF=height of left ? height of right

• Root: BF(15)= 2?3 = -1 ?
• Left Subtree: BF(6) = 0 ? ? . BF(10)=0 ? ? . BF(8)=1?1=0 ?
• Right Subtree: BF(58)= 0 ? ? . BF(25)= 1?0=1 ? ? . BF(23)= 0?2 = -2 ?

This is NOT an AVL Tree, as the BF at node(23) falls outside the range [-1,0,1]

• Root: BF(15)= 2?1= 1?
• Left Subtree: BF(6)= 0 ? . BF(10)= 0 ? . BF(8)= 1?1= 0 ?
• Right Subtree: BF(23)= 0 ?

YESSS! This is an AVL Tree! ?

Can we convert an unbalanced tree to a balanced tree?

Yes, we can! Let?s see how to do it!

Insertion/Deletion of a new node in your tree might destroy the balance of your tree and violate the height balance property!!! We can restore the balance through one or more ?rotations?.

Rotation: secures the Binary Search Tree property and restores it?s balance. In order to secure a successful rotation of the tree, we can check it by performing In-Order Traversal and it must produce the same result on both the original tree and the reconstructed one.

Types of Rotations

1. Single Left Rotation: on a node and 2 children
2. Single Right Rotation: on a node and 2 children
3. Double Left-Right Rotation: on a node, child and grandchild.
4. Double Right-Left Rotation: on a node, child and grandchild.