CPSC 2120 - DAY 8
MAY 24, 2016

================================================================================


AVL TREES
---------

Single Rotation

	(5)                     (5)              
	/ \                    /   \ 
      (2)   (8)              (2)  (7)
    /   \   /   -->         /  \   /  \ 
  (1)  (4) (7)            (1)  (4) (6) (8)
	/  /                    /   
      (3)  (6)		       (3)

zig - left
zag - right

To determine balance/inbalance - NULL = -1.  compare both children
if difference between height of right and left subtree is less than two, it is
balanced.

Zig-zig - single rotation right

Zig-zag - double rotation

Zag-zig - double rotation

Zag-zag - single rotation left