平衡二叉查找树（AVL）的查找、插入、删除

柔光的暖阳◎ 2022-02-02 13:41 165阅读 0赞

一.平衡二叉查找树  
平衡二叉查找树是带有平衡条件的二叉查找树。平衡条件：每个节点的左子树和右子树的高度差最多为1二叉查找树（其中空树的高度为-1）。

二、平衡二叉树算法思想

若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。

失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。

当对一颗AVL树进行插入操作，可能会导致AVL树不平衡，此时，我们就需要做平衡处理，假设重新平衡的节点为Q，则不平衡会下列四种情况：

在Q的左孩子的左子树插入 （LL）

在Q的左孩子的右子树插入 （LR）

在Q的右孩子的左子树插入  （RL）

在Q的右孩子的右子树插入  （RR）  
　旋转算法需要借助于两个功能的辅助，一个是求树的高度，一个是求两个高度的最大值。这里规定，一棵空树的高度为-1，只有一个根节点的树的高度为0，以后每多一层高度加1。为了解决指针NULL这种情况，写了一个求高度的函数，这个函数还是很有必要的。

代码：

// return the height of node ptrTree or -1 if NULL;  
//只有一个根节点的高度为0，空树的高度-1  
int NodeHeight(PtrToNode  ptrTree)  
\{  
    return ptrTree==NULL ? -1 :ptrTree->height;  
\}  
int max(int a,int b)  
\{  
    return a<b ? b : a;  
\}

（1）LL型平衡旋转法

由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

对应的代码：

思路：先把B的右子树变为A的左子树，在把A作为B的右子树

//LL旋转  
void RotateWithLeft(PtrToNode &k1)  
\{  
    PtrToNode k= k1->left;  //保存节点的左子树  
    k1->left = k->right;   //k节点的右子树作为k1的左子树  
    k->right =k1;          //把k1的k的右子树  
    //到此树旋转完成，更新树的深度,以k，k1为节点的树的深度发生了变化；  
    k1->height= max(NodeHeight(k1->left),NodeHeight(k1->right))+1;  
    k->height= max(NodeHeight(k->left),NodeHeight(k->right))+1;  
    //根节点发生了变化，右k1变为了k，因为传的参数是引用，程序默认k1为根节点  
    //k为局部变量，离开作用域，变量就会销毁，因此需要返回根节点，只不过是通过引用的方式罢了；  
    k1=k;  
\}

（2）RR型平衡旋转法

由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。

思路：先把C的左子树作为A的右子树，在把A作为C的左子树。

代码：

void RotateWithRight(PtrToNode &k2)  
\{  
    PtrToNode k= k2->right;  //保存节点的右子树  
    k2->right=k->left;  
    k->left=k2;  
    //到此树旋转完成，更新树的深度,以k，k1为节点的树的深度发生了变化；  
    k2->height= max(NodeHeight(k2->left),NodeHeight(k2->right))+1;  
    k->height= max(NodeHeight(k->left),NodeHeight(k->right))+1;  
    //根节点发生了变化，右k1变为了k，因为传的参数是引用，程序默认k1为根节点  
    //k为局部变量，离开作用域，变量就会销毁，因此需要返回根节点，只不过是通过引用的方式罢了；  
    k2=k;  
\}

（3）LR型平衡旋转法

由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。

如图中所示，先将圈圈的部分进行逆时针旋转（RR旋转），使之转换为LL型，再进行LL旋转；（双旋转）

代码：

void DoubleRotateWithLeft(PtrToNode &k3)  
\{  
    RotateWithRight(k3->left);  
    RotateWithLeft(k3);  
\}

（4）RL型平衡旋转法

由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。

如图中所示，先将圈圈的部分进行顺时针旋转（LL旋转），使之转换为RR型，再进行RR旋转；（双旋转）

代码：

void DoubleRotateWithRight(PtrToNode &k3)  
\{  
    RotateWithLeft(k3->right);  
    RotateWithRight(k3);  
\}

三、AVL的查找、删除、插入  
1.AVL树的类型声明

//平衡二叉树的结构体  
typedef int elementType;  
typedef struct AVLNODE   
\{  
    elementType data;  
    struct AVLNODE \* left;  
    struct AVLNODE \* right;  
    int height;  //以此节点为根，树的高度；  
    unsigned int freq;//此节点保存的数据出现的频率  
\}AvlNode,\*PtrToNode;</span>

