浙大数据结构慕课课后题(04-树5 Root of AVL Tree)

 题目要求:

AVL 树是一种自平衡的二叉搜索树。在 AVL 树中,任何节点的两个子子树的高度最多相差一;如果在任何时候它们相差不止一,则进行重新平衡以恢复此属性。图 1-4 说明了旋转规则。

 

                                图1

                                图2

                                图3

                                图4

现在给定一系列插入,您应该分辨生成的 AVL 树的根。

输入规格: 

 每个输入文件都包含一个测试用例。对于每种情况,第一行都包含一个正整数N(<=20),这是要插入的键的总数。然后N不同的整数键在下一行中给出。一行中的所有数字都用空格分隔。

输出规格: 

 对于每个测试用例,将生成的 AVL 树的根打印在一行中。

示例输入 1: 

 5
88 70 61 96 120

 示例输出 1:

 70

题解: 

        思路如注释所示,可通过所有测试点。

#include<bits/stdc++.h>
using namespace std;   
typedef struct AVLNode *Position;
typedef Position AVLTree;
typedef int ElementType;
struct AVLNode{ElementType Data;AVLTree Left;AVLTree Right;int Hight; 
};             int Max(int a,int b){return a > b ? a:b;
}int GetHight(AVLTree A)
{return A == NULL ? -1 : A->Hight;
}AVLTree SingleLeftRotation(AVLTree A){AVLTree B = A->Left;A->Left = B->Right;B->Right = A;A->Hight = Max( GetHight(A->Left), GetHight(A->Right) ) + 1;B->Hight = Max( GetHight(B->Left), A->Hight ) + 1;return B;
}AVLTree SingleRightRotation(AVLTree A){AVLTree B = A->Right;A->Right = B->Left;B->Left = A;A->Hight = Max( GetHight(A->Left), GetHight(A->Right) ) + 1;B->Hight = Max( GetHight(B->Right), A->Hight ) + 1;return B; 
}AVLTree DoubleLeftRightRotation(AVLTree A){/* 注意:A必须有一个左子结点B,且B必须有一个右子结点C *//* 将A、B与C做两次单旋,返回新的根结点C *//* 将B与C做右单旋,C被返回 */A->Left = SingleRightRotation(A->Left);/* 将A与C做左单旋,C被返回 */return SingleLeftRotation(A);
}AVLTree DoubleRightLeftRotation(AVLTree A){A->Right = SingleLeftRotation(A->Right);return SingleRightRotation(A);	
}AVLTree Insert(AVLTree T,ElementType X){if(!T){ //若插入空树。则新建一个结点 T = (AVLTree)malloc(sizeof(struct AVLNode));T->Data = X;T->Hight = 0;T->Left = NULL;T->Right = NULL;}	else if(X < T->Data){ //插入左树 T->Left = Insert(T->Left,X);if(GetHight(T->Left)-GetHight(T->Right) == 2){   //出现不平衡           if(X < T->Left->Data)T = SingleLeftRotation(T);   //插入在左树的左边->单左旋elseT = DoubleLeftRightRotation(T);   //插入再左树的右边->左右双旋				}}else if(X > T->Data){ //插入右树T->Right = Insert(T->Right,X);if(GetHight(T->Right)-GetHight(T->Left) == 2){   //出现不平衡 if(X > T->Right->Data)T = SingleRightRotation(T);      //单右旋 elseT = DoubleRightLeftRotation(T);	 	//右左旋 }} else return T;T->Hight = Max(GetHight(T->Left),GetHight(T->Right))+1;return T;
}int main(){AVLTree T = NULL;int t;cin>>t;while(t--){int num;cin>>num;T = Insert(T,num);}cout<<T->Data;
}

此题有以下几个要注意的点:

        1.Hight是指把 一个给定结点作为根节点时,其代表的树的树高,这样当左右子树树高差大于等于2时,可以发现平衡树失衡。

        2.树高取左右子树的最大值。

        3.左右双旋的时候在代码层面实际是先右单旋再左单旋,右左单旋时同理。

这里感觉何老师的ppt很清晰,(引一下,侵删)重点是找到“麻烦结点”对“不平衡发现者”是怎样破环的

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/397634.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【经验总结】ShardingSphere5.2.1 + Springboot 分库分表 快速开始

Sharding Sphere 官方文档地址&#xff1a; https://shardingsphere.apache.org/document/current/cn/overview/maven仓库&#xff1a;https://mvnrepository.com/artifact/org.apache.shardingsphere/shardingsphere-jdbc 官方的文档写的很详尽到位&#xff0c;这里会截取部分…

Spring事务管理:程序化 vs 声明式

Spring事务管理&#xff1a;程序化 vs 声明式 1、程序化事务管理2、声明式事务管理3、总结 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; Spring框架为事务管理提供了两种主要方式&#xff1a;程序化事务管理和声明式事务管理。 1、程序化…

【数据结构】六、图:3.十字链表、邻接多重表、边集数组

3.十字链表&#xff08;有向图&#xff09; 文章目录 3.十字链表&#xff08;有向图&#xff09;3.1性能分析 4.邻接多重表&#xff08;无向图&#xff09;4.1性能分析 5.边集数组 十字链表是有向图的一种链式存储结构。 不足 对于有向图来说&#xff0c;邻接表是有缺陷的。了…

Go语言fmt包中print相关方法

Go语言的fmt包提供了多种打印相关的函数&#xff0c;主要用于在控制台或其他输出目标上格式化并输出数据。下面是一些常用的print相关方法的用途和区别&#xff1a; 1.fmt.Print() 功能: fmt.Print() 将参数的内容按默认格式输出到标准输出&#xff08;通常是控制台&#xff…

【从零开始一步步学习VSOA开发】发布订阅服务端

发布订阅服务端 概念 **发布订阅模式&#xff08;Publish-Subscribe Pattern&#xff09;**是一种消息传递模式&#xff0c;其中发布者发布消息&#xff0c;而订阅者接收和处理这些消息。它是一种松耦合的通信方式&#xff0c;允许发布者和订阅者在不知道彼此存在的情况下进行…

【C++】面向对象三大特性之—— 多态(从底层带你理解多态)

目录 前言 什么是多态 多态的定义及实现 虚函数 虚函数的重写 多态的构成条件 虚函数重写的两个例外 协变 析构函数的重写&#xff08;重要&#xff01;&#xff01;&#xff01;&#xff09; override 和 final&#xff08;了解&#xff09; override final 重载、…

linux 查看端口占用并处理

lsof 命令 lsof -i:端口注意pid netstat 命令 netstat -tnpla | grep 端口注意pid 查看详情 ps -ef | grep 3766607删除 kill -9 PIDkill -9 3766607

【整数规划】+【0—1规划】解决优化类问题(Matlab代码)

目录 文章目录 前言 一、整数规划 分类&#xff1a; 二、典例讲解 1.背包问题 2.指派问题 总结 前言 如果觉得本篇文章还不错的话&#xff0c;给作者点个赞鼓励一下吧&#x1f601;&#x1f601;&#x1f601; 在规划问题中&#xff0c;有些最优解可能是分数或小数&am…

SpringBoot+Vue3+SSE实现实时消息语音播报

目录 1、前言 2、什么是SSE 2.1、与WebSocket有什么异同&#xff1f; 3、代码实现 3.1、前置代码 3.2、SSE相关代码 3.3、消息类相关代码 3.4 、前端代码 4、实机演示 1、前言 有这样一个业务场景&#xff0c;比如有一个后台管理系统&#xff0c;用来监听订单的更新&…

【NUCLEO-G071RB】010——TIM6-基本定时器

NUCLEO-G071RB&#xff1a;010——TIM6-基本定时器 基本定时器设计目标芯片配置程序修改运行测试 基本定时器 基本定时器只能用于计时&#xff0c;可以配置有无上溢出中断&#xff0c;它基本到不支持下溢出中断。它的时钟源&#xff08;应该&#xff09;是TPCLK&#xff0c;内…

ChatGPT首次被植入人类大脑:帮助残障人士开启对话

马斯克在脑机接口中最强大的竞争对手Synchron有了新的技术进展&#xff0c;他们首次将ChatGPT整合到其脑机系统中&#xff0c;以使瘫痪患者更容易控制他们的数字设备。Synchron凭借其独特的脑机接口&#xff08;BCI&#xff09;技术脱颖而出&#xff0c;该技术巧妙地运用了成熟…

【npm】如何将自己的插件发布到npm上

前言 简单说下 npm 是什么&#xff1a; npm 是一个 node 模块管理工具&#xff0c;也是全球最大的共享源。 npm 工具与 nodejs 配套发布&#xff0c;便利开发人员共享代码。npm 主要包括 npm 官方网站、CLI&#xff08;控制台命令行工具&#xff09;、和 registry&#xff08;…

「Pytorch」BF16 Mixed Precision Training

在深度学习领域&#xff0c;神经网络的训练性能瓶颈常常出现在 GPU显存的使用上。主要表现为两方面&#xff1a; 单卡上可容纳的模型和数据量有限&#xff1b;显存与计算单元之间的带宽和延迟限制了运算速度&#xff1b; 为了解决显卡瓶颈的问题&#xff0c;涌现了不同的解决…

Arduino控制带编码器的直流电机速度

Arduino DC Motor Speed Control with Encoder, Arduino DC Motor Encoder 作者 How to control dc motor with encoder:DC Motor with Encoder Arduino, Circuit Diagram:Driving the Motor with Encoder and Arduino:Control DC motor using Encoder feedback loop: How …

深度学习碎碎念——碎片知识1

1、什么叫模型收敛&#xff1f;什么叫模型欠拟合和过拟合&#xff1f; 什么叫模型收敛&#xff1f;——模型收敛是指在训练过程中&#xff0c;模型的损失函数逐渐减小并且趋于稳定的状态。简而言之&#xff0c;当模型的训练过程达到一个稳定的点&#xff0c;使得进一步的训练不…

CV党福音:YOLOv8实现语义分割(一)

前面我们得知YOLOv8不但可以实现目标检测任务&#xff0c;还包揽了分类、分割、姿态估计等计算机视觉任务。在上一篇博文中&#xff0c;博主已经介绍了YOLOv8如何实现分类&#xff0c;在这篇博文里&#xff0c;博主将介绍其如何将语义分割给收入囊中。 YOLOv8语义分割架构图 …

【C++】特殊类的设计与类型转换

文章目录 1. 特殊类的设计1.1 不能被拷贝的类1.2 只能在堆上创建对象的类1.3 只能在栈上创建对象的类1.4 不能被继承的类1.5 只能创建一个对象的类&#xff08;单列模式&#xff09; 2. 类型转换2.1 C/C的类型转换2.2 C规定的四种类型转换2.2.1 static_cast2.2.2 reinterpret_c…

【吊打面试官系列-Elasticsearch面试题】对于 GC 方面,在使用 Elasticsearch 时要注意什么?

大家好&#xff0c;我是锋哥。今天分享关于 【对于 GC 方面&#xff0c;在使用 Elasticsearch 时要注意什么&#xff1f;】面试题&#xff0c;希望对大家有帮助&#xff1b; 对于 GC 方面&#xff0c;在使用 Elasticsearch 时要注意什么&#xff1f; 1、SEE 2、倒排词典的索引需…

vue3使用pnpm运行项目但是运行不起来

运行项目的时候发现根本运行不起来了 尝试过创建.npmr文件 删除node_modules重新下 但是都出现问题了 创建.npmr&#xff1a;不管用 删除node_modules重新下&#xff1a;文字编译乱码&#xff0c;utf-8可能解析处理问题 最后解决方法&#xff1a; 重新创建项目&#xff0…

网络科技公司官网电商软件开发小程序网站pbootcms模板带手机端

免费授权可商用网站模板 PC端移动端后台测试数据 所有页面均都能完全自定义标题/关键词/描述&#xff0c;PHP程序&#xff0c;安全、稳定、快速&#xff0c;响应式同一个后台&#xff0c;数据即时同步&#xff0c;简单适用&#xff0c;附带测试数据&#xff01;&#xff01;