当前位置：文档之家 › 数据结构_11

数据结构_11

  • 格式：ppt
  • 大小：1.52 MB
  • 文档页数：112

下载文档原格式

  / 112

合集下载

南邮_数据结构课后习题答案讲解

南邮_数据结构课后习题答案讲解

?
?
?1 4 7 ?
?
?
?4 4 9 ?
?4 4 9 ?
4.7 求对题图4-1的稀疏矩阵执行矩阵转置时数组
num[]和k[]的值。
col
0
1
2
3
4
num[col] 1
0
2
1
2
k[col]
0
1
1
3
4
2020/2/8
14
第六章 习题讲解
6-2. 对于三个结点 A，B和C，可分别组成多少不同 的无序树、有序树和二叉树？
int i,j,sum=0;
for (i=0;temp[i]<x&&i<n;i++); //找到首个大于等于 x的元素位置 i
if(i>n-1) return; //没有符合条件的元素
ffoorr ((jj==ii;;ljs<tn[j;]<) =y&&j<n;j++); if (lst[j]>y//)找到首个//大大于于yy的的元元素素前位移置 j
?0 0 ???3 0
6 0
0 0
0? 7??
行三元组：???10
2 0
6 ?列三元组：?1
? 3??
??0
0 2
?3?
6
? ?
? 0 0 0 0 0?
?1 4 7 ?
?3 2 ?8?
? ?
0
0 ? 8 10 0??
??3 2 ?8??
??3
3
10
? ?
?? 0 0 0 0 9??
?3 3 10 ?
（2）void Search_Delete(List *lst, T x,T y)

11.数据结构的传输和XDR标准

11.数据结构的传输和XDR标准

第11章数据结构的传输和XDR标准在复杂的网络应用中，在客户进程和服务器进程间可能需要传递一些复杂的数据结构，这些数据结构可能用于控制进程的动作或者返回进程处理的结果。

本章首先说明在网络中传送数据结构中，存在的问题。

比如各种数据类型的不同处理、指针的传递等等。

接着我们示例一个使用我们自己定义的简单规则进行数据结构传送的程序片断。

然后我们将说明在数据结构传送中实际上被使用的标准XDR（extern data representation），外部数据表示。

我们介绍了XDR转换库函数的使用。

11.1 数据结构的传送我们在UDP数据报一章曾经演示了一个视频点播的模拟，在模拟中，我们使用了非常简单的控制命令，而实际的系统中，可能需要传递更多的信息。

比如在客户进程和服务器进程连接TCP连接后，用户必须输入自身的用户标识和用户密码等等身份确认信息，然后通过TCP 连接将这些信息发送给服务器端，在服务器进程根据这些信息对用户的身份进行确认后，才能允许用户进入系统，使用系统中的各种资源。

因而，对于较复杂的网络应用，我们常常需要复杂的数据结构，而不是简单的几个字节。

11.1.1 数据结构传送的问题下面，我们将说明在数据结构传递中可能存在的问题。

1.网络字序的问题不同类型的计算机对于数据的存储格式可能不同，这将导致它们对相同整数（或其他类型数）的2进制序列理解不同，这个问题在以前我们已经详细说明了。

2.浮点数的传递图11.1 将浮点数的小数部分和整数部分分别传递浮点数的传递比整数更加困难，通常浮点数使用若干比特表示整数部分，其他比特表示小数部分。

不同类型的浮点数float和double，它们使用的比特数不相同，这使得在网络中传递它们有一定的困难。

对于浮点数的处理，可以将浮点数用字符串的形式进行传递，在接收端再将浮点数字符串转化成浮点数。

或者我们可以将浮点数的小数点前后的两个部分分别看成两个整数，分别进行传递。

图11.2 将浮点数作为字符串传递3.指针的处理在数据结构传递中，最为困难的是指针，因为指针的含义是本机上存放某个数据的地址，这个地址在远端的主机没有任何的意义。

国开作业数据结构（本）-单元测试11参考（含答案）

国开作业数据结构（本）-单元测试11参考（含答案）

题目：在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

选项A：2
选项B：4
选项C：1/2
选项D：1
答案：2
题目：邻接表是图的一种（）。

选项A：链式存储结构
选项B：索引存储结构
选项C：顺序存储结构
选项D：散列存储结构
答案：链式存储结构
题目：如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

选项A：完全图
选项B：有回路
选项C：连通图
选项D：一棵树
答案：连通图
题目：下列有关图遍历的说法不正确的是（）。

选项A：非连通图不能用深度优先搜索法
选项B：连通图的深度优先搜索是一个递归过程
选项C：图的遍历要求每一顶点仅被访问一次
选项D：图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
答案：非连通图不能用深度优先搜索法
题目：无向图的邻接矩阵是一个（）。

选项A：零矩阵
选项B：上三角矩阵
选项C：对角矩阵
选项D：对称矩阵
答案：对称矩阵
题目：图的深度优先遍历算法类似于二叉树的（）遍历。

选项A：中序
选项B：后序
选项C：层次
选项D：先序
答案：先序
题目：已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

）。

）。

）条边。

选项A：n（n+1）/2
选项B：n（n-1）/2
选项C：n（n-1）
选项D：n（n+1）
答案：n（n-1）/2。

济南大学 - 计11 - 数据结构课程设计题目

济南大学 - 计11 - 数据结构课程设计题目

济南大学 - 计11 - 数据结构课程设计题目济南大学信息科学与工程学院数据结构课程设计Practicum for Data Structure课程设计题目带结点记录的线性链表操作的实现设计小组成员设计目的：掌握线性链表的建立；掌握线性链表的结点定义；掌握线性链表的基本操作。

设计内容：利用线性链表实现学生成绩管理系统，具体功能：输入、输出、插入、删除、查找、追加、显示、保存、退出，并能在屏幕上输出操作前后的结果。

设计要求： 1. 结点定义包括：书名，作者，出版社，ISBN(13位，主关键码) 2. 查询包括：按书名查询、按作者查询、按书号查询。

作者相同是列出全部记录，作者和书名能实现模糊查询（含有某些子串的）。

3. 书写设计报告，叙述主要算法。

参考文献： 1. 严蔚敏, 陈文博. 数据结构及应用算法教程, 清华大学出版社, 2021 2. 严蔚敏. 数据结构（C语言版）, 清华大学出版社, 2021 3. 朱振元. 数据结构――C++语言描述, 清华大学出版社, 2021 4. 潘玉奇, 刘明军. 程序设计基础(C语言)实验指导, 清华大学出版社, 2021 济南大学信息科学与工程学院数据结构课程设计Practicum for Data Structure课程设计题目带结点记录的集合操作的实现设计小组成员设计目的：掌握用线性链表表示的集合的建立；掌握线性链表的结点定义；掌握集合的基本操作。

设计内容：利用线性链表实现集合操作，具体功能：集合的输入、显示、元素排序、交、差、并、对称差、程序退出，并能在屏幕上输出操作前后的结果。

设计要求： 1. 结点定义包括：英语词汇(主关键码)，词性，汉语 2. 基本操作：输入两个集合，按英语词条对两个集合进行排序、交集、差集、并集、对称差集的求解。

3. 书写设计报告，叙述主要算法。

参考文献： 1. 严蔚敏, 陈文博. 数据结构及应用算法教程, 清华大学出版社, 2021 2. 严蔚敏. 数据结构（C语言版）, 清华大学出版社, 2021 3. 朱振元. 数据结构――C++语言描述, 清华大学出版社, 2021 4. 杨波, 刘明军. 程序设计基础(C语言), 清华大学出版社, 2021 5. 潘玉奇, 刘明军. 程序设计基础(C语言)实验指导, 清华大学出版社, 2021 济南大学信息科学与工程学院数据结构课程设计Practicum for Data Structure课程设计题目表达式求值（计算器）设计小组成员设计目的：熟悉栈类型的数据结构和运算符重载。

硬盘数据结构11

硬盘数据结构11

一个完整硬盘的数据应该包括五部分：MBR，DBR，FA T，DIR区和DA TA区。

其中只有主引导扇区是唯一的，其它的随你的分区数的增加而增加硬盘分区后逻辑结构图中用淡红色标明的扇区（尤以主引导扇区和第一分区引导扇区为最）是易受病毒攻击的扇区（一）主引导扇区（0扇区）主引导扇区位于整个硬盘的0磁道0柱面1扇区，包括硬盘主引导记录MBR（Main Boot Record）和分区表DPT（Disk Partition Table）。

主引导程序代码又称第一关键代码，它的作用是找出系统当前的活动分区，负责把对应的一个操作系统的引导记录即当前活动分区的引导记录载入内存。

此后，主引导记录就把控制权转给该分区的引导记录。

如果主引导记录被病毒覆盖、清零，或者被某些分区软件改写，则可以用相应DOS版本的FDISK／mbr命令加以更正。

０扇区示意图主引导扇区即主引导记录MBR(Master Boot Record)，是硬盘的第一个物理扇区（0柱面，0磁头，1扇区），也就是硬盘的"0"扇区。

在它的512个字节中，包括三部分：主引导程序代码，占446字节（第一关键代码)硬盘分区表HDPT，占用64字节（第二关键代码)主引导扇区结束标志AA55H（第三关键代码)硬盘的总分区数为什么不能大于4的原因(需要建立扩展分区)。

