平衡二叉树（AVL）的实现

干翻全岛蛙蛙  金牌会员 | 2022-9-16 17:21:03 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 886|帖子 886|积分 2658

平衡二叉树概念

平衡二叉排序树（Balanced Binary Tree），因由前苏联数学家Adelson-Velskii 和
Landis于1962年首先提出的，所以又称为AVL树。
平衡二叉树是一种特殊的二叉排序树，理解平衡二叉树首先要理解什么是二叉排序树。
如果已经了解二叉排序树可以直接看下面平衡二叉树内容。
二叉排序树（Binary Sort Tree）

所谓二叉排序树(BST)即：
（1）若该树的左子树不为空，那么左子树所以结点的值均小于其根结点的值。
（2）若该树的右子树不为空，那么右子树所以结点的值均大于其根结点的值。
（3）该树的左右子树也均为二叉排序树。
依此定义，我们可以通过比较根结点的值一层层地定位到所要查找的值。
例：如下图是一棵二叉排序树

比如我们要查找7，那么先从根结点开始比较，8>7查找左子树 ----> 3</strong> 6>7查找右子树 ----> 最后7=7，找到了7。
这种查找算法与折半查找相似，也是逐步缩小搜索范围。
若中序遍历上图，则可以得到一个按数值大小排序的递增序列：1，3，4，6，7，8，10，13，15。
二叉排序树的储存结构
  1. typedef struct BSTNode
  2. {
  3.         int data=0;//数据项
  4.         struct BSTNode *lchild=NULL,*rchild=NULL;//左右子树
  5. }BSTNode,*BSTree.
复制代码
二叉排序树的查找算法（递归查找）

BSTree T 为二叉树根节点 ，int e 为查找的关键字。时间复制度为O(log2 n)。
  1. int searchTree(BSTree T,int e)//在二叉树中查找给定关键字(函数返回值为成功1,失败0)
  2. {
  3.     if (T==NULL)//无法查找到给定关键字
  4.     {
  5.         return 0;
  6.     }else if (e==T->data)//查找到关键字
  7.     {
  8.         return 1;
  9.     }else if (e<T->data)//小于根结点，向左子树查找
  10.     {
  11.         return searchTree(T->lchild,e);
  12.     }else if(e>T->data)//大于根结点，向右子树查找
  13.     {
  14.         return searchTree(T->rchild,e);
  15.     }
  16. }
复制代码
二叉排序树的创建及插入（递归）

二叉排序树的插入算法基本过程也是查找，时间复制度也为O(log2 n)。
  1. void InsertBST(BSTree &T,int e)//插入节点，根据节点值的大小插入
  2. {//当二叉排序树中不存在关键字等于e的结点时，查找结束，插入结点
  3.     if (!T)//查找到插入位置
  4.     {
  5.         BSTNode *S; //生成新结点
  6.         S=new BSTNode;
  7.         S->data=e;//给新结点赋值
  8.         S->lchild=S->rchild=NULL;//将新结点作为叶子结点
  9.         T=S;//给查找到的插入位置赋值
  10.     }
  11.     else if (e<T->data)
  12.     {
  13.         InsertBST(T->lchild,e);//向左查找插入
  14.     }else if (e>T->data)
  15.     {
  16.         InsertBST(T->rchild,e);//向右查找插入
  17.     }
  18. }
  19. void CreatBST(BSTree &T)//创建二叉树
  20. {
  21.     T=NULL;
  22.     int e,n,i;
  23.     scanf("%d",&n);
  24.     for (i=0;i<n;i++)
  25.     {
  26.         scanf("%d",&e);
  27.         InsertBST(T,e);
  28.     }
  29. }
复制代码
平衡二叉树的创建及调整方法

如何创建一棵平衡二叉树呢？
简单的来说就是：
（1）先按照我们创建二叉排序树的方法，找到结点插入位置，将结点插入二叉树中。
（2）然后我们来计算该插入结点父结点的平衡因子， 如果平衡因子绝对值大于1，代表该子树是不平衡的，那么对该子树进行调整，将其调整为平衡二叉树， 然后一层一层往上计算平衡因子和进行调整，直到根节点（根结点平衡因子绝对值大于1也要调整），最终把整棵树调整为平衡二叉树。
（3）第三步就重复上面操作，把一个一个结点插入二叉树中并进行调整，最终插入完所有结点并创建完成平衡二叉树。

平衡二叉树的调整

平衡二叉树的调整有4种调整情况。
这里有一篇写得比较好的文章可以参考一下：平衡二叉树（AVL）图解与实现-zthgreat
LL型

