1、AVL树删除

思路：

(1)、首先找到要删除的结点；没找到，直接false返回退出即可；

(2)、将其转化为只有一个分支的结点，前面的路径都要入栈，

(3)、其父节点(parent)的平衡因子(根据父的左/右=p(要删除的结点)，修改父的bf)，有几种情况,i>父节点的bf=1/-1，代表原先有两个结点，现在剩下一个了，直接退出循环，不用再往上寻找更改bf了；ii>父节点的bf=0；代表此时的往上更改爷爷结点(在此出栈即可，栈中保存了路径信息)的bf，看情况(bf=2/-2)是否进行旋转，和要进行相应的旋转方式。

(4)、判断栈空，进行相应的连接操作；

(5)、最后删除这个结点；

相应部分情况：

2、AVL树删除代码

template<typenameType>boolAVLTree<Type>::remove(AVLNode<Type>*&t,constType&x){AVLNode<Type>*p=t;AVLNode<Type>*parent=NULL;//父结点AVLNode<Type>*q=NULL;//删除结点的辅助结点stack<AVLNode<Type>*>st;AVLNode<Type>*ppr;//爷爷结点intflag=0;while(p!=NULL){if(p->data==x){break;}parent=p;st.push(parent);if(x<p->data){p=p->leftChild;}else{p=p->rightChild;}}//以上是：查找删除点if(p==NULL){//没有要删除的结点returnfalse;}if(p->leftChild!=NULL&&p->rightChild!=NULL){parent=p;st.push(parent);q=p->leftChild;while(q->rightChild!=NULL){parent=q;st.push(parent);q=q->rightChild;}p->data=q->data;p=q;}if(p->leftChild!=NULL){q=p->leftChild;}else{q=p->rightChild;}//以上是：使其要删除的转化为只有一个分支的if(parent==NULL){//删除的是根结点，并且无入栈，代表只有一个分支，并没有寻找t=q;}else{if(parent->leftChild==p){flag=0;parent->leftChild=q;}else{flag=1;parent->rightChild=q;}while(!st.empty()){parent=st.top();st.pop();if(parent->leftChild==q){//对要删除的父节点更改bf;parent->bf++;}else{parent->bf--;}if(!st.empty()){ppr=st.top();if(ppr->leftChild==parent){flag=0;}else{flag=1;}}if(parent->bf==-1||parent->bf==1){break;//删除前的平衡因子为0，此时不用再调整其它平衡因子,直接退出循环;}if(parent->bf==0){//原先只有左孩子/右孩子q=parent;//往上回溯更改爷爷结点的bf；}else{//此时到达2,已经不平衡了，的进行旋转化的调整if(parent->bf<0){flag=-1;q=parent->leftChild;}else{flag=1;q=parent->rightChild;}if(q->bf==0){if(flag==-1){}}if(parent->bf>0){q=parent->rightChild;if(q->bf==0){RotateL(parent);}elseif(q->bf>0){RotateL(parent);}else{RotateRL(parent);}}else{q=parent->leftChild;if(q->bf==0){RotateR(parent);}elseif(q->bf<0){RotateR(parent);}else{RotateLR(parent);}}}}if(st.empty()){t=parent;//直接更改root}else{AVLNode<Type>*tmp=st.top();//当前的栈顶结点使其的左/右指向parent(是旋转化后的根);if(parent->data<tmp->data){tmp->leftChild=parent;}else{tmp->rightChild=parent;}}}deletep;//删除结点;returntrue;}

3、完整代码、测试代码、测试结果

(1)完整代码

#ifndef_AVL_TREE_H_#define_AVL_TREE_H_#include<iostream>//引入头文件#include<stack>//要用栈保存路径信息usingnamespacestd;template<typenameType>classAVLTree;template<typenameType>classAVLNode{//AVL树的结点friendclassAVLTree<Type>;public:AVLNode():data(Type()),leftChild(NULL),rightChild(NULL),bf(0){}AVLNode(Typed,AVLNode*left=NULL,AVLNode*right=NULL):data(d),leftChild(left),rightChild(right),bf(0){}~AVLNode(){}private:Typedata;AVLNode*leftChild;AVLNode*rightChild;intbf;//多了一个平衡因子};template<typenameType>classAVLTree{//AVL树的类型public:AVLTree():root(NULL){}public:boolinsert(constType&x){returninsert(root,x);}boolremove(constType&x){returnremove(root,x);}voidinOrder()const{inOrder(root);}protected:voidinOrder(AVLNode<Type>*t)const{if(t!=NULL){inOrder(t->leftChild);cout<<t->data<<":"<<t->bf<<endl;;inOrder(t->rightChild);}}boolinsert(AVLNode<Type>*&t,constType&x);//插入函数boolremove(AVLNode<Type>*&t,constType&x);voidRotateR(AVLNode<Type>*&ptr){//右旋AVLNode<Type>*subR=ptr;ptr=ptr->leftChild;subR->leftChild=ptr->rightChild;ptr->rightChild=subR;ptr->bf=subR->bf=0;}voidRotateL(AVLNode<Type>*&ptr){//左旋AVLNode<Type>*subL=ptr;ptr=subL->rightChild;subL->rightChild=ptr->leftChild;ptr->leftChild=subL;subL->bf=ptr->bf=0;}voidRotateLR(AVLNode<Type>*&ptr){//先左后右旋转AVLNode<Type>*subR=ptr;AVLNode<Type>*subL=ptr->leftChild;ptr=subL->rightChild;subL->rightChild=ptr->leftChild;ptr->leftChild=subL;if(ptr->bf<=0){subL->bf=0;}else{subL->bf=-1;}subR->leftChild=ptr->rightChild;ptr->rightChild=subR;if(ptr->bf==-1){subR->bf=1;}else{subR->bf=0;}ptr->bf=0;}voidRotateRL(AVLNode<Type>*&ptr){//先右后左旋转AVLNode<Type>*subL=ptr;AVLNode<Type>*subR=ptr->rightChild;ptr=subR->leftChild;subR->leftChild=ptr->rightChild;ptr->rightChild=subR;if(ptr->bf>=0){subR->bf=0;}else{subR->bf=1;}subL->rightChild=ptr->leftChild;ptr->leftChild=subL;if(ptr->bf==1){subL->bf=-1;}else{subL->bf=0;}ptr->bf=0;}private:AVLNode<Type>*root;};template<typenameType>boolAVLTree<Type>::insert(AVLNode<Type>*&t,constType&x){AVLNode<Type>*p=t;AVLNode<Type>*parent=NULL;//记录前驱结点，方便连接和调整平衡因子stack<AVLNode<Type>*>st;//用栈记录插入的路径，方便调整栈中结点的平衡因子;intsign;while(p!=NULL){if(x==p->data){//要插入的数据和AVL树中的数字相同,则返回失败！returnfalse;}parent=p;st.push(parent);//找过的入栈if(x<p->data){p=p->leftChild;}elseif(x>p->data){p=p->rightChild;}}//找插入位置,不用递归，就是为了记录路径信息p=newAVLNode<Type>(x);if(parent==NULL){t=p;//判断是不是第一个结点，进行root的连接;returntrue;}if(x<parent->data){//此时通过父节点的数据判断插入的是左还是右parent->leftChild=p;}else{parent->rightChild=p;}//新插入点的bf为0,关键是栈中的平衡因子的调整///////////////////////////////////////////////////////以上完成插入工作while(!st.empty()){//栈不空，出栈顶元素parent=st.top();st.pop();if(p==parent->leftChild){//判断插入的是父节点的左/右孩子,parent->bf--;//让其bf++/--;}else{parent->bf++;}//以下判断栈中的平衡因子，看是否需要进行旋转调整if(parent->bf==0){//bf=0，直接跳出循环break;}if(parent->bf==1||parent->bf==-1){p=parent;//此时在向上走，判断bf;}else{//以下的bf为2/-2;利用标志判断左右旋;sign=parent->bf>0?1:-1;if(p->bf==sign){//符号相同为单旋if(sign==1){//为1左旋RotateL(parent);}else{RotateR(parent);//右旋}}else{//符号不同，为双旋if(sign==1){RotateRL(parent);//为1右左}else{RotateLR(parent);}}/*以下方法也可以判断左右旋else{if(parent->bf<0)//左边{if(p->bf<0&&p==parent->leftChild)///只能是左孩子{//RotateR(parent);}elseif(p->bf>0&&p==parent->leftChild)//<{//RotateLR(parent);}}else{if(p->bf>0&&p==parent->rightChild)//\{//RotateL(parent);}elseif(p->pf<0&&p==parent->rightChild)//>{//RotateRL(parent);}}}*/break;}}if(st.empty()){//通过旋转函数，此时parent指向根节点;t=parent;//此时调到栈底了，旋转后将更改root的指向}else{AVLNode<Type>*tmp=st.top();//当前的栈顶结点if(parent->data<tmp->data){tmp->leftChild=parent;}else{tmp->rightChild=parent;}}returntrue;}template<typenameType>boolAVLTree<Type>::remove(AVLNode<Type>*&t,constType&x){AVLNode<Type>*p=t;AVLNode<Type>*parent=NULL;//父结点AVLNode<Type>*q=NULL;//删除结点的辅助结点stack<AVLNode<Type>*>st;AVLNode<Type>*ppr;//爷爷结点intflag=0;while(p!=NULL){if(p->data==x){break;}parent=p;st.push(parent);if(x<p->data){p=p->leftChild;}else{p=p->rightChild;}}//以上是：查找删除点if(p==NULL){//没有要删除的结点returnfalse;}if(p->leftChild!=NULL&&p->rightChild!=NULL){parent=p;st.push(parent);q=p->leftChild;while(q->rightChild!=NULL){parent=q;st.push(parent);q=q->rightChild;}p->data=q->data;p=q;}if(p->leftChild!=NULL){q=p->leftChild;}else{q=p->rightChild;}//以上是：使其要删除的转化为只有一个分支的if(parent==NULL){//删除的是根结点，并且无入栈，代表只有一个分支，并没有寻找t=q;}else{if(parent->leftChild==p){flag=0;parent->leftChild=q;}else{flag=1;parent->rightChild=q;}while(!st.empty()){parent=st.top();st.pop();if(parent->leftChild==q){//对要删除的父节点更改bf;parent->bf++;}else{parent->bf--;}if(!st.empty()){ppr=st.top();if(ppr->leftChild==parent){flag=0;}else{flag=1;}}if(parent->bf==-1||parent->bf==1){break;//删除前的平衡因子为0，此时不用再调整其它平衡因子}if(parent->bf==0){//原先只有左孩子/右孩子q=parent;//往上回溯更改爷爷结点的bf；}else{//此时到达2,已经不平衡了，的进行旋转化的调整if(parent->bf<0){flag=-1;q=parent->leftChild;}else{flag=1;q=parent->rightChild;}if(q->bf==0){if(flag==-1){}}if(parent->bf>0){q=parent->rightChild;if(q->bf==0){RotateL(parent);}elseif(q->bf>0){RotateL(parent);}else{RotateRL(parent);}}else{q=parent->leftChild;if(q->bf==0){RotateR(parent);}elseif(q->bf<0){RotateR(parent);}else{RotateLR(parent);}}}}if(st.empty()){t=parent;//直接更改root}else{AVLNode<Type>*tmp=st.top();//当前的栈顶结点使其的左/右指向parent(是旋转化后的根);if(parent->data<tmp->data){tmp->leftChild=parent;}else{tmp->rightChild=parent;}}}deletep;//删除结点;returntrue;}#endif

(2)、测试代码

#include"avlTree.h"intmain(void){intar[]={16,3,7,11,9,26,18,14,15,};intn=sizeof(ar)/sizeof(int);AVLTree<int>avl;for(inti=0;i<n;i++){avl.insert(ar[i]);}cout<<"删除前:"<<endl;avl.inOrder();avl.remove(16);cout<<"删除后:"<<endl;avl.inOrder();return0;}

(3)、测试结果