ToB企服应用市场:ToB评测及商务社交产业平台

标题: 平衡二叉树（AVL）的实现 [打印本页]

作者: 干翻全岛蛙蛙 时间: 2022-9-16 17:21
标题: 平衡二叉树（AVL）的实现
平衡二叉树概念

平衡二叉排序树（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。
二叉排序树的储存结构

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）先按照我们创建二叉排序树的方法，找到结点插入位置，将结点插入二叉树中。
（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结点的左子树，该树调整完成。

代码实现：

typedef struct AVLNode
{
int data=0;//结点值
int depth=0;//深度，方便通过计算左右子树深度之差得到该结点的平衡因子
struct AVLNode *father=NULL;//父结点
struct AVLNode *lchild=NULL,*rchild=NULL;//左右结点
} 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型是左右相反的调整。

代码实现：

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

复制代码

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

复制代码

(4) RL型

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

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

代码实现：

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

复制代码

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

[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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)