(a) 图a中我们插入“16” 后计算平衡因子发现结点“31”的平衡因子为2，该树为非平衡树，需要进行调整，我们以结点“25”为旋转中心，将其父结点按顺时针旋转为其右子树，至此该树调整完毕。
注意：25的左结点16不进行旋转。
(b) 图b中我们插入“9”后计算平衡因子发现结点“31”的平衡因子为2，该树为非平衡树，需要进行调整，我们以结点“25”为旋转中心，将其父结点“31”按顺时针旋转为其右子树，再把旋转中心“25”的右子树调整为31的左子树，至此该树调整完毕。

   我们总结出以下规律（参考下图）：将B结点作为根结点，A结点旋转为B结点的右子树，再把B结点本来的右子树连接为A结点的左子树，该树调整完成。

代码实现：
  1. typedef struct AVLNode
  2. {
  3.     int data=0;//结点值
  4.     int depth=0;//深度，方便通过计算左右子树深度之差得到该结点的平衡因子
  5.     struct AVLNode *father=NULL;//父结点
  6.     struct AVLNode *lchild=NULL,*rchild=NULL;//左右结点
  7. } AVLNode,*AVLTree; //结点结构体
复制代码
RR型


(a) 图a中我们插入“69” 后计算平衡因子发现结点“31”的平衡因子为-2，该树为非平衡树，需要进行调整，我们以结点“47”为旋转中心，将其父结点按逆时针旋转为其左子树，至此该树调整完毕。
注意：47的右结点69不进行旋转。
(b) 图b中我们插入“76”后计算平衡因子发现结点“31”的平衡因子为2，该树为非平衡树，需要进行调整，我们以结点“47”为旋转中心，将其父结点“31”按逆时针旋转为其左子树，再把旋转中心“47”的左子树调整为31的右子树，至此该树调整完毕。
   我们总结出以下规律（参考下图）：将B结点作为根结点，A结点旋转为B结点的左子树，再把B结点本来的左子树连接为A结点的右子树，该树调整完成。
   可以看到LL型调整和RR型是左右相反的调整。

代码实现：
  1. int count_depth(AVLTree &T)//计算各结点的深度
  2. {
  3.     if(T==NULL)
  4.     {
  5.         return 0;
  6.     }
  7.     else
  8.     {
  9.         int l=count_depth(T->lchild);//左子树深度
  10.         int r=count_depth(T->rchild);//右子树深度
  11.         return T->depth=max(l,r)+1;//更新深度
  12.     }
  13. }
  15. int get_balance(AVLTree T)//读取深度
  16. {
  17.     if(T)
  18.     {
  19.         return T->depth;
  20.     }
  21.     else
  22.     {
  23.         return 0;
  24.     }
  25. }
  27. int count_balance(AVLTree T)//计算平衡因子
  28. {
  29.     if(!T)
  30.     {
  31.         return 0;
  32.     }
  33.     else
  34.     {
  35.         return get_balance(T->lchild)-get_balance(T->rchild);//平衡因子等于左右子树的深度之差
  36.     }
  37. }
复制代码
(3) LR型


(a) 图a中我们插入“28” 后计算平衡因子发现结点“31”的平衡因子为2，该树为非平衡树，需要进行调整。
(1)我们对25和28进行RR型旋转调整以结点“28”为旋转中心，将其父结点25按逆时针旋转为其左子树，再连接为31的左子树。
(2)观察到调整后的树是LL型，故以结点“28”为旋转中心，将其父结点31按顺时针旋转为其右子树，调整完毕。

(b) 图b中我们插入“26” 后计算平衡因子发现结点“31”的平衡因子为2，该树为非平衡树，需要进行调整。
(1)我们对25和28进行RR型旋转调整以结点“28”为旋转中心，将其父结点25按逆时针旋转为其左子树，“28”的左子树“26”连接为“25”的右子树，再将"28"连接为"31"的左子树。
(2)观察到调整后的树是LL型，故以结点“28”为旋转中心，将其父结点31按顺时针旋转为其右子树，调整完毕。

(c)图b中我们插入“30” 后计算平衡因子发现结点“31”的平衡因子为2，该树为非平衡树，需要进行调整。
(1)我们对25和28进行RR型旋转调整以结点“28”为旋转中心，将其父结点25按逆时针旋转为其左子树，再将"28"连接为"31"的左子树。
(2)观察到调整后的树是LL型，故以结点“28”为旋转中心，将其父结点31按顺时针旋转为其右子树，再将“28”（旋转中心）的右子树“30”连接为“31”的左子树，调整完毕。

  我们总结出以下规律（参考下图）：LR型先对B,C进行RR型旋转(以B为旋转中心)，旋转后就变成LL型的非平衡树之后再对A，B，C进行LL型旋转调整(以B为旋转中心)。

