/***AVL平衡树插入例程**2014-5-30 11:44:50*/avlTree insert(elementType X, avlTree T){	if(T == NULL){		T = malloc(sizeof(struct avlTree));		if(T == NULL) fatalError("Out of space!!!");		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);		}	}	/*--假设X已经存在，那么啥都不用做--*/		T->height = max(height(T->left), height(T->right)) + 1;	return T;}static position singleRotateWithLeft(position k2){	position 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;}/*双右左旋就是先对T的右子树左单旋再对T本身右单旋*/static position