详解如何用c++实现平衡二叉树
作者：zhangbaochong 发布时间：2023-11-30 21:29:44
标签：c++,平衡二叉树,AVL树
一、概述
平衡二叉树具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
平衡二叉树大部分操作和二叉查找树类似，主要不同在于插入删除的时候平衡二叉树的平衡可能被改变，并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变，因为只有这些结点的子树可能变化。
二、平衡二叉树不平衡的情形
把需要重新平衡的结点叫做α，由于任意两个结点最多只有两个儿子，因此高度不平衡时，α结点的两颗子树的高度相差2.容易看出，这种不平衡可能出现在下面4中情况中：
1.对α的左儿子的左子树进行一次插入
2.对α的左儿子的右子树进行一次插入
3.对α的右儿子的左子树进行一次插入
4.对α的右儿子的右子树进行一次插入
情形1和情形4是关于α的镜像对称，二情形2和情形3也是关于α的镜像对称，因此理论上看只有两种情况，但编程的角度看还是四种情形。
第一种情况是插入发生在“外边”的情形（左左或右右），该情况可以通过一次单旋转完成调整；第二种情况是插入发生在“内部”的情形（左右或右左），这种情况比较复杂，需要通过双旋转来调整。
三、调整措施
3.1、单旋转
上图是左左的情况，k2结点不满足平衡性，它的左子树k1比右子树z深两层，k1子树中更深的是k1的左子树x，因此属于左左情况。
为了恢复平衡，我们把x上移一层，并把z下移一层，但此时实际已经超出了AVL树的性质要求。为此，重新安排结点以形成一颗等价的树。为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。
这种情况称为单旋转。
3.2、双旋转
对于左右和右左两种情况，单旋转不能解决问题，要经过两次旋转。
对于上图情况，为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树。
四、AVL树的删除操作
同插入操作一样，删除结点时也有可能破坏平衡性，这就要求我们删除的时候要进行平衡性调整。
删除分为以下几种情况：
首先在整个二叉树中搜索要删除的结点，如果没搜索到直接返回不作处理，否则执行以下操作：
1.要删除的节点是当前根节点T。
如果左右子树都非空。在高度较大的子树中实施删除操作。
分两种情况：
(1)、左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前根节点，然后删除左子树中元素值最大的那个节点。
(1)、左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。
如果左右子树中有一个为空，那么直接用那个非空子树或者是NULL替换当前根节点即可。
2、要删除的节点元素值小于当前根节点T值，在左子树中进行删除。
递归调用，在左子树中实施删除。
这个是需要判断当前根节点是否仍然满足平衡条件，
如果满足平衡条件，只需要更新当前根节点T的高度信息。
否则，需要进行旋转调整：
如果T的左子节点的左子树的高度大于T的左子节点的右子树的高度，进行相应的单旋转。否则进行双旋转。
3、要删除的节点元素值大于当前根节点T值，在右子树中进行删除。
五、代码实现
AvlTree.h
#include <iostream>
#include <algorithm>
using namespace std;
#pragma once
//平衡二叉树结点
template <typename T>
struct AvlNode
{
T data;
int height; //结点所在高度
AvlNode<T> *left;
AvlNode<T> *right;
AvlNode<T>(const T theData) : data(theData), left(NULL), right(NULL), height(0){}
};
//AvlTree
template <typename T>
class AvlTree
{
public:
AvlTree<T>(){}
~AvlTree<T>(){}
AvlNode<T> *root;
//插入结点
void Insert(AvlNode<T> *&t, T x);
//删除结点
bool Delete(AvlNode<T> *&t, T x);
//查找是否存在给定值的结点
bool Contains(AvlNode<T> *t, const T x) const;
//中序遍历
void InorderTraversal(AvlNode<T> *t);
//前序遍历
void PreorderTraversal(AvlNode<T> *t);
//最小值结点
AvlNode<T> *FindMin(AvlNode<T> *t) const;
//最大值结点
AvlNode<T> *FindMax(AvlNode<T> *t) const;
private:
//求树的高度
int GetHeight(AvlNode<T> *t);
//单旋转 左
AvlNode<T> *LL(AvlNode<T> *t);
//单旋转 右
AvlNode<T> *RR(AvlNode<T> *t);
//双旋转 右左
AvlNode<T> *LR(AvlNode<T> *t);
//双旋转 左右
AvlNode<T> *RL(AvlNode<T> *t);
};
template <typename T>
AvlNode<T> * AvlTree<T>::FindMax(AvlNode<T> *t) const
{
if (t == NULL)
return NULL;
if (t->right == NULL)
return t;
return FindMax(t->right);
}
template <typename T>
AvlNode<T> * AvlTree<T>::FindMin(AvlNode<T> *t) const
{
if (t == NULL)
return NULL;
if (t->left == NULL)
return t;
return FindMin(t->left);
}
template <typename T>
int AvlTree<T>::GetHeight(AvlNode<T> *t)
{
if (t == NULL)
return -1;
else
return t->height;
}
//单旋转
//左左插入导致的不平衡
template <typename T>
AvlNode<T> * AvlTree<T>::LL(AvlNode<T> *t)
{
AvlNode<T> *q = t->left;
t->left = q->right;
q->right = t;
t = q;
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;
return q;
}
//单旋转
//右右插入导致的不平衡
template <typename T>
AvlNode<T> * AvlTree<T>::RR(AvlNode<T> *t)
{
AvlNode<T> *q = t->right;
t->right = q->left;
q->left = t;
t = q;
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;
return q;
}
//双旋转
//插入点位于t的左儿子的右子树
template <typename T>
AvlNode<T> * AvlTree<T>::LR(AvlNode<T> *t)
{
//双旋转可以通过两次单旋转实现
//对t的左结点进行RR旋转，再对根节点进行LL旋转
RR(t->left);
return LL(t);
}
//双旋转
//插入点位于t的右儿子的左子树
template <typename T>
AvlNode<T> * AvlTree<T>::RL(AvlNode<T> *t)
{
LL(t->right);
return RR(t);
}
template <typename T>
void AvlTree<T>::Insert(AvlNode<T> *&t, T x)
{
if (t == NULL)
t = new AvlNode<T>(x);
else if (x < t->data)
{
Insert(t->left, x);
//判断平衡情况
if (GetHeight(t->left) - GetHeight(t->right) > 1)
{
//分两种情况 左左或左右
if (x < t->left->data)//左左
t = LL(t);
else //左右
t = LR(t);
}
}
else if (x > t->data)
{
Insert(t->right, x);
if (GetHeight(t->right) - GetHeight(t->left) > 1)
{
if (x > t->right->data)
t = RR(t);
else
t = RL(t);
}
}
else
;//数据重复
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
template <typename T>
bool AvlTree<T>::Delete(AvlNode<T> *&t, T x)
{
//t为空 未找到要删除的结点
if (t == NULL)
return false;
//找到了要删除的结点
else if (t->data == x)
{
//左右子树都非空
if (t->left != NULL && t->right != NULL)
{//在高度更大的那个子树上进行删除操作
//左子树高度大，删除左子树中值最大的结点，将其赋给根结点
if (GetHeight(t->left) > GetHeight(t->right))
{
t->data = FindMax(t->left)->data;
Delete(t->left, t->data);
}
else//右子树高度更大，删除右子树中值最小的结点，将其赋给根结点
{
t->data = FindMin(t->right)->data;
Delete(t->right, t->data);
}
}
else
{//左右子树有一个不为空，直接用需要删除的结点的子结点替换即可
AvlNode<T> *old = t;
t = t->left ? t->left: t->right;//t赋值为不空的子结点
delete old;
}
}
else if (x < t->data)//要删除的结点在左子树上
{
//递归删除左子树上的结点
Delete(t->left, x);
//判断是否仍然满足平衡条件
if (GetHeight(t->right) - GetHeight(t->left) > 1)
{
if (GetHeight(t->right->left) > GetHeight(t->right->right))
{
//RL双旋转
t = RL(t);
}
else
{//RR单旋转
t = RR(t);
}
}
else//满足平衡条件 调整高度信息
{
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
}
else//要删除的结点在右子树上
{
//递归删除右子树结点
Delete(t->right, x);
//判断平衡情况
if (GetHeight(t->left) - GetHeight(t->right) > 1)
{
if (GetHeight(t->left->right) > GetHeight(t->left->left))
{
//LR双旋转
t = LR(t);
}
else
{
//LL单旋转
t = LL(t);
}
}
else//满足平衡性 调整高度
{
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
}
return true;
}
//查找结点
template <typename T>
bool AvlTree<T>::Contains(AvlNode<T> *t, const T x) const
{
if (t == NULL)
return false;
if (x < t->data)
return Contains(t->left, x);
else if (x > t->data)
return Contains(t->right, x);
else
return true;
}
//中序遍历
template <typename T>
void AvlTree<T>::InorderTraversal(AvlNode<T> *t)
{
if (t)
{
InorderTraversal(t->left);
cout << t->data << ' ';
InorderTraversal(t->right);
}
}
//前序遍历
template <typename T>
void AvlTree<T>::PreorderTraversal(AvlNode<T> *t)
{
if (t)
{
cout << t->data << ' ';
PreorderTraversal(t->left);
PreorderTraversal(t->right);
}
}
main.cpp
#include "AvlTree.h"
int main()
{
AvlTree<int> tree;
int value;
int tmp;
cout << "请输入整数建立二叉树(-1结束)：" << endl;
while (cin >> value)
{
if (value == -1)
break;
tree.Insert(tree.root,value);
}
cout << "中序遍历";
tree.InorderTraversal(tree.root);
cout << "\n前序遍历:";
tree.PreorderTraversal(tree.root);
cout << "\n请输入要查找的结点：";
cin >> tmp;
if (tree.Contains(tree.root, tmp))
cout << "已查找到" << endl;
else
cout << "值为" << tmp << "的结点不存在" << endl;
cout << "请输入要删除的结点：";
cin >> tmp;
tree.Delete(tree.root, tmp);
cout << "删除后的中序遍历：";
tree.InorderTraversal(tree.root);
cout << "\n删除后的前序遍历：";
tree.PreorderTraversal(tree.root);
}
测试结果
来源：https://www.cnblogs.com/zhangbaochong/p/5164994.html
0
投稿猜你喜欢
使用filter设置要排除的URL@WebFilter(urlPatterns = "/*")@Order(value- 题目：Binary Tree Maximum Path SumGiven a binary tree, find the maximum p
- 最近项目中经常需要用到自定义控件，因此自定义属性也是经常要用到的，在此说明一下自定义属性的用法：自定义属性都存在于/value/attr.x
- 本文实例为大家分享了Java流布局图形界面编写代码，供大家参考，具体内容如下package jisuanqi;import java.awt
- 前言有时候我们开发时会发现有些方法调用非常多，但它的默认的调用方法却要传很多参数进去而且还得记得调用具体的写法，比如Toast，不止要调用m
- 前言通常在DAL层我们都需要把DataTable转换为List<T>让调用者尽可能的好用，尽量的不用关心数据库的字段等，所以我们
- 下面我们来探究Android如何实现关机，重启；在Android中这种操作往往需要管理员级别，或者rootAndroid实现的方式如下几种：
- 微信分享接口的java开发的一些小步骤，具体内容如下1.配置接口信息进行验证代码如下： /** * 访问没认证的地
- 操作流程假设你已经有自己的域名，因为微信公众号和微信回调都需要域名先看看官方给的文档根据官方文档，主要流程如下：（1）引导用户进入授权页面同
- 直接上代码：@Testpublic void testUnicode() { String a = "Hello&qu
- 相信大家使用多点对图片进行缩放，平移的操作很熟悉了，大部分大图的浏览都具有此功能，有些app还可以对图片进行旋转操作，QQ的大图浏览就可以对
- 最近 Google 已经发布 Android 新版本 7.0 Nougat (牛轧糖) ，相信Android手机用户在未来的几个月内会收到第
- 1.前提已经配置Sleuth，可参考2.什么是Zipkin?官网:https://zipkin.io/大规模分布式系统的APM工具( App
- ArrayList就是传说中的动态数组，它提供了如下一些好处：动态的增加和减少元素实现了ICollection和IList接口灵活的设置数组
- 重写子pagerview的dispatchTouchEvent方法，在返回前添加一句getParent().requestDisallowI
- 这篇文章主要介绍了Java数组扩容实现方法解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参
- 本文实例为大家分享了Android项目实现视频播放器的具体代码，供大家参考，具体内容如下VideoView控件是播放视频用的，借助它可以完成
- W3C制定了XML DOM标准。很多编程语言中多提供了支持W3C XML DOM标准的API。我在之前的文章中介绍过如何使用Javascri
- Android通过wifi连接手机的方法，供大家参考，具体内容如下1.首先电脑，手机连接同一个网络2.在Android studio中Ter
- Android 获取屏幕尺寸实例代码实现代码：/** * <supports-screens * android:smallScr