在主分区最多只能分四个主分区不管硬盘有多大，最多也只能有四个主分区（扩展分区也是一个主分区）。

通常在WIN98下使用FDISK分区工具分区时，只分了一个活动分区和一个扩展分区。

16字节表示的意义磁头(０-254)、柱面(０-1023 ）、扇区(1-63) 由来每一分区的第1至第3字节是该分区起始地址。

其中第1字节为起始磁头号（面号）；第2字节的低6位为起始扇区号，高2位则为起始柱面号的高2位；第3字节为起始柱面号的低8位。

因此，分区的起始柱面号是用10位二进制数表示的，最大值为210 = 1024，因逻辑柱面号从0开始计，故柱面号的显示最大值为1023。

《数据结构》填空作业题(答案)

《数据结构》填空作业题(答案)

《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。

2．程序包括两个内容：数据结构和算法。

3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S）。

4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。

5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。

6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。

7. 在树形结构中，数据元素之间存在一对多的关系。

8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。

9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3种类型，树型结构和有向图结构合称为非线性结构。

10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。

12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。

13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。

14. 数据结构在物理上可分为顺序存储结构和链式存储结构。

15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。

16. 数据元素可由若干个数据项组成。

17. 算法分析的两个主要方面是时间复杂度和空间复杂度。

18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。

19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。

20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。

数据结构--第11章 文件

• 存储在顺序存储器（如磁带）上的文件，只能 是顺序文件，这种文件只能进行“顺序存取” 和“成批处理”。 • 顺序存取是指按记录的逻辑(或物理)顺序实现 逐个存取， • 若要查询第i个记录则必须先检索前 i－1 个记 录； • 插入新的记录只能加在文件的末尾；
• 更新某个记录必须对整个文件进行"复制"。
• 每个记录面有一个读/写磁 头，所有读写头安装在一 个活动臂装置上，可以一 起作径向移动。当磁道在 读/写头下通过时，便可以 进行信息的读/写。
• 各记录盘面上直径相同 的磁道组成一个“柱面”
• 一个磁道又可分为若干 弧段，称为“扇面”。 • 磁盘信息存取的单位为 一个扇面的字符组，称 为一个“页块” • 因此需用一个三维地址 来表明磁盘信息：柱面 号、记录面号和页块号。
二、B树的操作
• （1）按关键码进行查找 假设要查找关键码等于 kval 的记录
• 首先将根结点读入内存进行查找，若找到，即找 到了该记录所对应的物理记录位置，算法结束；
• 否则沿着指针所指，读入相应子树根结点继续进 行查找，直至找到关键码等于kval的索引项或者 顺指针找到某个叶子结点
• 前者可由索引项取得主文件中的记录，后者说明 索引文件中不存在关键码等于 kval 的记录。
二、磁盘存储器
• 磁盘是一种直接存取的存 储设备，既能顺序存取， 又能随机存取。目前使用 多为活动头磁盘。
• 由若干盘片组成一个盘片 组，固定在一个主轴上， 随着主轴顺一个方向高速 旋转。
• 除最顶上和最底下的两个 外侧盘面外，其余用于存 储数据的盘面称为“记录 盘面”，简称“记录面” • 记录面上存储数据的同心 圆称为“磁道”。
• 静态索引以ISAM文件为代表，它是一种专为磁 盘存取设计的文件组织方式，由索引区，数据区 和溢出区三部分组成。 • 索引区通常是与硬件层次一致的三级索引：总索 引，柱面索引和磁道索引，溢出区用来存放后插 入的记录。

数据结构与算法(共11张PPT)


(b)入队3个元素(c)出队3个元素
(b) d, e, b, g入队
利用一组连续的存储单元(一维数组)依次存放从队 在循环队列中进行出队、入队操作时，队首、队尾指
队列示意图
在非空队列里，队首指针始终指向队头元素，而队
(b) d, e, b, g入队
8
Q.rear
a5
a4
Q.front
(d)入队2个元素
a1, a2, … , an
的指修针改 和是队依列先中进元先素出的Q的变.re原化a则情r 进况行。的，如图所示。
a3
Q.front
a2
a1
首到队尾的各个元素，称为顺序队列。
(c)
d, e出队Q.front
Q.front
◆出队：首先删去front所指的元素，然后将队首指针front+1，并
◆rear所指的单元始终为空(a。)空队列
i
i, j, k入队
(e)
1
2
3
k
r
01
j5
2
front
43
i
b, g出队
(f )
r, p,
p rear
s, t入队
循环队列操作及指针变化情况
入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针 ，故队空和队满时头尾指针均相等。因此，无法通过front=rear来 判断队列“空”还是“满”。解决此问题的方法是：约定入队前，
数据结构与算法
1算法基础 2数据结构
3栈
4队列
5链表 6树和二叉树
7查找
4队列
✓队列的基本概念 ✓队列运算
✓循环队列及其运算
4队列
1.队列的基本概念

严蔚敏《数据结构》(第2版)章节题库-第11章 外部排序【圣才出品】

第11章　外部排序一、选择题1．下列排序算法中，其中（）是稳定的。

A．堆排序，起泡排序B．快速排序，堆排序C．直接选择排序，归并排序D．归并排序，起泡排序【答案】D2．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A．快速排序B．堆排序C．归并排序D．直接插入排序【答案】C【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。

不稳定排序有：快速排序、堆排序、shell排序。

时间复杂度平均为O（nlog2n）的有：归并排序、堆排序、shell排序、快速排序。

3．在下面的排序方法中，辅助空间为O（n）的是（）。

A．希尔排序B．堆排序C．选择排序D．归并排序【答案】D4．下列排序算法中，占用辅助空间最多的是（）。

A．归并排序B．快速排序C．希尔排序D．堆排序【解析】归并排序的辅助空间为O（n），快速排序所占用的辅助空间为O（logn），堆排序所占用的辅助空间为O（1）。

5．将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A．N B．2N-1 C．2N D．N-1【答案】A【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。

最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序最好情况下的复杂度为O（n）。

6．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A．插入B．选择C．希尔D．二路归并【答案】A【解析】解此题需要熟知各种排序方法的基本思想。

插入排序的基本思想是：假设待排序的记录存放在数组R[0．．n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0．．i-1]和R[i．．n-1]，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。

将当前无序区的第1个记录R[i]插入到有序区R[0．．i-1]中适当的位置上。

数据结构导论自考题模拟11

数据结构导论自考题模拟11(总分：100.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.逻辑关系是指数据元素的______（分数：2.00）A.存储方式B.数据项C.结构D.关联方式√解析：[考点] 逻辑关系[解析] 所谓逻辑关系是指数据元素之间的关联方式或者“邻接关系”。

2.算法能正确地实现预定功能的特性称为______（分数：2.00）A.正确性√B.易读性C.健壮性D.时空性解析：[考点] 算法的评价因素[解析] 算法的正确性是指能正确地实现预定功能，满足具体问题的需要。

3.for(i=0;i＜n;i++)for(j=0;j＜n;j++)A[i][j]=i*j;上面算法的时间复杂度为______∙ A.O(1)∙ B.O(n2)∙ C.O(log2n)∙ D.O(n)（分数：2.00）A.B. √C.D.解析：[考点] 时间复杂度的计算[解析] 第一个for语句执行n+1次，第二个for语句执行n*(n+1)次，第三行赋值语句执行n*n次，可得整个程序段的时间函数为T=(n+1)+n*(n+1)+n*n=2n 2 +2n+1，因此算法的时间复杂度为O(n 2 )。

4.带头结点的单链表head为空的判断条件为______（分数：2.00）A.head=NULLB.head!=NULLC.head-＞next=NULL √D.head-＞next=head解析：[考点] 单链表[解析] 带头结点的单链表head为空的判断条件为head-＞next=NULL。

5.设顺序表有10个元素，则在第4个元素前插入一个元素所需移动元素的个数为______（分数：2.00）A.6B.7 √C.8D.9解析：[考点] 顺序表的插入算法[解析] 插入法的基本步骤是：①将结点各向后移一位，以便空出第i个位置；②将x置入该空位；③表长加一，完成顺序表的插入。

6.已知一个单链表中，指针q指向指针p的前驱结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行______（分数：2.00）A.q-＞next=s;p-＞next=s;B.q-＞next=s;s-＞next=q;C.q-＞next=s;q-＞next=p;D.q-＞next=s;s-＞next=p; √解析：[考点] 单链表的插入算法[解析] 单链表的插入步骤是：找到插入位置的前一个结点q和后一个结点p，生成一个结点s，然后执行q-＞next=s;s-＞next=p完成单链表的插入。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
12/28/2011 31
观察
如果插入后bf(X)=0，那么以X为根节 点的子树的高度在插入前后是相同的。
12/28/2011
32
观察
例如，如果插入前的高度是h，且bf(X)为1， 那么，在插入前，X的左子树的高度XL是h1,右子树的高度XR是h-2。由于平衡因子变 为0，所以必须在XR中作插入，得到高度为 ‘ h-1的新子树X‘R。 由于从X到新插入节点途中遇到的所有节点 在插入前的平衡因子均为0，所以X'R的高 度必须增加到h-1。 X的高度仍保持为h，X的祖先的平衡因子在 插入前后保持相同，所以树的平衡被保持 住了。
12/28/2011 7
带索引的二叉搜索树的抽象数据类型描述
抽象数据类型IndexedBSTree{ 实例 除每一个节点有一个LeftSize域以外，其他与BSTree相同 操作 Create()：产生一个空的带索引的二叉搜索树 Search(k,e)：将关键值为k的元素返回到e中；如果操作 失败返回false，否则返回true IndexSearch(k,e)：将第k个元素返回到e中 Insert(e)：将元素e插入到搜索树 Delete(k,e)：删除关键值为k的元素并且将其返回到e中 IndexDelete(k,e)：删除第k个元素并将其返回到e中 Ascend()：按照关键值的升序排列输出所有元素 }
8
12/28/2011
二叉搜索树的搜索
要查找关键值为k的元素，那么先从根开始。 如果根为空，那么搜索树不包含任何元素， 查找失败，否则，将k与根的关键值相比较: 如果k小于根节点的关键值，那么就不必搜 索右子树中的元素，只要在左子树中搜索 即可。 如果k大于根节点的关键值，则正好相反， 只需在右子树中搜索即可。 如果k等于根节点的关键值，则查找成功， 搜索终止。 在子树中的查找与此类似。 12/28/2011 9
LR型不平衡
12/28/2011
38
LR型不平衡
12/28/2011
39
AVL搜索树的插入
1) 沿着从根节点开始的路径对具有相同关键值的元素进行 搜索，以找到插入新元素的位置。在此过程中，寻找最 近的，平衡因子为- 1或1的节点，令其为A 节点。如果 找到了相同关键值的元素，那么插入失败，以下步骤无 需执行。 2) 如果没有这样的节点A，那么从根节点开始再遍历一次， 并修改平衡因子，然后终止。 3) 如果bf(A) = 1并且新节点插入到A的的右子树中，或者 bf(A) =-1并且插入是在左子树中进行的，那么A 的新平 衡因子是0。这种情况下，修改从A 到新节点途中的平衡 因子，然后终止。 4) 确定A 的不平衡类型并执行相应的旋转，在从新子树根 节点至新插入节点途中，根据旋转需要修改相应的平衡 因子。
Chapter11 Serch Trees
1.
2. 3. 4.
二叉搜索树(Binary Search) Trees AVL树(AVL Trees) 红-黑树(Red-Black Trees) B树(B-Trees)
12/28/2011
1
本章重点
1. 2. 3.
二叉搜索树 AVL树 B树
12/28/2011
12/28/2011 40
AVL搜索树的删除
同普通二叉搜索树？
12/28/2011
41
AVL搜索树的删除
设q是被删除节点的父节点 如果删除发生在q的左子树，那么bf(q)减1， 而如果删除发生在q的右子树，那么bf(q) 加1。可以看到如下现象： 1)如果q新的平衡因子是0，那么它的高度 减少了1，并且需要改变它的父节点（如果 有的话）和其他某些祖先节点的平衡因子。 2)如果q新的平衡因子是－1或1，那么它的 高度与删除前相同，并且无需改变其祖先 的平衡因子值。 3)如果q新的平衡因子是－2或2，那么树在 12/28/2011 42 q节点是不平衡的。
12/28/2011 21
AVL树的描述
一般用链表方式来描述AVL树。 为简化插入和删除操作，为每个节点 增加一个平衡因子bf。节点x 的平衡 因子bf(x) 定义为： x 的左子树的高度-x 的右子树的高度 从AVL树的定义可以知道，平衡因子的 可能取值为?。
12/28/2011 22
平衡因子
18
1) 2)
12/28/2011
AVL树？
12/28/2011
19
AVL搜索树
AVL搜索树既是二叉搜索树，也是AVL 树。 带索引的AVL搜索树既是带索引的二叉 搜索树，也是AVL树。
12/28/2011
20
AVL树特征
如果用AVL树来描述字典并希望在对数时间内完成每 一种字典操作，那么， AVL树必须具备下述特征： 1) n 个元素（节点）的AVL树的高度是O(logn)。 2) 一棵n 元素的AVL 搜索树能在O(高度) = O(logn) 的时间内完成搜索。 3) 将一个新元素插入到一棵n 元素的AVL搜索树中， 可得到一棵n+ 1元素的AVL树，这种插入过程可 以在O(logn)时间内完成。 4) 从一棵n 元素的AVL搜索树中删除一个元素，可 得到一棵n- 1元素的AVL树，这种删除过程可以 在O(logn)时间内完成。
二叉搜索树的插入
在二叉搜索树中插入一个新元素e，首 先要验证e的关键值与树中已有元素的 关键值是否相同，这可以通过用e的关 键值对二叉树进行搜索来实现。 如果搜索不成功，那么新元素将被插 入到搜索的中断点。
12/28/2011
10
二叉搜索树的插入
12/28/2011
11
二叉搜索树的删除
考虑包含被删除元素的节点p的三种情 况： 1)p是树叶； 2)p只有一个非空子树； 3)p有两个非空子树。
操作 Create()：创建一个空的二叉搜索树 Search(k,e)：将关键值为k的元素返回到e 中；如果操作失败则返回false，否则返 回true Insert(e)：将元素e插入到搜索树中 Delete(k,e)：删除关键值为k的元素并且 将其返回到e中 Ascend()：按照关键值的升序排列输出所 有元素 ??? }
二叉搜索树?
12/28/2011
5
二叉搜索树的抽象数据类型描述
抽象数据类型BSTree{ 实例 二叉树，每一个节点中有一个元素， 该元素有一个关键值域；所有元素 的关键值各不相同；任何节点左子 树的关键值小于该节点的关键值； 任何节点右子树的关键值大于该节 点的关键值。
12/28/2011 6
二叉搜索树的抽象数据类型描述
2
平衡搜索树
当用平衡搜索树来描述一个n元素的 字典时，对其进行搜索、插入或者删 除所需要的平均时间和最坏时间均为 Θ(logn)，按元素排名进行的查找和 删除操作所需要的时间为O(logn)， 并且所有字典元素能够在线性时间内 按升序输出。
12/28/2011 3
二叉搜索树
定义[二叉搜索树] 二叉搜索树是一棵可能为 空的二叉树，一棵非空的二叉搜索树满足 以下特征： 1) 每个元素有一个关键值，所有的关键值都 是唯一的。 2) 根节点左子树的关键值（如果有的话）小 于根节点的关键值。 3) 根节点右子树的关键值（如果有的话）大 于根节点的关键值。 4) 根节点的左右子树也都是二叉搜索树。4 12/28/2011
12/28/2011 35
LL型不平衡
12/28/2011
36
LL型旋转
原来以A为根节点的子树，现在以B为根节 点，B‘L仍然是B的左子树，A变成B的右子 树，BR变成A的左子树，A的右子树不变。 由于A的平衡因子改变了，所以处于从B到 新插入节点途中的B‘的所有节点的平衡因 子都将改变，其他节点的平衡因子与旋转 前保持一致。 图11-8中a和c子树的高度是一样的，所以， 子树的祖父节点的平衡因子与插入前是一 样的。因此不再有平衡因子不是-1，0或1 的节点。一个LL旋转就已经使整个树重新 12/28/2011 37 获得平衡！
从AVL树的定义可以知道，平衡因子的 可能取值为-1，0和1。
12/28/2011
23
平衡因子
12/28/2011
24
AVL搜索树的ห้องสมุดไป่ตู้索
同普通二叉搜索树。 复杂性？
12/28/2011
25
AVL搜索树的插入
将一个新元素插入到AV L树中时，若 得到的新树中有一个或多个节点的平 衡因子的值不是-1，0或1，那么就说 新树是不平衡的。 通过移动不平衡树的子树来恢复树的 平衡。
14
12/28/2011
二叉搜索树的删除
如果p有两个非空子树。 只需将该元素替换为它的左子树中的 最大元素或右子树中的最小元素。
12/28/2011
15
二叉搜索树的删除
注意，必须确保右子树中的最小元素以及 左子树中的最大元素或者在没有子树的节 点中，或者在只有一个子树的节点中。 可以按下述方法来查找到左子树中的最大 元素：首先移动到子树的根，然后沿着各 节点的右孩子指针移动，直到右孩子指针 为0为止。 类似地，也可以找到右子树中的最小元素： 首先移动到子树的根，然后沿着各节点的 左孩子指针移动，直到左孩子指针为0为止。
12/28/2011 16
平衡树
当确定搜索树的高度总是O(logn)时， 能够保证每个搜索树操作所占用的时 间为O(logn)。 高度为O(logn)的树称为平衡树 （balanced tree）。
12/28/2011
17
AVL树
定义 空二叉树是AVL树； 如果T是一棵非空的二叉树，TL 和TR 分别是其左子树和右子树，那么当T满 足以下条件时，T是一棵AVL树： TL和TR是AVL树； | hL - hR |≤1, hL 和hR 分别是左子 树和右子树的高度。
12/28/2011 33
观察
使树的平衡遭到破坏的唯一一种情形 是插入过程使得平衡因子bf(X)的值由 -1变为-2，或者由1变为2。