首页 > 其他分享 >平衡二叉树（AVL）的实现

平衡二叉树（AVL）的实现

时间：2022-08-25 09:44:44浏览次数：81  
标签：lchild 结点 AVLTree son AVL 二叉树 平衡

平衡二叉树概念

平衡二叉排序树（Balanced Binary Tree），因由前苏联数学家Adelson-Velskii 和
Landis于1962年首先提出的，所以又称为AVL树。

平衡二叉树是一种特殊的二叉排序树，理解平衡二叉树首先要理解什么是二叉排序树。
如果已经了解二叉排序树可以直接看下面平衡二叉树内容。

二叉排序树（Binary Sort Tree）

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

例：如下图是一棵二叉排序树

比如我们要查找7，那么先从根结点开始比较，8>7查找左子树 ----> 3<7查找右子树 ----> 6>7查找右子树 ----> 最后7=7，找到了7。
这种查找算法与折半查找相似，也是逐步缩小搜索范围。
若中序遍历上图，则可以得到一个按数值大小排序的递增序列：1，3，4，6，7，8，10，13，15。

二叉排序树的储存结构

typedef struct BSTNode
{
	int data=0;//数据项
	struct BSTNode *lchild=NULL,*rchild=NULL;//左右子树
}BSTNode,*BSTree.

二叉排序树的查找算法（递归查找）

BSTree T 为二叉树根节点 ，int e 为查找的关键字。时间复制度为O(log2 n)。

int searchTree(BSTree T,int e)//在二叉树中查找给定关键字(函数返回值为成功1,失败0)
{
    if (T==NULL)//无法查找到给定关键字
    {
        return 0;
    }else if (e==T->data)//查找到关键字
    {
        return 1;
    }else if (e<T->data)//小于根结点，向左子树查找
    {
        return searchTree(T->lchild,e);
    }else if(e>T->data)//大于根结点，向右子树查找
    {
        return searchTree(T->rchild,e);
    }
}

二叉排序树的创建及插入（递归）

二叉排序树的插入算法基本过程也是查找，时间复制度也为O(log2 n)。

void InsertBST(BSTree &T,int e)//插入节点，根据节点值的大小插入
{//当二叉排序树中不存在关键字等于e的结点时，查找结束，插入结点
    if (!T)//查找到插入位置
    {
        BSTNode *S; //生成新结点
        S=new BSTNode;
        S->data=e;//给新结点赋值
        S->lchild=S->rchild=NULL;//将新结点作为叶子结点
        T=S;//给查找到的插入位置赋值
    }
    else if (e<T->data)
    {
        InsertBST(T->lchild,e);//向左查找插入
    }else if (e>T->data)
    {
        InsertBST(T->rchild,e);//向右查找插入
    }
}
void CreatBST(BSTree &T)//创建二叉树
{
    T=NULL;
    int e,n,i;
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        scanf("%d",&e);
        InsertBST(T,e);
    }
}

平衡二叉树

介绍完二叉排序树，我们就来看看平衡二叉树。
平衡二叉树就是在二叉排序树上建立的，可以说是具有以下两个特征的二叉排序树：
（1）左子树和右子树的深度之差的绝对值不超过1。
（2）左子树和右子树也是平衡二叉树。

平衡因子

为了方便记录和计算左右子树深度之差，我们引入一个概念叫平衡因子。
平衡因子就是该结点左右子树深度之差，由平衡二叉树的定义我们可以知道平衡二叉树上的平衡因子只可能是-1，0，1 。
图片来源于网络

二叉排序树的储存结构

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);//平衡因子等于左右子树的深度之差
    }
}

平衡二叉树的创建及调整方法

如何创建一棵平衡二叉树呢？
简单的来说就是：
（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结点的左子树，该树调整完成。

代码实现：

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

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型是左右相反的调整。

代码实现：

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

(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为旋转中心)。

代码实现：

AVLTree LR_rotate(AVLTree T)
{
    RR_rotate(T->lchild);
    return LL_rotate(T);
}

(4) RL型


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

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

代码实现：

AVLTree RL_rotate(AVLTree T)
{
    LL_rotate(T->rchild);
    return RR_rotate(T);
}

平衡二叉树的创建

了解完了如何调整非平衡二叉树，剩下工作就比较简单了，无非是在创建二叉排序树时，每次插入结点，把二叉树调整为平衡二叉树。
下面是代码实现：

输入数据

void creativetree(AVLTree &T)//输入数据
{
    T=NULL;
    int e,n,i;
    scanf("%d",&n);
    for (i=0; i<n; i++)
    {
        scanf("%d",&e);
        T=Insert(T,e);
    }
}

插入数据

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 (e<T->data)//向左搜索
    {
        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;
}

调整平衡二叉树

