AVL树之删除算法-白红宇

AVL树之删除算法

阅读量：5901 次

发布时间：2019-06-19

本文共 8418 字，大约阅读时间需要 28 分钟。

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
     
      bool AVLTree
      
       ::remove(AVLNode
       
         *&t, const Type &x){    AVLNode
        
          *p = t;    AVLNode
         
           *parent = NULL;  //父结点    AVLNode
          
            *q = NULL;  //删除结点的辅助结点    stack
           
            
              *> st;    AVLNode
             
               *ppr; //爷爷结点    int flag = 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){  //没有要删除的结点        return false;    }    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);                    }else if(q->bf > 0){                        RotateL(parent);                    }else{                        RotateRL(parent);                    }                }else{                    q = parent->leftChild;                    if(q->bf == 0){                        RotateR(parent);                    }else if(q->bf < 0){                        RotateR(parent);                    }else{                        RotateLR(parent);                    }                }            }        }        if(st.empty()){            t = parent;  //直接更改root        }else{            AVLNode
              
                *tmp = st.top();  //当前的栈顶结点使其的左/右指向parent(是旋转化后的根);            if(parent->data < tmp->data){                  tmp->leftChild = parent;            }else{                tmp->rightChild = parent;            }        }    }    delete p;  //删除结点;    return true;}

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

(1)完整代码

#ifndef _AVL_TREE_H_#define _AVL_TREE_H_#include
     
        //引入头文件#include
      
           //要用栈保存路径信息using namespace std;template
       
        class AVLTree;template
        
         class AVLNode{   //AVL树的结点    friend class AVLTree
         
          ;public:    AVLNode() : data(Type()), leftChild(NULL), rightChild(NULL), bf(0){}    AVLNode(Type d, AVLNode *left = NULL, AVLNode *right = NULL)         : data(d), leftChild(left), rightChild(right), bf(0){}    ~AVLNode(){}private:    Type data;    AVLNode *leftChild;    AVLNode *rightChild;    int bf;  //多了一个平衡因子};template
          
           class AVLTree{   //AVL树的类型public:    AVLTree() : root(NULL){}public:    bool insert(const Type &x){        return insert(root, x);    }    bool remove(const Type &x){        return remove(root, x);    }    void inOrder()const{        inOrder(root);    }protected:    void inOrder(AVLNode
           
             *t)const{        if(t != NULL){            inOrder(t->leftChild);            cout<
            
             data<<" : "<
             
              bf<
              
               rightChild);        }    }    bool insert(AVLNode
               
                 *&t, const Type &x); //插入函数    bool remove(AVLNode
                
                  *&t, const Type &x);    void RotateR(AVLNode
                 
                   *&ptr){  //右旋        AVLNode
                  
                    *subR = ptr;        ptr = ptr->leftChild;        subR->leftChild = ptr->rightChild;        ptr->rightChild = subR;        ptr->bf = subR->bf = 0;    }    void RotateL(AVLNode
                   
                     *&ptr){  //左旋        AVLNode
                    
                      *subL = ptr;        ptr = subL->rightChild;        subL->rightChild = ptr->leftChild;        ptr->leftChild = subL;        subL->bf = ptr->bf = 0;    }    void RotateLR(AVLNode
                     
                       *&ptr){  //先左后右旋转        AVLNode
                      
                        *subR = ptr;        AVLNode
                       
                         *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;    }    void RotateRL(AVLNode
                        
                          *&ptr){  //先右后左旋转        AVLNode
                         
                           *subL = ptr;        AVLNode
                          
                            *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
                           
                             *root;};template
                            
                             bool AVLTree
                             
                              ::insert(AVLNode
                              
                                *&t, const Type &x){    AVLNode
                               
                                 *p = t;    AVLNode
                                
                                  *parent = NULL; // 记录前驱结点，方便连接和调整平衡因子    stack
                                 
                                  
                                    *> st; //用栈记录插入的路径，方便调整栈中结点的平衡因子;    int sign;    while(p != NULL){        if(x == p->data){ //要插入的数据和AVL树中的数字相同,则返回失败！            return false;        }        parent = p;        st.push(parent); //找过的入栈        if(x < p->data){            p = p->leftChild;        }else if(x > p->data){            p = p->rightChild;        }    } // 找插入位置,不用递归，就是为了记录路径信息        p = new AVLNode
                                   
                                    (x);    if(parent == NULL){        t = p;    //判断是不是第一个结点，进行root的连接;        return true;    }    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);                }                else if(p->bf>0 && p == parent->leftChild)  //   <                {                    //RotateLR(parent);                }            }            else            {                if(p->bf>0 && p==parent->rightChild)   //   \                 {                    //RotateL(parent);                }                else if(p->pf<0 && p==parent->rightChild)  //      >                {                    //RotateRL(parent);                }            }        }*/    break;        }    }    if(st.empty()){  //通过旋转函数，此时parent指向根节点;        t = parent;  //此时调到栈底了，旋转后将更改root的指向    }else{        AVLNode
                                    
                                      *tmp = st.top();  //当前的栈顶结点        if(parent->data < tmp->data){              tmp->leftChild = parent;        }else{            tmp->rightChild = parent;        }    }    return true;}template
                                     
                                      bool AVLTree
                                      
                                       ::remove(AVLNode
                                       
                                         *&t, const Type &x){    AVLNode
                                        
                                          *p = t;    AVLNode
                                         
                                           *parent = NULL;  //父结点    AVLNode
                                          
                                            *q = NULL;  //删除结点的辅助结点    stack
                                           
                                            
                                              *> st;    AVLNode
                                             
                                               *ppr; //爷爷结点    int flag = 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){  //没有要删除的结点        return false;    }    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);                    }else if(q->bf > 0){                        RotateL(parent);                    }else{                        RotateRL(parent);                    }                }else{                    q = parent->leftChild;                    if(q->bf == 0){                        RotateR(parent);                    }else if(q->bf < 0){                        RotateR(parent);                    }else{                        RotateLR(parent);                    }                }            }        }        if(st.empty()){            t = parent;  //直接更改root        }else{            AVLNode
                                              
                                                *tmp = st.top();  //当前的栈顶结点使其的左/右指向parent(是旋转化后的根);            if(parent->data < tmp->data){                  tmp->leftChild = parent;            }else{                tmp->rightChild = parent;            }        }    }    delete p;  //删除结点;    return true;}#endif

(2)、测试代码

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

(3)、测试结果

转载于:https://blog.51cto.com/wait0804/1839312

你可能感兴趣的文章