Notes on AVL tree

Stripped down rotations on binary tree

/** call the following functions ONLY if nodes
	being rotated exist --
	error checking has been removed to simplify code
 */

/**********************************************/  

/** rotateLeft: rotate node with right child
    i.e., child rotates up and to the left
    p is right heavy and p.right is right heavy
 */
 
Node rotateLeft (Node p) {  
  Node temp = p.right;		// use temp to simplify code
  p.right = temp.left;
  temp.left = p;
  return temp;
  }
  
/**********************************************/  

/** rotateRight: rotate node with left child
    i.e., child rotates up and to the right
    p is left heavy and p.left is left heavy
 */
 
Node rotateRight (Node p) {
	Node temp = p.left;	// use temp to simplify code
	p.left = temp.right;
	temp.right = p;
	return temp;
	}

/**********************************************/  
	
/** 
  p is right heavy, p.right is left heavy 
 */
 
Node rotateLeftRight(Node p) {
	p.right = rotateRight(p.right);
	p = rotateLeft(p);
	return p;
	}
	
/**********************************************/  

/**
  p is left heavy, p.right is right heavy
*/

Node rotateRightLeft(Node p) {
	p.left = rotateLeft(p.left);
	p = rotateRight(p);
	return p;
	}

/************************************************/	
/**  usage example **/
/* do not call rotate methods on empty nodes!! */

if (p is right heavy && p.right is right heavy) 
	p = rotateLeft(p);
	
else if (p is left heavy && p.left is left heavy)
	p = rotateLeft(p);
	
else if (p is right heavy && p.right is left heavy)
	p = rotateLeftRight(p);
	
else if (p is left heavy && p.left is right heavy)
	p = rotateRightLeft(p);