CPSC 2120 - DAY 9
MAY 25, 2016

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

AVL TREES
---------


When inserting a value, you always insert the value as a leaf.

You compare the height of the left and right child to determine whether it is
balanced

t == null ? - 1 : t.height

equivalent to if t == null, return -1, else, t-> height

if t == null, create new node.

CODE FOR AVL TREES
------------------

struct AvlNode
{
	Comparable element;
	AvlNode *left;
	AvlNode *right;
	int height;
	
	AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, int
		h = 0) : element(theElement), left(lt), right(rt), height(h)
}


void insert (const Comparable & x, AvlNode * & t)
{
	if(t == NULL)
		t = new AvlNode(x, NULL, NULL);
	else if( x < t-> element)
	{
		insert(x, t->left);
		if(height (t->left) - height(t->right) == 2)
			if(x < t->left->element)
				rotateWithLeftChild(t);
			else
				doubleWithLeftChild(t);
	}
	
	else if (t->element < x)
	{
		insert(x.t->right);
		if(height(t->right) - height(t->left) == 2)
			if(t->right->element < x)
				rotateWithRightChild(t);
			else
				doubleWithRightChild(t);
	}
	else
		;
	t->height = max(height(t->left), height(t->right)) + 1;
}