数据结构与算法——图解平衡二叉树及代码实现

女爷i 2022-05-26 09:35 46阅读 0赞

# 平衡二叉树介绍 #

**平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差最多等于1**。由3位科学家共同发明，用他们首字母命名 又被称为**AVL树**。从平衡二叉树的名称，你也可以体会到它是一种高度平衡的二叉排序树。我们将**二叉树上结点的左子树深度减去右子树的深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只能是-1,0,1**。

# 平衡二叉树的实现原理 #

平衡二叉树构建的***基本思想***就在在**构建二叉排序树的过程中**，**每当插入一个结点时**，先**检查**否是因为插入而破坏了树的平衡性，若是，这找出**最小不平衡树**，在满足二叉排序树的特点，**将其调整成新的平衡二叉树**。

# 旋转图解 #

在理解平衡二叉树代码之前，我们得理解树的旋转，在下面的一系列图中，**字母并无实际意义不代表其数据域，就是一个标识，但是要想着他们都是满足二叉排序的特性，在这个特性之上进行旋转**。

## 对树节点进行左右旋转 ##

下面2图是最基本的左右旋转，理解后，对应的旋转代码就好理解了。  
![这里写图片描述][70]  
![这里写图片描述][70 1]

## 双旋转的情况 ##

**让其左平衡，进行右旋转，让其右平衡进行左旋转**。T代表要旋转的树节点，L = T->lchild，Lr = L-rchild;R = T->rchild,Rl = R->lchild;  
但是要注意下面情况：  
某个树节点T插入结点后，如果其左不平衡bf > 0，我们通过旋转让其左平衡。此时，其 L 左孩子的 bf 会影响如何旋转，如果L->bf = 1 同 T 方向一致，这是最简单的情况，只需将T进行右旋转。右平衡也是一样的道理。如果L->bf 和 T的方向不一致，那么就要先通过左旋转 让T->lchild和 T的方向一致，T在进行右旋转。  
结合代码很好看明白。

### 左平衡情况 ###

![这里写图片描述][70 2]  
![这里写图片描述][70 3]  
![这里写图片描述][70 4]  
![这里写图片描述][70 5]

### 右平衡情况 ###

![这里写图片描述][70 6]  
![这里写图片描述][70 7]  
![这里写图片描述][70 8]  
![这里写图片描述][70 9]

# 实现代码 #

下面主要是平衡二叉树的插入算法，平衡二叉树的主要算法也就是插入算法。它的删除和查找同二叉排序树是一样的这里就多写了，有兴趣可以看数据结构与算法——二叉排序树详解以及代码实现。

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct BiTNode
    {
        int data;
        int bf;
        struct BiTNode* lchild, *rchild;
    }BiTNode, *BiTree;
    typedef enum{
       false,true}bool;
    //左旋转
    void L_Rotate(BiTree *T)
    {
        BiTree R = (*T)->rchild;
        (*T)->rchild = R->lchild;
        R->lchild = *T;
        *T = R;
        return;
    }
    //右旋转
    void R_Rotate(BiTree *T)
    {
        BiTree L = (*T)->lchild;
        (*T)->lchild = L->rchild;
        L->rchild = *T;
        *T = L;
        return;
    }
    #define LH +1
    #define EH 0
    #define RH -1
    //T 的左边高，不平衡，使其平衡，右旋转，右旋转前先检查L->bf，
    //如果为RH，L要先进行左旋转，使T->lchild->bf和T->bf一致
    void LeftBalance(BiTree* T)
    {
        BiTree L,Lr;
        L = (*T)->lchild;
        Lr = L->rchild;
        switch (L->bf)
        {
            case LH:
                L->bf = (*T)->bf =  EH;
                R_Rotate(T);
                break;
            case RH:
                switch (Lr->bf)
                {
                    case LH:
                        L->bf = EH;
                        (*T)->bf = RH;
                        break;
                    case EH:
                        L->bf = (*T)->bf = EH;
                        break;
                    case RH:
                        L->bf = LH;
                        (*T)->bf = EH;
                        break;
                }
                Lr->bf = EH;
                L_Rotate(&L);
                R_Rotate(T);
                break;
        }
    }
    //T 的右边高，不平衡，使其平衡，左旋转，左旋转前先检查R->bf,
    //如果为LH，R要先进行右旋转，使T->rchild->bf和T->bf一致
    void RightBalance(BiTree* T)
    {
        BiTree R,Rl;
        R = (*T)->rchild;
        Rl = R->lchild;
        switch(R->bf)
        {
            case RH:
                R->bf = (*T)->bf = EH;
                L_Rotate(T);
                break;
            case LH:
                switch(R->bf)
                {
                    case LH:
                        R->bf = RH;
                        (*T)->bf = EH;
                        break;
                    case EH:
                        R->bf = (*T)->bf = EH;
                        break;
                    case RH:
                        R->bf = EH;
                        (*T)->bf = LH;
                        break;
                }
                Rl->bf = EH;
                R_Rotate(&R);
                L_Rotate(T);
                break;
        }
    }
    //往平衡二叉树上插入结点
    bool InsertAVL(BiTree* T,int data,bool *taller)
    {
        if(*T == NULL)  //找到插入位置
        {
            *T = (BiTree)malloc(sizeof(BiTNode));   
            (*T)->bf = EH;
            (*T)->rchild = (*T)->lchild = NULL;
            (*T)->data = data; 
            *taller = true;
        }
        else
        {
            if(data == (*T)->data) //树中有相同的结点数据直接返回 { *taller = false; return false; } if(data < (*T)->data) //往左子树搜索进行插入 { if(!InsertAVL(&(*T)->lchild,data,taller)) //树中有相同的结点 { *taller = false; return false; } if (*taller) { switch ((*T)->bf) //T插入结点后，检测平衡因子，根据情况，做相应的修改和旋转 { case LH: LeftBalance(T); //插入后左边不平衡了，让其左平衡 *taller = false; break; case EH: (*T)->bf = LH;
                        *taller = true;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        *taller = false;
                        break;
                    }
                }
            }
            else                    //往右子树搜索进行插入
            {
                if(!Insert(&(*T)->rchild),data,taller) //树中有相同的结点 { *taller = false; return false; } if (*taller) //插入到右子树中且长高了 { switch ((*T)->bf) //T插入结点后，检测平衡因子，根据情况，做相应的修改和旋转 { case LH: (*T)->bf = EH;
                        *taller = false;
                        break;
                    case EH:
                        (*T)->bf = RH;
                        *taller = true;
                        break;
                    case RH:
                        R_Balance(T);                       //插入后右边不平衡了，让其右平衡
                        *taller = false;
                        break;
                    }
                }
            }
        }
        return true;
    }

[70]: /images/20220526/24f3dec4871d412590c9ca54dd3d021c.png
[70 1]: /images/20220526/c2886457d68f4871beb6883821f0792b.png
[70 2]: /images/20220526/0a954c793778426f9ca621de9bcda5fd.png
[70 3]: /images/20220526/65ce27fc15a9413d89ba8f1626c6b39e.png
[70 4]: /images/20220526/d2c3c878981342be925802ea38b30395.png
[70 5]: /images/20220526/11ea749e2c7c4528b35bd71adfb8a0d1.png
[70 6]: /images/20220526/96b93cfbf56f413687c24b9463d635bd.png
[70 7]: /images/20220526/1075384007c44b8696e0b74b813325d2.png
[70 8]: /images/20220526/21d7886a07c943e88395b7b1dfe04060.png
[70 9]: /images/20220526/16ebca5d39254315a763fc1264e5efbe.png