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

平衡二叉树

平衡 二叉树介绍

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

平衡二叉树的实现原理

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

旋转图解

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

对树节点进行左右旋转

下面2图是最基本的左右旋转，理解后，对应的旋转代码就好理解了。

这里写图片描述

双旋转的情况

让其左平衡，进行右旋转，让其右平衡进行左旋转。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在进行右旋转。

结合代码很好看明白。

左平衡情况

这里写图片描述

右平衡情况

这里写图片描述

实现代码

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

#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;
}

文章最后发布于: 2018-04-28 17:36:54

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