二叉平衡树的程序分析.doc

/* Note:Your choice is C IDE */平衡二叉树。#include stdio.h#include stdlib.htypedef struct Nodeint key;struct Node*pLeft;struct Node*pRight;int bf;Node;void RightRotate(Node*pNode)/ 右旋函数。Node*pAxis=(*pNode)-pLeft;(*pNode)-pLeft=pAxis-pRight;pAxis-pRight=*pNode;*pNode=pAxis;void LeftRotate(Node*pNode)/ 左旋函数。Node*pAxis=(*pNode)-pRight;(*pNode)-pRight=pAxis-pLeft;pAxis-pLeft=*pNode;*pNode=pAxis;void LL_LR_Balance(Node*pNode)/LL型或LR函数。Node*pLeft=(*pNode)-pLeft;Node*pRight;switch(pLeft-bf)case 1:(*pNode)-bf=pLeft-bf=0;RightRotate(pNode);break;case -1:pRight=pLeft-pRight;switch(pRight-bf)case 0:(*pNode)-bf=pLeft-bf=0;break;case 1:pRight-bf=pLeft-bf=0;(*pNode)-bf=-1;break;case -1:(*pNode)-bf=pRight-bf=0;pLeft-bf=1;break;LeftRotate(&(*pNode)-pLeft);RightRotate(pNode);break;void RR_RL_Balance(Node*pNode) /RR型或RL函数。Node*pRight=(*pNode)-pRight;Node*pLeft;switch(pRight-bf)case -1:(*pNode)-bf=pRight-bf=0;LeftRotate(pNode);break;case 1:pLeft=pRight-pLeft;switch(pLeft-bf)case 0:(*pNode)-bf=pRight-bf=0;break;case 1:(*pNode)-bf=pLeft-bf=0;pRight-bf=-1;break;case -1:pRight-bf=pLeft-bf=0;(*pNode)-bf=1;break;RightRotate(&(*pNode)-pRight);LeftRotate(pNode);break;int InsertBST(Node*pRoot,int key,int*chain) Insert（）函数。 if(*pRoot)=NULL) *pRoot=(Node*)malloc(sizeof(Node);(*pRoot)-bf=0;(*pRoot)-pLeft=(*pRoot)-pRight=NULL;(*pRoot)-key=key;*chain=1;elseif(key=(*pRoot)-key)*chain=0;return 0;if(keykey)if(!InsertBST(&(*pRoot)-pLeft,key,chain)return 0;if(*chain) switch(*pRoot)-bf)case 0:(*pRoot)-bf=1;*chain=1;break;case 1:LL_LR_Balance(pRoot);*chain=0;break;case -1:(*pRoot)-bf=0;*chain=0;break; elseif(!InsertBST(&(*pRoot)-pRight,key,chain)return 0;if(*chain) switch(*pRoot)-bf)case 0:(*pRoot)-bf=-1;*chain=1;break;case 1:(*pRoot)-bf=0;*chain=0;break;case -1:RR_RL_Balance(pRoot);*chain=0;break; return 1;void PintTree(Node *bt,int n)/屏幕显示二叉树!int i;if(bt=NULL)return ;PintTree(bt-pLeft,n+1);for(i=0;i=1)printf( -);printf(%dn,bt-key);PintTree(bt-pRight,n+1);void main()Node*pRoot=NULL;int a=0,*chain=&a,n=0; InsertBST(&pRoot,3,chain); InsertBST(&pRoot,8,chain); InsertBST(&pRoot,16,chain); InsertBST(&pRoot,7,chain); InsertBST(&pRoot,2,chain); InsertBST(&pRoot,5,chain); PintTree(pRoot, n); RR型或RL函数与LL型或LR函数的程序分析：已经知道是LL型的树。设n、 x、y表示数的高度， x=n-1，y=n-1；B的左子树的高度为n,包括C。A上的2表示平衡因子Abf。B上的1也是Bbf。右旋后结果：由图可知A的平衡因子变为0，B的平衡因子也变为0。至于子树的位置都不变。下面是LR型（先左旋，后右旋）分三种情况。Cbf=0；（Cbf为平衡因子。）设C的左子树的高度x=n，由于C的平衡因子为0，则右子树的高度y=n，同理已知了B的右子树的高度为n+1，B的平衡因子为-1，则可知B的左子树的高度为n.。其余的推论类似。第一步左旋：第二步右旋：由于C原来为0，不用修改。当Cbf=1时。第一步：第二步：当Cbf=-1时。第一步：第二步：下面的是RR型的二叉平衡树。（只需左旋一次。）左旋后的结果：左旋之后，如图，得到A、B点的平衡因子信息。如上修改。下面是RL型的证明：也分三种情况：Cbf=0，第一步右旋：第二步（左旋）：当Cbf=1，第一步：第二步：当Cbf=-1时。第一步：第二步：对Insert（）函数的分析：Insert（）函数的插入算法的内容： 如果插入一个叶子结点，对于双亲结点来说，高度是增加的。未插入时，parentbf=0。左边插入后，parentbf+1=1.高度增加chan=1。右边插入后，parentbf-1=-1.高度增加,chan=1。（如果某结点的子树高度增加，则该结点的高度的改变量可能为1、0、-1，要做出判断。）而在递归退回到双亲结点的双亲结点时，当这个祖先结点的子树高度增加，该结点的平衡因子grandparentbf可能为1、0、-1。 .如果双亲结点是祖先的左孩子。若grandparentbf=-1，则grandparentbf=0；高度没有增加，chan=0；若grandparentbf=0，则grandparentbf=1；高度增加，chan=1；若grandparentbf=1，则grandparentbf=2；调用LL型或LR函数，高度没有增加，chan=0；.如果双亲结点是祖先的右孩子。若grandparentbf=-1，则grandparentbf=-2；调用RR型或RL函数，高度没有增加，chan=0；若gr