平衡二叉树(AVL) 的认识与实现

文章目录

1 基本
- 1.1 概念
- 1.2 特点
- 1.3 构建
- 1.4 调整
- - 1.4.1 RR
  - - 1.4.1.1 示例
    - 1.4.1.2 多棵树不平衡
  - 1.4.2 LL
  - - 1.4.2.1 示例
  - 1.4.3 LR
  - - 1.4.3.1 示例
  - 1.4.4 RL
  - - 1.4.4.1 示例
- 1.5 实现
- - 1.5.1 示例
  - 1.5.2 完善

1 基本

1.1 概念

平衡二叉树是一棵合理的二叉排序树

解释

对于这么一个序列

在这里插入图片描述

如果按照普通的排序思路，5>4>3>2>1，会得到这么一棵树

如果想要查询结点5，则需要比对很多次；

而如果以3为根，则可以得到一棵较为合理的树

这样就搜索结点5只需要3次即可

为了实现较为合理的排序，AVL就因此诞生

1.2 特点

平衡二叉树有个至关重要的特点：

左右子树高度差不超过1

由此减少树的深度，从而减少查找次数

1.3 构建

本质上与构建二叉排序树一致
在构建二叉排序树的过程中，如果发现树不符合左右子树高度差不超过1的特点，需要进行调整

1.4 调整

通过**失衡树的根节点root和导致树失衡的结点node**来调整新的树

而根据2个方向来选择调整方法

导致树失衡的结点node在root的哪一侧
node在root孩子结点的哪一侧

调整方法

LL：上面两个方向均在左侧
RR：上面两个方向均在右侧
RL：上面两个方向一右一左
LR：上面两个方向一左一右

1.4.1 RR

RR：

取中间节点，使其父节点成为其左子树
如果它有左子树，则先使其父节点成为其左子树，然后使其原有的左子树连接到现有左子树的右子树上

//	代码的实现则是反过来，先连接原有左子树到现有左子树的右子树，再连接到中间节点的右子树
root 1	node/child 3
root->right_child = child->left_child;
child->left_child = root;

1.4.1.1 示例

对于开头提到的序列

在这里插入图片描述

进行正常排序

可见，root是1， node是3

node在root的右侧:R
node在root孩子节点的右侧:R

两个都是R

进行调整

在这里插入图片描述

如果2原先有左子树，调整：

在这里插入图片描述

1.4.1.2 多棵树不平衡

注意：如果遇到多棵树不平衡，则调整最小树

将上面的序列继续排序

在这里插入图片描述

排序

在这里插入图片描述

如图，有两棵树失衡，一棵树最大的树12345，一颗是345，我们只用调整最小的345即可

这棵也是RR，直接调整

在这里插入图片描述

1.4.2 LL

和RR完全相反

LL：

取中间节点，使其父节点成为其右子树
如果它有右子树，则先使其父节点成为其右子树，然后使其原有的右子树连接到现有右子树的左子树上

//	代码的实现则是反过来，先连接原有左子树到现有左子树的右子树，再连接到中间节点的右子树
root 5	node/child 3
root->left_child = child->right_child;
child->right_child = root;

1.4.2.1 示例

再来一组数据

在这里插入图片描述

正常排序

进行LL排序

在这里插入图片描述

继续

继续排序最小树

在这里插入图片描述

1.4.3 LR

LR：

取最后一个节点，使其作为父节点
将其原有的父节点作为它的左子树，将它原有的父节点的父节点作为它的右子树
如果它有左子树，则先使其父节点成为其左子树，然后使其原有的左子树连接到现有左子树的右子树上
如果它有右子树，则先将它原有的父节点的父节点作为它的右子树，然后将其原有的右子树连接到它原有的父节点的父节点的左子树上

总结

先RR
后LL

//	代码的实现则是反过来
root 7	node/child 6
root->left_child = child->right_child;	child-right_>child = root;		//有右子树
root->left_child->right_child = child->left_child;	root->left_child->right_child = child->left_child 	//有左子树
child->right_child = root;
root = child;

1.4.3.1 示例

在这里插入图片描述

进行正常排序

在这里插入图片描述

两棵树失衡

在这里插入图片描述

调整最下面的树

可见，root是7， node是6

node在root的左侧:L
node在root孩子节点的右侧:R

即LR

进行调整

在这里插入图片描述

1.4.4 RL

RL：

取最后一个节点，使其作为父节点
将其原有的父节点作为它的右子树，将它原有的父节点的父节点作为它的左子树
如果它有左子树，则先将它原有的父节点的父节点作为它的左子树，然后将其原有的左子树连接到它原有的父节点的父节点的右子树上
如果它有右子树，则先使其父节点成为其右子树，然后使其原有的右子树连接到现有右子树的左子树上，

总结

先LL
后RR

//	代码的实现则是反过来
root 1	node/child 6
root->right_child->left_child = child->right_child;	child-right_>child = root->right_child;		//有右子树
root->right_child = child->left_child;	child->left_child = root;		//有左子树
child->left_child = root;
root = child;

1.4.4.1 示例

在这里插入图片描述

进行正常排序

在这里插入图片描述

已经失衡，进行调整

可见，root是1， node是6

node在root的左侧:R
node在root孩子节点的右侧:L