AVLTree AVLchange(AVLTree &T,AVLTree S)//调整为平衡二叉树
{
    int balance=0;//平衡因子
    while (S)
    {
        count_depth(T);//计算深度
        balance=count_balance(S);//计算平衡因子
        if(balance>1||balance<-1)
        {
            if(balance>1)//L型
            {
                if(count_balance(S->lchild)>0)//LL型
                {
                    S=LL_rotate(S);
                }
                else  //LR型
                {
                    S=LR_rotate(S);
                }
            }
            if(balance<1)//R型
            {
                if (count_balance(S->rchild)<0) //RR型
                    S=RR_rotate(S);
                else //RL型
                    S=RL_rotate(S);
            }
            if(S->father==NULL)//到达根节点，退出循环
            {
                T=S;//更新为新的根节点
                break;
            }
        }
        S=S->father;//一层一层往上调整
    }
    return T;
}

平衡二叉树实现的整体代码

#include "stdio.h"
#include "malloc.h"
#include <iostream>
#include <stack>
#include <queue>
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);//平衡因子等于左右子树的深度之差
    }
}

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 LR_rotate(AVLTree T)
{
    RR_rotate(T->lchild);
    return LL_rotate(T);
}

AVLTree RL_rotate(AVLTree T)
{
    LL_rotate(T->rchild);
    return RR_rotate(T);
}

AVLTree AVLchange(AVLTree &T,AVLTree S)//调整为平衡二叉树
{
    int balance=0;//平衡因子
    while (S)
    {
        count_depth(T);//计算深度
        balance=count_balance(S);//计算平衡因子
        if(balance>1||balance<-1)
        {
            if(balance>1)//L型
            {
                if(count_balance(S->lchild)>0)//LL型
                {
                    S=LL_rotate(S);
                }
                else  //LR型
                {
                    S=LR_rotate(S);
                }
            }
            if(balance<1)//R型
            {
                if (count_balance(S->rchild)<0) //RR型
                    S=RR_rotate(S);
                else //RL型
                    S=RL_rotate(S);
            }
            if(S->father==NULL)//到达根节点，退出循环
            {
                T=S;//更新为新的根节点
                break;
            }
        }
        S=S->father;//一层一层往上调整
    }
    return 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 (e<T->data)//向左搜索
    {
        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<n; i++)
    {
        scanf("%d",&e);
        T=Insert(T,e);
    }
}
int main()
{
    AVLTree T;
    creativetree(T);//建树
    return 0;
}

平衡二叉树的删除操作和其他遍历操作与二叉排序树无异，其他操作可以参考这里 实现二叉排序树的各种算法

标签：lchild,结点,AVLTree,son,AVL,二叉树,平衡
From： https://www.cnblogs.com/Tajt/p/16623193.html

相关文章

  • 文艺平衡树
    #【模板】文艺平衡树##题目描述您需要写一种数据结构（可参考题目标题），来维护一个有序数列。其中需要提供以下操作：翻转一个区间，例如原有序序列是54321，翻转区间是[2......
  • 二叉树的结构
    https://www.acwing.com/problem/content/description/4274/#include<bits/stdc++.h>#include<string.h>usingnamespacestd;constintN=1010;intpost[N],in[N......
  • 判断是不是平衡二叉树
    staticintflag=0;publicbooleanisBalanced(TreeNoderoot){flag=0;travel12(root);if(flag==1){returnfalse;......
  • leetcode 热题100刷题-二叉树的中序遍历
    题题号：94题目：二叉树的中序遍历难度：简单链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/2022/08/23答案算法思路  本题在课程中是学过的。  ......
  • 平衡树Splay与FHQ
    树剖的未来会补的（卑微）。这里想讲讲平衡树，因为看着高级，可以证明我学过OI。我们先了解下\(BST\)，也就是平衡二叉树。他的概念是，对于每一个非叶子结点，他的左儿子一定小于当......
  • 2022-8-22 剑指offer-优先队列-每日一题-二叉树-搜索/递归
    剑指OfferII060.出现频率最高的k个数字难度中等36收藏分享切换为英文接收动态反馈给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元......
  • 算法---二叉树的前序遍历
    知识点树递归dfs广度优先搜索(BFS)描述给你二叉树的根节点root，返回它节点值的前序遍历。数据范围：二叉树的节点数量满足0≤n≤100 0\len\le100\0≤......
  • 平衡二叉树
    1.为什么需要平衡二叉树？二叉排序树可能的存在的问题给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST),并分析问题所在.上图BST存在的问题分析:左子树全部为......
  • 655. 输出二叉树
    655.输出二叉树给你一棵二叉树的根节点root，请你构造一个下标从0开始、大小为mxn的字符串矩阵res，用以表示树的格式化布局。构造此格式化布局矩阵需要遵循......
  • 后缀数组 & 后缀平衡树
    后缀数组&后缀平衡树PPT:【腾讯文档】后缀数组——钱贵宁后缀数组是什么本质上是对一个字符串的所有后缀进行排序例如字符串abbcaba，我们按长度顺序列出它的所有后......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99