AVL Trees
AVL Trees =============== - Also called height balanced tree -Height of children present at same level may not have same height. There height can differ at most by 1. -The height of an AVL tree T storing n keys is O(log n) Structure of AVL Tree ======================== - Consoder an AVL tree of n nodes -Cosider a leaf which is closest to the root - Suppose this leaf is at level k. -Then height of a tree is at most 2k - 1. Summary of AVL Tree ========================== - If height is h , then leaf closest to root is at level at least (h+1)/2 -On the first (h-1)/2 levels the AVL tree is a complete binary tree - After (h-1)/2 level the AVL tree may start "thinning out" -Number of nodes in AVL tree is at least 2 to raise (h-1)/2 and at most 2 raise to h Insertion in AVL Tree ========================== Insertion of node make tree changes height and hence height balance property voilated. If Insertion causes T to become unbalanced , we travel up the