代码实现：
  1. AVLTree LL_rotate(AVLTree T)
  2. {
  3.     AVLTree parent=NULL,son;//son结点即为旋转中心
  4.     parent=T->father;//获取失衡结点的父节点
  5.     son=T->lchild;//获取失衡结点的左孩子
  6.     if (son->rchild!=NULL)//设置son结点右孩子的父指针
  7.         son->rchild->father=T;
  8.     T->lchild=son->rchild;//失衡结点的左孩子变更为son的右孩子
  9.     //T的子结点更新完毕
  10.     count_depth(T);//更新失衡结点的深度信息
  11.     son->rchild=T;//失衡结点变成son的右孩子
  12.     son->father=parent;//设置son的父结点为原失衡结点的父结点，连接整颗树
  13.     //如果失衡结点不是根结点，则更新父节点
  14.     if (parent!=NULL)
  15.     {
  16.         //如果父节点的左孩子是失衡结点，指向现在更新后的新孩子son
  17.         if (parent->lchild==T)
  18.             parent->lchild=son;
  19.         else //父节点的右孩子是失衡结点
  20.             parent->rchild=son;
  21.     }
  22.     T->father=son;//设置失衡结点的父亲
  23.     count_depth(son);//更新son结点的高度信息
  24.     return son;
  25. }
复制代码
(4) RL型


RL型就与LR型相反，先进行LL型旋转，再进行RR型旋转。如（a）图的旋转。

  我们总结出以下规律（参考下图）：RL型先对B,C进行LL型旋转(以B为旋转中心)，旋转后就变成RR型的非平衡树之后再对A，B，C进行RR型旋转调整(以B为旋转中心)。

代码实现：
  1. AVLTree RR_rotate(AVLTree T)
  2. {
  3.     AVLTree parent=NULL,son;//son结点即为旋转中心
  4.     parent=T->father;//获取失衡结点的父节点
  5.     son=T->rchild;//获取失衡结点的右孩子
  6.     if (son->lchild!=NULL)//设置son结点左孩子的父指针
  7.         son->lchild->father=T;
  8.     T->rchild=son->lchild;//失衡结点的右孩子变更为son的左孩子
  9.     //T的子结点更新完毕
  10.     count_depth(T);//更新失衡结点的高度信息
  11.     son->lchild=T;//失衡结点变成son的右孩子
  12.     son->father=parent;//设置son的父结点为原失衡结点的父结点，连接整颗树
  13.     //如果失衡结点不是根结点，则更新父节点
  14.     if (parent!=NULL)
  15.     {
  16.         //如果父节点的左孩子是失衡结点，指向现在更新后的新孩子son
  17.         if (parent->lchild==T)
  18.             parent->lchild=son;
  19.         else //父节点的右孩子是失衡结点
  20.             parent->rchild=son;
  21.     }
  22.     T->father=son;//设置失衡结点的父亲
  23.     count_depth(son);//更新son结点的高度信息
  24.     return son;
  25. }
复制代码
平衡二叉树的创建

了解完了如何调整非平衡二叉树，剩下工作就比较简单了，无非是在创建二叉排序树时，每次插入结点，把二叉树调整为平衡二叉树。
下面是代码实现：
输入数据
  1. AVLTree LR_rotate(AVLTree T)
  2. {
  3.     RR_rotate(T->lchild);
  4.     return LL_rotate(T);
  5. }
复制代码
调整平衡二叉树
  1. AVLTree RL_rotate(AVLTree T)
  2. {
  3.     LL_rotate(T->rchild);
  4.     return RR_rotate(T);
  5. }
复制代码
平衡二叉树实现的整体代码

