本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作 昆山爱达人信息技术有限公司

Slides:



Advertisements
Similar presentations
凉山州2011级一诊考试情况分析 暨后期复习建议 四川省凉山州教育科学研究所 谌业锋.
Advertisements

《凉山州中长期教育改革和发展规划纲要》( 年)解读 (讲座幻灯课件请在网上下载,让我们一起思考!)
(讲座幻灯课件请在网上下载,让我们一起思考!)
上海培训班交流材料 顶岗实习考核评价体系研究 辽宁建筑职业技术学院  孙玉红 2010年6月.
(讲座幻灯课件请在网上下载,让我们一起思考!)
二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的许多操作算法简单,而任何树都可以与二叉树 相互转换,这样就解决了树的
让爱住紫荆 教师师德培训.
交易早餐-金融品 2017年3月11日 徽商期货研究所.
(讲座幻灯课件请在网上下载,让我们一起思考!)
全区中小学电子学籍应用视频培训 一、我区中小学生电子学籍信息系统建设使用情况
凉山州2012级一诊考试情况分析会.
第九章 查找.
主讲:计算机工程学院 李兰 答疑地点:主教学楼B区213
工资福利退休 政策及办事指南.
(讲座幻灯课件请在网上下载,让我们一起思考!)
毕业留念册.
(讲座幻灯课件请在网上下载,让我们一起思考!)
凉山州2008级高考情况分析 暨2009届高三复习建议 ——兼谈高考学生的心理指导.
简明连贯得体 准确鲜明生动 写完读一遍 不顺改一改 真诚教育 zhenchengjiaoyu 四年级作文第10课
第8章 查找 数据结构(C++描述).
树(三) 2012初赛知识点梳理.
赵海燕 软件研究所 14 Apr 第5章 树与二叉树 之三 赵海燕 软件研究所 14 Apr
第12章 樹狀搜尋結構 (Search Trees)
第7章 查找 北京师范大学 教育技术学院 杨开城.
第11讲 树和二叉树(二).
Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree
Ch.9 查找 查找和排序是两个重要的运算 §9.1 基本概念
无向树和根树.
本节内容 字符编码 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 随机读取 视频提供:昆山爱达人信息技术有限公司.
本节内容 消息的分发 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第二章 Java基本语法 讲师:复凡.
_04Combox控件和ListBox控件的使用
_05MessageMap的原理 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
MFC控件 本节内容 视频提供:昆山爱达人信息技术有限公司 视频录制:yang 官网地址:
Select模型 本节内容 视频提供:昆山爱达人信息技术有限公司 视频录制:yang 官网地址:
编译OpenSSL 本节内容 视频提供:昆山爱达人信息技术有限公司 视频录制:yang 官网地址:
Chapter 6 樹狀結構.
9.1 何謂高度平衡二元搜尋樹 9.2 AVL-tree的加入 9.3 AVL-tree的刪除
本节内容 Win32 API中的宽字符 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
_08文件的基本操作 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
本节内容 类成员的访问控制 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 内存复制指令 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 Private Memory 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
<编程达人入门课程> 本节内容 计算机编程语言 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
本节内容 结构体 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 线性地址的管理 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
_13简单的GDI绘图操作 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
本节内容 文件系统 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 模块隐藏 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
3.1私有内存的分配.
本节内容 C语言的汇编表示 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
_03宽字符与Unicode编程 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
本节内容 指针类型的使用 视频提供:昆山爱达人信息技术有限公司.
本节内容 通用寄存器 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
_08文件操作 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
MFC控件 本节内容 视频提供:昆山爱达人信息技术有限公司 视频录制:yang 官网地址:
_07多连接之select模型 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
阻塞式模型 本节内容 视频提供:昆山爱达人信息技术有限公司 视频录制:yang 官网地址:
MFC的六大核心 机制 命令传递 本节内容 视频提供:昆山爱达人信息技术有限公司 视频录制:yang
_01自己实现简单的消息处理框架模型 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司
本节内容 动态链接库 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 导出表 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 如何调试驱动程序? 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 进程 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
编程达人-- 从零开始学UI系列教程 第九节、布尔运算 先行者 YC.
<编程达人入门课程> 本节内容 有符号数与无符号数 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ:
本节内容 this指针 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
最小生成树 最优二叉树.
Presentation transcript:

本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡二叉树的定义 平衡二叉树的定义 平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的,所以又称为AVL树。 定义:平衡二叉树一种满足下面性质的二叉树 (1)是一棵空树或满足(2)、(3)的非空二叉树 (2)左子树和右子树深度之差的绝对值不大于1 (3)左子树和右子树也都是平衡二叉树

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡二叉树的定义 平衡二叉树的定义 平衡因子(Balance Factor):二叉树上结点的左子树的深度减去右子树的深度称为该结点的平衡因子。 因此,平衡二叉树上每个结点的平衡因子只可能是-1,0和1,否则,只要有一个结点的平衡因子的绝对值大于1,该二叉树就不是平衡二叉树。 如果一棵二叉树既是二叉排序树又是平衡二叉树称为平衡二叉排序树

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡二叉树的定义 平衡二叉树的定义

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡化旋转 平衡二叉树的旋转

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡化旋转 平衡二叉树的旋转 可见,一般的二叉排序树是不平衡的,需要对二叉排序树进行修正使其即保持有序性,又具有平衡性。这种修正的方法称为平衡化旋转。 在对AVL树进行插入和删除一个结点后,通常会影响到从根结点到插入(或删除)结点的路径上的某些结点。这些结点的子树可能发生变化。以插入结点为例,影响有如下可能: 1.某些结点深度发生了变化 2.某些结点平衡因子发生了变化 3.某些结点失去平衡

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡化旋转 LL型平衡化旋转

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡化旋转 RR型平衡化旋转

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡化旋转 LR型平衡化旋转

平衡化旋转 RL型平衡化旋转 以上的平衡化旋转的规则可以保证二叉排序树的次序不变 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡化旋转 RL型平衡化旋转 以上的平衡化旋转的规则可以保证二叉排序树的次序不变

平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作是在二叉排序树的基础上完成以下工作: 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作是在二叉排序树的基础上完成以下工作: 1.判断插入结点后的二叉排序树是否产生不平衡 2.找出失去平衡的最小子树 3.判断旋转类型,然后做相应调整

平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 算法思想: 1.按照二叉排序树的定义,将结点s插入 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 算法思想: 1.按照二叉排序树的定义,将结点s插入 2.在查找结点s的插入位置的过程中,记录离结点s最近且平衡因子不为0的结点a,若该结点不存在,则结点a指向根结点 3.修改结点a到结点s路径上所有结点的平衡因子 4.判断是否产生不平衡,若不平衡,则确定旋转类型并做相应调整

平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 演示: 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 演示: