定义： 为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左右子树的高度差的绝对值不超过1.将这样的二叉树称为平衡二叉树，简称平衡树。
平衡因子： 结点左子树和右子树的高度差，平衡树平衡因子取值只可能是-1、0、1。
1、LL平衡旋转（右单旋转）
在结点A的左孩子（L）的左子树（L）上插入新节点。
static Position SingleRotateWithRight(Position K2)
{
Position K1;
K1 = K2->Right;
K2->Right = K1->Left;
K1->Left = K2;
K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
K1->Height = Max(K2->Height, Height(K1->Right)) + 1;
return K1;
}
2、RR平衡旋转（左单旋转）
在结点A的右孩子（R）的右子树（R）上插入新节点。
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), K2->Height) + 1;
return K1;
}
3、LR平衡旋转（先左后右双旋转）
在结点A的左孩子（L）的右子树（R）上插入新节点。
static Position DoubleRotateWithLeft(Position K3)
{
K3->Left = SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}
2、RL平衡旋转（先右后左双旋转）
在结点A的右孩子（R）的左子树（L）上插入新节点。
static Position DoubleRotateWithRight(Position K3)
{
K3->Right = SingleRotateWithLeft(K3->Right);
return SingleRotateWithRight(K3);
}
例子：
插入 15、3、7、10、9、8，生成平衡树。
代码实现：
#include#include #include typedef struct AvlNode *Position; typedef struct AvlNode *AvlTree; typedef int ElementType; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; struct AvlNode { ElementType Element; AvlTree Left; AvlTree Right; int Height; }; AvlTree MakeEmpty(AvlTree T) { if (T != NULL) { MakeEmpty(T->Left); MakeEmpty(T->Right); free(T); } return NULL; } static int Height(Position P) { if (P == NULL) return -1; else return P->Height; } static int Max(int a, int b) { return a > b ? a : b; } 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), K2->Height) + 1; return K1; } static Position SingleRotateWithRight(Position K2) { Position K1; K1 = K2->Right; K2->Right = K1->Left; K1->Left = K2; K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1; K1->Height = Max(K2->Height, Height(K1->Right)) + 1; return K1; } static Position DoubleRotateWithLeft(Position K3) { K3->Left = SingleRotateWithRight(K3->Left); return SingleRotateWithLeft(K3); } static Position DoubleRotateWithRight(Position K3) { K3->Right = SingleRotateWithLeft(K3->Right); return SingleRotateWithRight(K3); } AvlTree Insert(ElementType X, AvlTree T) { if (T == NULL) { T = (AvlNode*)malloc( sizeof( struct AvlNode ) ); if (T == NULL) printf("Out of space!!!n"); else { T->Element = X; T->Height = 0; T->Left = T->Right = NULL; } } else if (X < T->Element) { T->Left = Insert(X, T->Left); if (Height(T->Left) - Height(T->Right) == 2) if (X < T->Left->Element) T = SingleRotateWithLeft(T); else T = DoubleRotateWithLeft(T); } else if (X > T->Element) { T->Right = Insert(X, T->Right); if (Height(T->Right) - Height(T->Left) == 2) if (X > T->Right->Element) T = SingleRotateWithRight(T); else T = DoubleRotateWithRight(T); } T->Height = Max(Height(T->Left), Height(T->Right)) + 1; return T; } Position FindMin(AvlTree T) { if (T == NULL) return NULL; else if (T->Left == NULL) return T; else return FindMin(T->Left); } Position FindMax(AvlTree T) { if (T == NULL) return NULL; else if (T->Right == NULL) return T; else return FindMax(T->Right); } AvlTree Delete(ElementType X, AvlTree T) { Position TmpCell; if(T == NULL) { printf("没找到该元素，无法删除！n"); return NULL; } else if (X < T->Element) T->Left = Delete(X, T->Left); else if (X > T->Element) T->Right = Delete(X, T->Right); else if(T->Left && T->Right) { //要删除的树左右都有儿子 TmpCell = FindMin(T->Right); //用该结点右儿子上最小结点替换该结点，然后与只有一个儿子的操作方法相同 T->Element = TmpCell->Element; T->Right = Delete(T->Element, T->Right); }else{ TmpCell = T; //要删除的结点只有一个儿子 if(T->Left == NULL) T = T->Right; else if(T->Right == NULL) T = T->Left; free(TmpCell); } return T; } Position Find(ElementType X, AvlTree T) { if (T == NULL) return NULL; if (X < T->Element) return Find(X, T->Left); else if (X > T->Element) return Find(X, T->Right); else return T; } ElementType Retrieve(Position P) { if(P != NULL) return P->Element; return -1; } void PreorderTravel(AvlTree T) { if (T != NULL) { printf("%d", T->Element); PreorderTravel(T->Left); PreorderTravel(T->Right); } } void InorderTravel(AvlTree T) { if (T != NULL) { InorderTravel(T->Left); printf("%d", T->Element); InorderTravel(T->Right); } } void PostorderTravel(AvlTree T) { if (T != NULL) { PostorderTravel(T->Left); PostorderTravel(T->Right); printf("%d", T->Element); } } void PrintTree(AvlTree T, ElementType Element, int direction) { if (T != NULL) { if (direction == 0) printf("%2d is rootn", T->Element); else printf("%2d is %2d's %6s childn", T->Element, Element, direction == 1 ? "right" : "left"); PrintTree(T->Left, T->Element, -1); PrintTree(T->Right, T->Element, 1); } } int main(int argc, char const *argv[]) { AvlTree T; Position P; int i; T = MakeEmpty(NULL); T = Insert(15, T); T = Insert(3, T); T = Insert(7, T); T = Insert(10, T); T = Insert(9, T); T = Insert(8, T); printf("Root: %dn", T->Element); printf("树的详细信息: "); PrintTree(T, T->Element, 0); printf("n"); printf("前序遍历二叉树: "); PreorderTravel(T); printf("n"); printf("中序遍历二叉树: "); InorderTravel(T); printf("n"); printf("后序遍历二叉树: "); PostorderTravel(T); printf("n"); printf("最大值: %dn", FindMax(T)->Element); printf("最小值: %dn", FindMin(T)->Element); Delete(7, T); printf("树的详细信息: n"); PrintTree(T, T->Element, 0); return 0; }
结果：