即RL

进行调整

在这里插入图片描述

然后继续插入7/10

在这里插入图片描述

1.5 实现

建立平衡二叉树的过程就是建立一棵二叉搜索树的过程
而在建立过程中我们需要对树进行调整，调整需要用到树的高度，因此我们节点的结构体中需要添加一个height字段来标记当前树的高度

1.5.1 示例

只实现二叉排序树，还未使用字段height

#include<iostream>
using namespace std;
//节点
typedef struct TreeNode {int data;int height;struct TreeNode* left_child;struct TreeNode* right_child;
}TreeNode;
//进行二叉排序树的构建
void AVLInsert(TreeNode** T, int data)
{if (*T == NULL)	//没有节点{*T = (TreeNode*)malloc(sizeof(TreeNode));	//创建一个(*T)->data = data;(*T)->height = 0;	//高度设为0(*T)->left_child = NULL;(*T)->right_child = NULL;}else if (data < (*T)->data){AVLInsert(&(*T)->left_child, data);	//比根节点的data大，插入在左子树}else if (data > (*T)->data){AVLInsert(&(*T)->right_child, data);}
}
//前序遍历打印树
void PreOrder(TreeNode* T)
{if (T){cout << T->data;PreOrder(T->left_child);	//递归调用左子树PreOrder(T->right_child);	//递归调用右子树}
}
int main()
{TreeNode* T = NULL;int nums[5] = { 1,2,3,4,5 };for (int i = 0; i < 5; i++){	//构建树AVLInsert(&T, nums[i]);}PreOrder(T);cout << endl;return 0;
}

在这里插入图片描述

1.5.2 完善

获取高度（其实我们结构体中有定义height字段可以直接调用，但为了易读我这里创建一个函数得到height）

//获取高度高度
int GetHeight(TreeNode* node)
{return node ? node->height : 0;	//节点不为空，则返回节点的height值，否则返回0
}

获取最大高度

//获取最大高度
int GetMax(int a, int b)
{return a > b ? a : b;
}

实现RR和LL

//RR旋转
void rrRotation(TreeNode* root, TreeNode** node)
{TreeNode* tmp = root->right_child;root->right_child = tmp->left_child;	//原有左子树连接到现有左子树的右子树上tmp->left_child = root;					//使其父节点成为其现有的左子树root->height = GetMax(GetHeight(root->left_child), GetHeight(root->right_child)) + 1;tmp->height = GetMax(GetHeight(tmp->left_child), GetHeight(tmp->right_child)) + 1;*node = tmp;
}//LL旋转
void llRotation(TreeNode* root, TreeNode** node)
{TreeNode* tmp = root->left_child;root->left_child = tmp->right_child;	//原有右子树连接到现有右子树的左子树上tmp->right_child = root;				//使其父节点成为其现有的右子树root->height = GetMax(GetHeight(root->left_child), GetHeight(root->right_child)) + 1;tmp->height = GetMax(GetHeight(tmp->left_child), GetHeight(tmp->right_child)) + 1;*node = tmp;
}

实现LR和RL，就是调用LL和RR

//LR
void lrTotation(TreeNode** T)
{rrRotation((*T)->left_child, &(*T)->left_child);llRotation(*T, T);
}//RL
void rlTotation(TreeNode** T)
{llRotation((*T)->right_child, &(*T)->right_child);rrRotation(*T, T);
}

最后完善构建二叉树

//进行二叉排序树的构建
void AVLInsert(TreeNode** T, int data)
{if (*T == NULL)	//没有节点{*T = (TreeNode*)malloc(sizeof(TreeNode));	//创建一个(*T)->data = data;(*T)->height = 0;	//高度设为0(*T)->left_child = NULL;(*T)->right_child = NULL;}else if (data < (*T)->data)		//比根节点的data小，插入在左子树	:L{AVLInsert(&(*T)->left_child, data);//获取当前节点左右子树的高度int left_height = GetHeight((*T)->left_child);int right_height = GetHeight((*T)->right_child);//判断高度差if (left_height - right_height > 1){if (data < (*T)->left_child->data)//小于父节点左子树的值，说明在左边	:L{//LLllRotation(*T, T);}else// : R{//LRlrTotation(T);}}}else if (data > (*T)->data)//比根节点的data大，插入在右子树			:R{AVLInsert(&(*T)->right_child, data);						//获取当前节点左右子树的高度int left_height = GetHeight((*T)->left_child);int right_height = GetHeight((*T)->right_child);//判断高度差if (right_height - left_height > 1){if (data > (*T)->right_child->data)	//大于父节点右子树的值，说明在右边	:R{//RRrrRotation(*T, T);}else//:L{//RLrlTotation(T);}}}(*T)->height = GetMax(GetHeight((*T)->left_child), GetHeight((*T)->right_child)) + 1;
}

main

int main()
{TreeNode* T = NULL;int nums1[5] = { 1,2,3,4,5 };int nums2[5] = { 5,4,3,2,1 };int nums3[5] = { 8,7,9,5,6 };int nums4[5] = { 1,8,6,7,10 };for (int i = 0; i < 5; i++){	//构建树AVLInsert(&T, nums4[i]);}PreOrder(T);cout << endl;return 0;
}

在这里插入图片描述