发布时间 : 星期一 文章动态查找树之平衡二叉树（Balanced Binary Tree,AVL树）更新完毕开始阅读ef873a4f2b160b4e767fcfde
插入删除是互为镜像的操作。我们可以采用前面对二叉排序树的删除操作来进行。然后，在删除掉结点后，再对平衡树进行平衡化处理。删除之所以删除操作需要的平衡化可能比插入时次数多，就是因为平衡化不会增加子树的高度，但是可能会减少子树的高度，在有有可能使树增高的插入操作中，一次平衡化能抵消掉增高；在有可能使树减低的删除操作中，平衡化可能会带来祖先节点的不平衡。
四、二叉排序数的C语言实现 #include \#include \#include \#define LH +1 //左高 #define EH 0 //等高 #define RH -1 //右高 #define TRUE 1 #define FALSE 1
#define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)< (b)) #define LQ(a,b) ((a)<=(b)) #define BT(a,b) ((a)> (b)) typedef int KeyType; typedef int info; typedef int Boolean; typedef struct ElemType {
KeyType key;
//info otherinfo;
};
typedef struct BSTNode {
ElemType data; int bf;
BSTNode *lchild,*rchild; // 左右孩子指针 }BSTNode,*BSTree;
void R_Rotate(BSTree &p) {//右旋 BSTree lc; lc=p->lchild;
p->lchild=lc->rchild; lc->rchild=p;
p=lc; //p指向新的根结点 }//R_Rotate
void L_Rotate(BSTree &p) {//左旋 BSTree rc; rc=p->rchild;
p->rchild=rc->lchild; rc->lchild=p;
p=rc; //p指向新的根结点 }//L_Rotate
void LeftBalance(BSTree &T) {//作平衡旋转处理 BSTree lc,rd; lc=T->lchild; switch(lc->bf) {
case LH:
T->bf=lc->bf=EH; R_Rotate(T); break; case RH:
rd=lc->rchild; switch(rd->bf) {
case LH:T->bf=RH;lc->bf=EH;break; case EH:T->bf=lc->bf=EH; break; case RH:T->bf=EH;lc->bf=LH;break; }//switch rd->bf=EH;
L_Rotate(T->lchild); R_Rotate(T); }//switch }//LeftBalance
void RightBalance(BSTree &T) {//作平衡旋转处理