AVL树：带有平衡条件的二叉查找树，即一棵AVL树是其每个节点的左子树和右子树的高度最多相差1的二叉查找树。一般通过Single Rotate和Double Rotate来保持AVL树的平衡。
AVL树的实现如下：
1) Single Rotate
2)Double Rotate
1) Single Rotate ( SingleRotateWithRight同理)
static Position SingleRotateWithLeft(Position K2) { Position K1; K1=K2->Left; K2->Left=K1->Right; K1->Right=K2; K2->Height=Max(Height(K2->Left),Height(K2->Right))+1; K1->Height=Max(Height(K1->Left),Height(K1->Right))+1; return K1; }
2)Double Rotate(DoubleRotateWithRight同理)
static Position DoubleRotateWithLeft(Position K3) { K3->Left=SingleRotateWithRight(K3->Left); return SingleRotateWithLeft(K3); }
原文：http://www.cnblogs.com/riden/p/4564432.html