一棵AVL树是每个节点的左子树和右子树的高度最多差1的二叉查找树
SearchTree Insert(ElementType X, SearchTree T) {
if (T == NULL) {
T == malloc(sizeof(struct TreeNode));
if (T == NULL) {
Error("out of space");
}
else {
T->Element = X;
T->Left = T-Right = NULL;
}
}
else if (X < T->Element) {
T->Left = Insert(X, T->Left);
if (Height(T->Left)-Height(T->Right) == )
if (X < T->Left->Element)
T = SingleRotateWithLeft(T);
else
T = DoubleRotateWithLeft(T);
}
else {
T-Right = Insert(X, T->Right);
if (Height(T->Right)-Height(T->Left) == )
if (X > T->Right->Element)
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}
T->Height = Max(Height(T->Left, Height(T->Right))) + ;
return T;
} 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)) + ;
K1->Height = Max(Height(K1->Left), K2->Height) + ; reutrn K1;
} static Position DoubleRotateWithLeft(Position K3) {
K3->Left = SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}