在上一篇文章查找-之二叉排序树（查找、插入、删除）引出的问题是：
二叉排序树的存在的不足是插入新结点导致树不平衡，不平衡树使得查找性能下降
解决方法
构建平衡的二叉树
AVL树、红黑树
AVL树：带有严格平衡条件的二叉查找树，用平衡因子差值判断树是否平衡并通过旋转实现平衡，左右子树的高度不超过1
适用于：插入和删除次数较少（插入删除操作使得树失去平衡，为维持严格平衡旋转操作，使得性能下降），查找次数较多的情况
Windows NT内核中广泛存在
算法复杂度：时间复杂度，查找O（logn）， 插入和删除 O（logn）
存在的问题：
AVL树的每个结点只能存放一个元素、并且每个结点只有两个子结点，查找时需要多次磁盘IO操作，每次查询从磁盘中的一页数据拷贝到内存，其中树的每一层结点存放在一页中，不同层数据存放在不同页，为此查找数据需要多次操作磁盘IO
红黑树：弱平衡二叉查找树，通过对任何一条根到叶子路径各个结点着色来限制，确保没有一条路径会比其它路径长出两倍
适用于：插入、删除次数较多，查找次数较多的情况
应用：
linux进程调度用红黑树管理进程控制块
Java Treemap、TreeSet
C++ STL
Nginx 中的定时器管理
算法复杂度：
查找、删除、插入操作的时间复杂度：O（logn）， O(log2 (n))
统计性能好于AVL树
AVL树：
1）左子树高于右子树，则旋转因子BF为正，该结点对应的整棵树右旋
2）右子树高于左子树，则旋转因子BF为负，该结点对应的整棵树左旋
3）符号不统一，双旋
//二叉树的二叉链表结点结构定义 typedef struct BiTNode { int data; //结点数据 int bf; //结点平衡因子 struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree;
//对以P为根的二叉排序树做右旋处理 void R_Rotate(BiTree *P) { BiTree L; L=(*P)->lchild; (*P)->lchild=L->rchild; L->rchild=(*P); *P=L;//P指向新的根结点 } //对以P为根的二叉排序树做左旋处理 void L_Rotate(BiTree *P) { BiTree R; R=(*P)->rchild; (*P)->rchild=R->lchild; R->lchild=(*P); *P=R; }
//左平衡旋转处理的函数代码 #define LH +1 //左高 #define EH 0 // 等高 #define RH -1 // 右高 //对指针T所指结点为根的二叉树作左平衡旋转处理,左子树的高度大于右子树的高度 void LeftBalance(BiTree *T) { BiTree L,Lr; L=(*T)->lchild;//L指向左子树的根结点 switch(L->bf) { //检查左子树的平衡度，并做相应的平衡处理 case LH://+1 说明L->bf和根结点的符号相同， （新结点插在T的左孩子的左子树上）----右旋处理 (*T)->bf=L->bf=EH; R_Rotate(T); break; case RH:// -1 说明L->bf -1和根结点的符号相反 ， （新结点插入在T的左孩子的右子树上） -----双旋处理 Lr=L->rchild;//Lr指向T的左孩子的右子树根 switch(Lr->bf)//T的左孩子的右子树根做判断---修改T及T的左孩子L的平衡因子 ？？ { case LH: //左高 +1 (*T)->bf=RH;//-1 L->bf=EH;//0 break; case EH://等高 0 (*T)->bf=L->bf=EH;//0 break; case RH: //右高 -1 (*T)->bf=EH;//0 L->bf=LH;//+1 break; } Lr->bf=EH;//0 L_Rotate(&(*T)->lchild);//T的左孩子左旋 R_Rotate(T);//T右旋 } }
// 若在平衡二叉排序树T中不存在和e有相同关键字的结点，则插入一个 //因插入数据而使得二叉排序树失去平衡，则做平衡旋转处理 //taller 反映树T长高与否 Status InsertAVL(BiTree *T,int e,Status *taller) { if(!*T)//如果树空 { *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH; *taller=True; } else { if(e==(*T)->data)//树中已存在和e有相同关键字的结点--则不再插入 { *taller=False; return False; } if(e<(*T)->data)//待插入的数小于根节点 ---在T的左子树搜索 { //继续在T的左子树中进行搜索 if(!InsertAVL(&(*T)->lchild,e,taller))//若在左子树中找到该插入的结点，则返回false return False; if(taller)//已插入到T的左子树且左子树长高 { switch((*T)->bf)//检查T的平衡度 { case LH://原本左子树比右子树高，现在左子树插入，需做左平衡处理 LeftBalance(T); *taller=False; break; case EH://原本左子树等于右子树，现在左子树插入，现在左子树增高 (*T)-bf=LH; *taller=True; break; case RH://原本右子树比左子树高，现在左子树插入，现在左右子树等高 (*T)->bf=EH; *taller=False; break; } } } else//继续在T的右子树中进行搜索 { if(!InsertAVL(&(*T)->rchild,e,taller)) //若在右子树中找到该插入的结点，则返回false ，未插入 { return False; } if(*taller)//插入T的右子树且右子树长高 { switch((*T)->bf) { case LH: //原本左子树比右子树高，现在在右子树插入，左右子树等高 (*T)->bf=EH; *taller=False; break; case EH: //原本左右子树等高，现在在右子树插入，右子树增高 (*T)->bf=RH; *taller=True; break; case RH: //原本右子树比左子树高，现在在右子树插入，需要做右平衡处理 RightBalance(T); *taller=False; break; } } } } return True; }
构建平衡二叉树的示例
//构建平衡二叉树 int i; int a[10]={3,2,1,4,5,6,7,10,9,8}; BiTree T=NULL; Status taller; for(i=0;i<10;i++) { InsertAVL(&T,a[i],&taller); }
参考
《大话数据结构》
