Chapter111二叉搜索树2学时最新完整版本.pdfVIP

Chapter11Chapter11搜索树搜索树

中国地质大学信息工程学院中国地质大学信息工程学院

LOGO

2011/10/211

内容提要内容提要LOGO

11.111.1二叉搜索树二叉搜索树

11.2AVL11.2AVL树树

11.311.3红黑树红黑树

11.4B11.4B--树树

11.511.5应用应用

2011/10/212

查找表的分类LOGO

静态查找表

仅作查询和检索操作的查找表。

常用方法：

顺序查找：无序表、有序表

折半查找：有序表

分块查找：索引顺序表

动态查找表

在查找过程中同时插入查找表中不存在的数据元

素，或者从查找表中删除已存在的某个数据元素。

哈希查找表

又叫散列查找，利用哈希函数进行查找的过程

2011/10/213

11、搜索树简介、搜索树简介LOGO

可用于描述字典的数据结构：可用于描述字典的数据结构：nn个元素个元素

跳表：进行搜索、插入或者删除操作所需要的平跳表：进行搜索、插入或者删除操作所需要的平

均时间为均时间为O(logn)O(logn)，而最坏情况下的时间为，而最坏情况下的时间为O(n)O(n)；；

散列：平均和最坏时间分别为散列：平均和最坏时间分别为O(1)O(1)和和O(n)O(n)，可适，可适

用于根据元素关键值进行的操作；用于根据元素关键值进行的操作；

两者比较：使用跳表很容易对字典元素进行高效两者比较：使用跳表很容易对字典元素进行高效

的顺序访问（如按照升序搜索元素），而散列却的顺序访问（如按照升序搜索元素），而散列却

做不到这一点。做不到这一点。

2011/10/214

搜索树的引入搜索树的引入LOGO

平衡搜索树平衡搜索树：对一个：对一个nn元素的字典进行搜索、插入元素的字典进行搜索、插入

或者删除所需要的平均和最坏时间均为或者删除所需要的平均和最坏时间均为O(logn)O(logn)；；

并且所有字典元素能够在线性时间内按升序输出。并且所有字典元素能够在线性时间内按升序输出。

在搜索树中进行顺序访问时，搜索每个元素所需要在搜索树中进行顺序访问时，搜索每个元素所需要

的平均时间为的平均时间为O(1)O(1)。。

搜索树既适用于根据元素关键值的操作，也适用于搜索树既适用于根据元素关键值的操作，也适用于

不按精确的关键值匹配进行字典操作的应用（比如不按精确的关键值匹配进行字典操作的应用（比如

寻找关键值大于寻找关键值大于kk的最小元素）。的最小元素）。

2011/10/215

22、二叉搜索树、二叉搜索树LOGO

散列无法提供较好性能的一些操作：散列无法提供较好性能的一些操作：

按关键值