2.插入  
AVL树的插入和二叉查找树的插入相似，只是AVL树的插入可能会破坏树的平衡性。对AVL树而言，插入完成后，需要判断树的平衡性是否被破坏，然后进行相应的旋转处理使之成为平衡树。

（1）左平衡处理  
所谓左平衡处理，就是某一根结点的左子树比右子树过高，从而失去了平衡。在节点的左子树进行插入操作使此节点失去平衡，需要左平衡处理。

//左平衡处理  
void LeftBalance(PtrToNode &node)  
\{  
    PtrToNode ptrTmp=node->left;  
    if(NodeHeight(ptrTmp->left)-NodeHeight(ptrTmp->right)==-1)   
    \{  
             //右子树高于左子树，在右子树插入的  
        DoubleRotateWithLeft(node); //LR  
    \}  
    else  
    \{      
        RotateWithLeft(node); //LL  
    \}  
\}

需要判断是在失去平衡的节点的左孩子的左子树还右子树进行插入的，左子树插入（LL旋转），右子树插入（LR旋转）。  
（2）右平衡处理  
类似左平衡处理，所谓右平衡处理，就是某一根结点的右子树比左子树过高，从而失去了平衡。

//右平衡处理  
void RightBalance(PtrToNode &node)  
\{  
    PtrToNode ptrTmp=node->right;  
    if(NodeHeight(ptrTmp->right)-NodeHeight(ptrTmp->left)==-1)  
    \{  //左子树比右子树高，说明在左子树插入的  
        DoubleRotateWithRight(node); //RL  
    \}  
    else  
    \{  
        RotateWithRight(node);  //RR  
    \}  
\}

需要判断是在失去平衡的节点的右孩子的左子树还右子树进行插入的，左子树插入（RL旋转），右子树插入（RR旋转）。  
(3) 插入函数的编写

void AVL\_Insert(PtrToNode &node,elementType x)  
\{  
    if(NULL==node) //找到插入的节点的位置  
    \{  
        node =(struct AVLNODE \*) malloc(sizeof(struct AVLNODE ));  
        node->data=x;  
        node->height=0;  
        node->freq = 1;  
        node->left=NULL;  
        node->right=NULL;  
    \}  
    else if(x<node->data)  //在左子树插入  
    \{  
        AVL\_Insert(node->left,x);  
        //判断是否破坏AVL树的平衡性  
        if (NodeHeight(node->left)-NodeHeight(node->right)==2)   
            LeftBalance(node);  //左平衡处理  
        \}  
    else if(node->data<x)   //在右子树插入  
    \{  
        AVL\_Insert(node->right,x);  
        //判断是否破坏AVL树的平衡性  
        if (NodeHeight(node->right)-NodeHeight(node->left)==2)   
            RightBalance(node); //右平衡处理  
   
    \}  
    else  
    \{node->freq++;\}  
   
    node->height = max(NodeHeight(node->left),NodeHeight(node->right)) +1 ;  //跟新树的高度  
          
\}

2. 查找  
由于AVL树是有序的二叉查找树，要查找的元素比节点的数据大，则在右子树查找；比节点的数据小，在左子树中查找；与节点的数据相等，返回该节点。

PtrToNode AVL\_Find(PtrToNode & node,elementType x)  
\{  
    if (node==NULL)  //没找到元素  
    \{  
        return NULL;  
    \}  
    else if(x<node->data)  
    \{  
        return AVL\_Find(node->left,x); //在左子树里面查找  
    \}  
    else if(node->data<x)  
    \{  
        return AVL\_Find(node->right,x); //在右子树里面查找  
    \}  
    else //相等  
        return node;  
\}

3.删除  
对二叉查找树，我们知道删除的结点可能有三种情况：(1)为叶子结点，(2)左子树或右子树有一个为空，(3)左右子树都不空。假设删除节点为A。

对于（1）：直接删除即可。

对于（2）：删除的方法，A的父节点绕过A节点使其指向A左子树（右子树为空）、右子树（左子树为空时）。

对于（3）：一般的删除策略：用A的左子树最大数据或右子树最小数据（假设B节点）代替A节点的数据，并递归地删除B节点。

AVL的树的删除策略与二叉查找树的删除策略相似，只是删除节点后造成树失去平衡性，需要做平衡处理。