[code]#include "stdio.h"#include "malloc.h"#include #include #include using namespace std;typedef struct AVLNode{    int data=0;//结点值    int depth=0;//深度    struct AVLNode *father=NULL;//父结点    struct AVLNode *lchild=NULL,*rchild=NULL;//左右结点} AVLNode,*AVLTree; //结点结构体int count_depth(AVLTree &T)//计算各结点的深度{    if(T==NULL)    {        return 0;    }    else    {        int l=count_depth(T->lchild);//左子树深度        int r=count_depth(T->rchild);//右子树深度        return T->depth=max(l,r)+1;//更新深度    }}int get_balance(AVLTree T)//读取深度{    if(T)    {        return T->depth;    }    else    {        return 0;    }}int count_balance(AVLTree T)//计算平衡因子{    if(!T)    {        return 0;    }    else    {        return get_balance(T->lchild)-get_balance(T->rchild);//平衡因子等于左右子树的深度之差    }}typedef struct AVLNode
{
    int data=0;//结点值
    int depth=0;//深度，方便通过计算左右子树深度之差得到该结点的平衡因子
    struct AVLNode *father=NULL;//父结点
    struct AVLNode *lchild=NULL,*rchild=NULL;//左右结点
} AVLNode,*AVLTree; //结点结构体int count_depth(AVLTree &T)//计算各结点的深度
{
    if(T==NULL)
    {
        return 0;
    }
    else
    {
        int l=count_depth(T->lchild);//左子树深度
        int r=count_depth(T->rchild);//右子树深度
        return T->depth=max(l,r)+1;//更新深度
    }
}

int get_balance(AVLTree T)//读取深度
{
    if(T)
    {
        return T->depth;
    }
    else
    {
        return 0;
    }
}

int count_balance(AVLTree T)//计算平衡因子
{
    if(!T)
    {
        return 0;
    }
    else
    {
        return get_balance(T->lchild)-get_balance(T->rchild);//平衡因子等于左右子树的深度之差
    }
}AVLTree LL_rotate(AVLTree T)
{
    AVLTree parent=NULL,son;//son结点即为旋转中心
    parent=T->father;//获取失衡结点的父节点
    son=T->lchild;//获取失衡结点的左孩子
    if (son->rchild!=NULL)//设置son结点右孩子的父指针
        son->rchild->father=T;
    T->lchild=son->rchild;//失衡结点的左孩子变更为son的右孩子
    //T的子结点更新完毕
    count_depth(T);//更新失衡结点的深度信息
    son->rchild=T;//失衡结点变成son的右孩子
    son->father=parent;//设置son的父结点为原失衡结点的父结点，连接整颗树
    //如果失衡结点不是根结点，则更新父节点
    if (parent!=NULL)
    {
        //如果父节点的左孩子是失衡结点，指向现在更新后的新孩子son
        if (parent->lchild==T)
            parent->lchild=son;
        else //父节点的右孩子是失衡结点
            parent->rchild=son;
    }
    T->father=son;//设置失衡结点的父亲
    count_depth(son);//更新son结点的高度信息
    return son;
}AVLTree RR_rotate(AVLTree T)
{
    AVLTree parent=NULL,son;//son结点即为旋转中心
    parent=T->father;//获取失衡结点的父节点
    son=T->rchild;//获取失衡结点的右孩子
    if (son->lchild!=NULL)//设置son结点左孩子的父指针
        son->lchild->father=T;
    T->rchild=son->lchild;//失衡结点的右孩子变更为son的左孩子
    //T的子结点更新完毕
    count_depth(T);//更新失衡结点的高度信息
    son->lchild=T;//失衡结点变成son的右孩子
    son->father=parent;//设置son的父结点为原失衡结点的父结点，连接整颗树
    //如果失衡结点不是根结点，则更新父节点
    if (parent!=NULL)
    {
        //如果父节点的左孩子是失衡结点，指向现在更新后的新孩子son
        if (parent->lchild==T)
            parent->lchild=son;
        else //父节点的右孩子是失衡结点
            parent->rchild=son;
    }
    T->father=son;//设置失衡结点的父亲
    count_depth(son);//更新son结点的高度信息
    return son;
}AVLTree RL_rotate(AVLTree T)
{
    LL_rotate(T->rchild);
    return RR_rotate(T);
}AVLTree InsertAVL(AVLTree &T,int e,AVLTree parent){    if (!T)//找到结点插入位置    {        AVLNode *S;        S=new AVLNode;        S->data=e;        S->father=parent;        S->lchild=S->rchild=NULL;        T=S;        return S;    }    else if (edata)//向左搜索    {        return InsertAVL(T->lchild,e,T);    }    else if (e>T->data)//向右搜索    {        return InsertAVL(T->rchild,e,T);    }    return NULL;//该结点已存在}AVLTree Insert(AVLTree &T,int e){    AVLNode *S;    S=new AVLNode;    S=InsertAVL(T,e,NULL);//插入结点    count_depth(T);//更新深度信息    T=AVLchange(T,S);//调整为平衡二叉树    return T;}void creativetree(AVLTree &T){    T=NULL;    int e,n,i;    scanf("%d",&n);    for (i=0; i

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

干翻全岛蛙蛙

金牌会员
这个人很懒什么都没写!

楼主热帖

标签云

挺好的 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表