/******************环境：http://anycodes.cn/zh/AVL有高度标签红黑树更有颜色标记http://blog.csdn.net/whucyl/article/details/17289841我们总是以ABC3个结点为例子插入元素后C总是不平衡的LLRR较为简单交换后C还是出于下方LRRL统一的一句就是C总提出交换子树，要翻身做了老大。LLLR与RRRL是对称的4种情况写了前2种就能写出后2种******************/#ifndefHEAD_H_#defineHEAD_H_#include<stdio.h>#include<stdlib.h>#defineN15typedefintElementType;typedefstructAvlNode//AVL树的节点{ElementTypedata;structAvlNode*left;//左孩子structAvlNode*right;//右孩子intHeight;}*Position,*AvlTree;AvlTreeMakeEmpty(AvlTreeT);PositionFind(ElementTypex,AvlTreeT);PositionFindMin(AvlTreeT);PositionFindMax(AvlTreeT);AvlTreeInsert(ElementTypex,AvlTreeT);AvlTreeDelete(ElementTypex,AvlTreeT);ElementTypeRetrieve(PositionP);voidDisplay(AvlTreeT);#endif/*HEAD_H_*//**初始化AVL树*/AvlTreeMakeEmpty(AvlTreeT){if(T!=NULL){MakeEmpty(T->left);MakeEmpty(T->right);free(T);}returnNULL;}/**查找可以像普通二叉查找树一样的进行，所以耗费O(logn)时间，因为AVL树总是保持平衡的。*不需要特殊的准备，树的结构不会由于查找而改变。（这是与伸展树查找相对立的，它会因为查找而变更树结构。）*/PositionFind(ElementTypex,AvlTreeT){if(T==NULL)returnNULL;if(x<T->data)returnFind(x,T->left);elseif(x>T->data)returnFind(x,T->right);elsereturnT;/*/递归中左走走右走走要么找不到要么返回找到的T结点/*/}/**FindMax，FindMin查找最大和最小值，*没有特别的这个就递归或循环找到最右下角和最左下即可*/PositionFindMin(AvlTreeT){if(T==NULL)returnNULL;if(T->left==NULL)returnT;elsereturnFindMin(T->left);}PositionFindMax(AvlTreeT){if(T!=NULL){while(T->right!=NULL)T=T->right;}returnT;}/**返回节点的高度*/staticintHeight(PositionP){if(P==NULL)return-1;elsereturnP->Height;}staticintMax(inth2,inth3){returnh2>h3?h2:h3;}/**此函数用于k2只有一个左孩子的单旋转，*在K2和它的左孩子之间旋转，*更新高度，返回新的根节点frist：K2K1K2RK1LK1Rthen：K1K1LK2K1RK2R*/staticPositionSingleRotateWithLeft(Positionk2)/*/LL旋转/*/{Positionk1;k1=k2->left;k2->left=k1->right;k1->right=k2;/*/因为比较的是左右孩子的高度，所以求父节点的高度要加1/*/k2->Height=Max(Height(k2->left),Height(k2->right))+1;k1->Height=Max(Height(k1->left),Height(k2->right))+1;returnk1;}/**此函数用于k1只有一个右孩子的单旋转，*在K1和它的右孩子之间旋转，*更新高度，返回新的根节点frist：K1K1LK2K2LK2Rthen：K2K1K2RK1LK2L*/staticPositionSingleRotateWithRight(Positionk1)/*/RR旋转/*/{Positionk2;k2=k1->right;k1->right=k2->left;k2->left=k1;/*结点的位置变了,要更新结点的高度值*/k1->Height=Max(Height(k1->left),Height(k1->right))+1;k2->Height=Max(Height(k2->left),Height(k2->right))+1;returnk2;}/**此函数用于当如果k3有一个左孩子，以及*它的左孩子又有右孩子，执行这个双旋转*更新高度，返回新的根节点first：K1K2K1RK2LK3K3LK3Rthen：K3K2K1K2LK3LK3RK1R*/staticPositionDoubleRotateLeft(Positionk3)/*/LR旋转/*/{/*/在k3的左孩子，执行右侧单旋转/*/k3->left=SingleRotateWithRight(k3->left);/*/RR旋转/*//*/再对k3进行左侧单旋转/*/returnSingleRotateWithLeft(k3);/*/LL旋转/*/}/**此函数用于当如果k4有一个右孩子，以及*它的右孩子又有左孩子，执行这个双旋转*更新高度，返回新的根节点first：K1K1LK2K4K2Rk4LK4Rthen：K4K1K2K1LK4LK4RK2R*/staticPositionDoubleRotateRight(Positionk4)/*/RL旋转/*/{/*/在k4的右孩子，执行左侧单旋转/*/k4->right=SingleRotateWithLeft(k4->right);/*/再对k4进行右侧单旋转/*/returnSingleRotateWithRight(k4);}/**向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，*接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。*因为折回到根节点的路途上最多有1.5乘logn个节点，而每次AVL旋转都耗费恒定的时间，*插入处理在整体上耗费O(logn)时间。X<CURX>CURTTXXXXLLLRRLRR*//*/4种基本的交换子树方式写好后以下进入重点/*/AvlTreeInsert(ElementTypex,AvlTreeT){/*/如果T不存在，则创建一个节点树/*/if(T==NULL){T=(AvlTree)malloc(sizeof(structAvlNode));{T->data=x;T->Height=0;T->left=T->right=NULL;}}/*/如果要插入的元素小于当前元素/*/elseif(x<T->data){/*/递归插入/*/T->left=Insert(x,T->left);/*/插入元素之后，若T的左子树比右子树高度之差是2，即不满足AVL平衡特性，需要调整/*/if(Height(T->left)-Height(T->right)==2){/*/把x插入到了T->left的左侧，只需左侧单旋转/*/if(x<T->left->data)T=SingleRotateWithLeft(T);/*/LL旋转/*/else/*/x插入到了T->left的右侧，需要左侧双旋转/*/T=DoubleRotateLeft(T);//LR旋转/*/}}/*/如果要插入的元素大于当前元素/*/elseif(x>T->data){T->right=Insert(x,T->right);if(Height(T->right)-Height(T->left)==2){if(x>T->right->data)T=SingleRotateWithRight(T);/*/RR旋转/*/elseT=DoubleRotateRight(T);/*/RL旋转/*/}}T->Height=Max(Height(T->left),Height(T->right))+1;returnT;}/**对单个节点进行的AVL调整TTLTRTLLTLRX1.LL2.LRTTLTRTLLTLRX3.RL4.RR*/AvlTreeRotate(AvlTreeT){if(Height(T->left)-Height(T->right)==2){if(Height(T->left->left)>=Height(T->left->right))T=SingleRotateWithLeft(T);/*/LL旋转/*/elseT=DoubleRotateLeft(T);/*/LR旋转/*/}if(Height(T->right)-Height(T->left)==2){if(Height(T->right->right)>=Height(T->right->left))T=SingleRotateWithRight(T);/*/RR旋转/*/elseT=DoubleRotateRight(T);/*/RL旋转/*/}returnT;}/**首先定位要删除的节点，然后用该节点的右孩子的最左孩子替换该节点，*并重新调整以该节点为根的子树为AVL树，具体调整方法跟插入数据类似*删除处理在整体上耗费O(logn)时间。*/AvlTreeDelete(ElementTypex,AvlTreeT){if(T==NULL)returnNULL;if(T->data==x)/*/要删除的x等于当前节点元素/*/{if(T->right==NULL)/*/若所要删除的节点T的右孩子为空,则直接删除/*/{AvlTreetmp=T;T=T->left;free(tmp);}else/*否则找到T->right的最左儿子代替T*/{AvlTreetmp=T->right;while(tmp->left)tmp=tmp->left;T->data=tmp->data;/*对于替代后的T即其字节点进行调整*/T->right=Delete(T->data,T->right);T->Height=Max(Height(T->left),Height(T->right))+1;}returnT;}elseif(x>T->data)/*/要删除的x大于当前节点元素，在T的右子树中查找删除/*/{T->right=Delete(x,T->right);}else/*/要删除的x小于当前节点元素，在T的左子树中查找删除/*/{T->left=Delete(x,T->left);}/**当删除元素后调整平衡*/T->Height=Max(Height(T->left),Height(T->right))+1;if(T->left!=NULL)T->left=Rotate(T->left);if(T->right!=NULL)T->right=Rotate(T->right);if(T)T=Rotate(T);returnT;}/**返回当前位置的元素*/ElementTypeRetrieve(PositionP){returnP->data;}/**遍历输出LDR中序遍历*/voidDisplay(AvlTreeT){staticintn=0;if(NULL!=T){Display(T->left);printf("[%d]ndata=%d\n",++n,T->data);Display(T->right);}}voidPointAsTree(AvlTreeT,intlay){if(T){PointAsTree(T->right,lay+1);for(inti=0;i<lay;i++)printf("**");printf("%d\n",T->data);PointAsTree(T->left,lay+1);}}intmain(){AvlTreeT=NULL;inti;intj=0;T=MakeEmpty(NULL);puts("数据准备\n");for(i=0;i<N;i++,j=(j+7)%50){/*插入15个数*/printf("j=%d",j);T=Insert(j,T);}puts("插入4\n");T=Insert(4,T);//printf("中序遍历\n");//Display(T);PointAsTree(T,4);printf("删除偶数值\n");for(i=0;i<N;i+=2){printf("delelte:%d\n",i);T=Delete(i,T);}printf("height=%d\n",T->Height);//printf("中序遍历\n");//Display(T);PointAsTree(T,4);puts("[1]ndata=0中[]数字仅用于展现递归调用多少次\n");printf("Minis%d,Maxis%d\n",Retrieve(FindMin(T)),Retrieve(FindMax(T)));returnEXIT_SUCCESS;}