动态查找树之平衡二叉树（Balanced Binary Tree,AVL树）

插入删除是互为镜像的操作。我们可以采用前面对二叉排序树的删除操作来进行。然后，在删除掉结点后，再对平衡树进行平衡化处理。删除之所以删除操作需要的平衡化可能比插入时次数多，就是因为平衡化不会增加子树的高度，但是可能会减少子树的高度，在有有可能使树增高的插入操作中，一次平衡化能抵消掉增高；在有可能使树减低的删除操作中，平衡化可能会带来祖先节点的不平衡。

四、二叉排序数的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) {//作平衡旋转处理