void AVL\_Delete(PtrToNode &node,elementType x)  
\{  
    if(NULL==node)  //空树直接返回  
        return;  
    if(x<node->data)  //在左子树中查找  
    \{  
         AVL\_Delete(node->left,x);      
         if(NodeHeight(node->right)-NodeHeight(node->left)==2)  //树左平衡处理  
          RightBalance(node);  
    \}  
    else if(node->data<x)  //在右子树中查找  
    \{  
        AVL\_Delete(node->right,x);  
         if(NodeHeight(node->left)-NodeHeight(node->right)==2)  //树右平衡处理  
          LeftBalance(node);  
    \}  
    else //找到要删除的元素节点  
    \{  
        if(node->left==NULL) //左子树为空  
        \{  
            PtrToNode ptrTmp = node;  
            node=node->right;         //用右孩子代替此节点  
            free(ptrTmp);            //释放内存  
        \}  
        else if(node->right==NULL)  //右子树为空  
        \{  
            PtrToNode ptrTmp = node;  
            node=node->left;       //用左孩子代替此节点  
            free(ptrTmp);   
        \}  
        else   //左右子树都不为空  
        \{  
            //一般的删除策略是左子树的最小数据 或 右子树的最小数据 代替该节点  
            PtrToNode ptrTmp=node->left;  //从左子树中查找  
            while(ptrTmp->right!=NULL)  ptrTmp=ptrTmp->right;  
            //此时的ptrTmp指向左子树中的最大元素  
            node->data =  ptrTmp->data;  
            AVL\_Delete(node->left,ptrTmp->data);  //递归的删除该节点  
        \}  
    \}  
   
    //更新节点的高度  
    if(node)  
        node->height = max(NodeHeight(node->left),NodeHeight(node->right));  
\}

4.遍历打印输出（中序）  
//中序遍历  
void print(PtrToNode & root)    
\{    
    if (NULL == root)     
    \{    
        return ;    
    \}   
    print(root->left);  
    printf("%d ",root->data);   
    print(root->right);         
\}

5.测试代码

int main()  
\{  
    //C++引入的引用概念，可以直接对树的节点进行插入操作，而不用返回树的根节点  
    PtrToNode root =NULL;  
/\*    for(int i=0;i<5;i++)  
    \{  
        AVL\_Insert(root,i);  
    \}  
    \*/  
    AVL\_Insert(root,4);  
    AVL\_Insert(root,2);  
    AVL\_Insert(root,6);  
    AVL\_Insert(root,1);  
    AVL\_Insert(root,3);  
    AVL\_Insert(root,5);  
    AVL\_Insert(root,7);  
    AVL\_Insert(root,16);  
    AVL\_Insert(root,15);  
    print(root);  
   
    printf("\\n%d\\n",root->height);  
    AVL\_Delete(root,15);  
    AVL\_Delete(root,5);  
    print(root);  
    PtrToNode y=AVL\_Find(root,15);  
    if (y==NULL)  
    \{  
        printf("没有查找到15\\n");  
    \}  
    else  
    \{  
        printf("所在节点的高度：%d\\n",y->height);  
        if (NULL!=y->left)  
        \{  
            printf("所在节点的左孩子：%d\\n",y->left->data);  
        \}  
        if (NULL!=y->right)  
        \{  
            printf("所在节点的右孩子：%d\\n",y->right->data);  
        \}  
          
    \}  
\}

平衡二叉树性能分析

平衡二叉树的性能优势：

很显然，平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。

平衡二叉树的缺陷：

(1) 很遗憾的是，为了保证高度平衡，动态插入和删除的代价也随之增加。红黑树是更加高效的查找结构。

(2) 所有二叉查找树结构的查找代价都与树高是紧密相关的，能否通过减少树高来进一步降低查找代价呢。我们可以通过多路查找树的结构来做到这一点。

(3) 在大数据量查找环境下(比如说系统磁盘里的文件目录，数据库中的记录查询 等)，所有的二叉查找树结构(BST、AVL、RBT)都不合适。如此大规模的数据量（几G数据），全部组织成平衡二叉树放在内存中是不可能做到的。那么把这棵树放在磁盘中吧。问题就来了：假如构造的平衡二叉树深度有1W层。那么从根节点出发到叶子节点很可能就需要1W次的硬盘IO读写。大家都知道，硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。 查找效率在IO读写过程中将会付出巨大的代价。在大规模数据查询这样一个实际应用背景下，平衡二叉树的效率就很成问题了。

上面提到的红黑树和多路查找树都是属于深度有界查找树（depth-bounded tree —DBT）

源代码：  
http://download.csdn.net/detail/lpp0900320123/7935897  
\---------------------   
作者：lpp0900320123   
来源：CSDN   
转自：https://blog.csdn.net/lpp0900320123/article/details/39367451