数据结构--查表找ppt课件

1、何谓查找表 ？ 查找表是由同一类型的数据元查找表是由同一类型的数据元素素(或记录或记录)构成的集合。构成的集合。 由于由于“集合集合中的数据元素之中的数据元素之间存在着松散的关系，因此查找表间存在着松散的关系，因此查找表是一种运用灵活的构造。是一种运用灵活的构造。对查找表经常进展的操作对查找表经常进展的操作: :查询某个查询某个“特定的特定的数据元素能否数据元素能否在查找表中；在查找表中；检索某个检索某个“特定的特定的数据元素的各数据元素的各种属性；种属性；在查找表中插入一个数据元素；在查找表中插入一个数据元素；从查找表中删去某个数据元素。从查找表中删去某个数据元素。仅作仅作 前两种即查询和检

2、索操作的查找表。前两种即查询和检索操作的查找表。即检索的前后不会改动查找表的内容。即检索的前后不会改动查找表的内容。在查找过程中同时插入查找表中不存在的数在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个据元素，或者从查找表中删除已存在的某个数据元素数据元素,此类表为动态查找表。即检索过程此类表为动态查找表。即检索过程中能够会改动数据元素的存储位置。中能够会改动数据元素的存储位置。查找表可分为两类查找表可分为两类:是数据元素或记录中某个数据项是数据元素或记录中某个数据项的值，用以标识识别一个数据元的值，用以标识识别一个数据元素或记录。素或记录。 假设此关键字可以识别独

3、一的一个假设此关键字可以识别独一的一个记录，那么称之谓记录，那么称之谓“主关键字主关键字。 假设此关键字能识别假设干记录，那么称假设此关键字能识别假设干记录，那么称之谓之谓“次关键字次关键字。 根据给定的某个值，在查找表中确定一个根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录其关键字等于给定值的数据元素或记录 查找查找 假设查找表中存在这样一个记录，那么假设查找表中存在这样一个记录，那么称称“查找胜利查找胜利，查找结果：给出整个记，查找结果：给出整个记录的信息，或指示该记录在查找表中的位录的信息，或指示该记录在查找表中的位置；置； 否那么称否那么称“查找不胜利查找不胜利

4、，查找结果：，查找结果：给出给出“空记录空记录或或“空指针空指针。假设查找表中的数据元素之间不存在假设查找表中的数据元素之间不存在明显的组织规律，那么不便于查找。明显的组织规律，那么不便于查找。 例：查阅英文单词时，由于字典是例：查阅英文单词时，由于字典是按单词的字母在字母表中的次序编排按单词的字母在字母表中的次序编排的，因此查找时不需求从字典中第一的，因此查找时不需求从字典中第一个单词比较起，而只需根据待查单词个单词比较起，而只需根据待查单词的每个字母在字母表中的位置查到该的每个字母在字母表中的位置查到该单词。单词。如何进展查找？如何进展查找？查找的方法取决于查找表的构造。即取查找的方法取决

5、于查找表的构造。即取决于数据元素依何种关系组织在一同。决于数据元素依何种关系组织在一同。9.1 静静 态态 查查 找找 表表数据对象数据对象D：数据关系数据关系R：D是具有一样特性的数是具有一样特性的数据元素的集合。每个数据元素的集合。每个数据元素含有类型一样的据元素含有类型一样的关键字，可独一标识数关键字，可独一标识数据元素。据元素。 数据元素同属一个集合。数据元素同属一个集合。ADT StaticSearchTable /P216 Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();根本操作根本操

6、作 P：next ADT StaticSearchTable构造一个含构造一个含n个数据元素个数据元素的静态查找表的静态查找表ST。 Create(&ST, n);操作结果：操作结果：销毁表销毁表ST。Destroy(&ST);初始条件：初始条件：操作结果：操作结果：静态查找表静态查找表ST存在；存在；假设假设 ST 中存在其关键字等中存在其关键字等于于 key 的数据元素，那么函数的数据元素，那么函数值为该元素的值或在表中的值为该元素的值或在表中的位置，否那么为位置，否那么为“空空。 Search(ST, key);初始条件：初始条件：操作结果：操作结果：静态查找表静态查找表

7、ST存在，存在，key 为为和查找表中元素的关键字类和查找表中元素的关键字类型一样的给定值；型一样的给定值；按某种次序对按某种次序对ST的每个元的每个元素调用函数素调用函数Visit()一次且仅一次且仅一次，一旦一次，一旦Visit()失败，那失败，那么操作失败。么操作失败。Traverse(ST, Visit();初始条件：初始条件：操作结果：操作结果：静态查找表静态查找表ST存在，存在，Visit是对元素操作的运用函数；是对元素操作的运用函数；typedef struct / 数据元素存储空间基址，建表时数据元素存储空间基址，建表时 / 按实践长度分配，按实践长度分配，0号单元留空号单元留

8、空 int length; / 表的长度表的长度 SSTable;假设静态查找表的顺序存储构造为假设静态查找表的顺序存储构造为ElemType *elem;数据元素类型的定义为数据元素类型的定义为:typedef struct keyType key; / 关键字域关键字域 / 其它属性域其它属性域 ElemType ; , TElemType ;一、顺序查找表一、顺序查找表二、有序查找表二、有序查找表三、索引顺序表三、索引顺序表 以顺序表或线性链表表示以顺序表或线性链表表示静态查找表。静态查找表。从表的一端开场，顺序逐个从表的一端开场，顺序逐个扫描线性表，依次将扫描到的扫描线性表，依次将扫描

9、到的结点关键字和给定值结点关键字和给定值Key相比相比较，假设当前扫描到的结点关较，假设当前扫描到的结点关键字与键字与Key相等，那么检索胜相等，那么检索胜利；假设扫描终了后，仍未找利；假设扫描终了后，仍未找到关键字等于到关键字等于Key的结点，那的结点，那么检索失败。么检索失败。 一、顺序查找表一、顺序查找表i0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找6464监视哨监视哨iiii比较次数比较次数=5比较次数：比较次数：查找第查找第n个元素：个元素： 1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素

10、： n查找第查找第i个元素：个元素： n+1-i查找失败：查找失败： n+1查找过程：从表的一端开场逐个进展记查找过程：从表的一端开场逐个进展记录的关键字和给定值的比较。录的关键字和给定值的比较。例如：例如：21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi60ikey=64key=60i64int Search_Seq(SSTable ST,

11、 KeyType key) / 在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于 / key的数据元素。假设找到，那么函数值为的数据元素。假设找到，那么函数值为 / 该元素在表中的位置，否那么为该元素在表中的位置，否那么为0。 ST.elem0.key = key; / “哨兵哨兵 for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找从后往前找 return i; / 找不到时，找不到时，i为为0 / Search_Seq 定义：定义： 查找算法的平均查找长度查找算法的平均查找长度 (Average Search Length) 也

12、就是为确定某一结点在数据集合中的位置，给定值也就是为确定某一结点在数据集合中的位置，给定值与集合中的结点关键字所需进展的比较次数。与集合中的结点关键字所需进展的比较次数。其中其中: n 为表长，为表长，Pi 为查找表中第为查找表中第i个记录的概率，个记录的概率， 且且 Ci为找到该记录时，曾和给定值为找到该记录时，曾和给定值 比较过的关键字的个数比较过的关键字的个数分析顺序查找的时间性能。分析顺序查找的时间性能。niiiCPASL111niiP在等概率查找的情况下，在等概率查找的情况下， 顺序表查找的平均查找长度为：顺序表查找的平均查找长度为：对顺序表而言，对顺序表而言，Ci = n-i+1n

13、Pi121111n)i(nnASLnissASL = nP1 +(n-1)P2 + +2Pn-1+Pn 假设查找概率无法事先测定，假设查找概率无法事先测定，那么查找过程采取的改良方法是，那么查找过程采取的改良方法是，可以在记录中附设一个访问频度域，可以在记录中附设一个访问频度域，使查找概率大的记录在查找过程中使查找概率大的记录在查找过程中不断后移，以便在以后的查找过程不断后移，以便在以后的查找过程中减少比较次数中减少比较次数在不等概率查找的情况下，在不等概率查找的情况下，ASLss 在在 PnPn-1P2P1时取极小值时取极小值ASL = nP1 +(n-1)P2 + +2Pn-1+Pn 上述

14、顺序查找表的查找算法简单，上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。但平均查找长度较大，特别不适用于表长较大的查找表。二、有序查找表二、有序查找表 假设以有序表表示静态查找假设以有序表表示静态查找表，那么查找过程可以基于表，那么查找过程可以基于“折折半半进展。进展。1.设表长为设表长为n，low、high和和mid分别指向待查分别指向待查元素所在区间的上界、下界和中点元素所在区间的上界、下界和中点,k为给定为给定值。值。2.初始时，令初始时，令low=1,high=n,mid=(low+high)/2让让k与与mid指向的记录比较指向的记录比较假设假设k

15、=rmid.key，查找胜利，查找胜利假设假设krmid.key，那么，那么low=mid+13.反复上述操作，直至反复上述操作，直至lowhigh时，查找失时，查找失败。败。折半查找算法实现折半查找算法实现05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找过程如下的查找过程如下lowhighmidlow mid high midlow 指示查找区间的下界指示查找区间的下界;high 指示查找区间的上界指示查找区间的上界;mid = (low+high)/2。in

16、t Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值置区间初值 while (low 50时，可得近似结果时，可得近似结果 普通情况下，表长为普通情况下，表长为 n 的折半查的折半查找的断定树的深度和含有找的断定树的深度和含有 n 个结个结点的完全二叉树的深度一样。因点的完全二叉树的深度一样。因此具有此具有n个结点的断定树的深度为个结点的断定树的深度为 +1。为了方便起见，。为了方便起见，以满二叉树为例，树中层次为以满二叉树为例，树中层次为1的的结点有结点有1个，层次为个，层次为2的结点有的结点有

17、2个，个，层次为层次为h的结点有的结点有2h1个个.n2log1) 1(log2nASLbs1) 1(log1) 1(log12111),1(log, 122211112nnnnjncncpASLnphnhnhjjniiniiiih则：概率相等设表中每个记录的查找的满二叉树即判定树是深度为设表长在在 n50 时，可得近似结果时，可得近似结果 1) 1(log2nASLbs可见，可见，折半查找的效率比顺序查找高。折半查找的效率比顺序查找高。折半查找只能适用于有序表，并且以顺序存折半查找只能适用于有序表，并且以顺序存储构造存储。储构造存储。顺序表和有序表的比较顺序表和有序表的比较三、索引顺序表三、

18、索引顺序表以索引顺序表表示静态查找表，以索引顺序表表示静态查找表，searchsearch操作可用分块查找来实现。操作可用分块查找来实现。分块查找又称索引顺序查找，这是分块查找又称索引顺序查找，这是顺序查找的一种改良方法。在此查顺序查找的一种改良方法。在此查找方法中，除表本身以外，尚需建找方法中，除表本身以外，尚需建立一个立一个“索引表索引表。例如例如 表中含有表中含有1818个元素，可分成三个子表。个元素，可分成三个子表。对每个子表或称块建立一个索引项，对每个子表或称块建立一个索引项，其中包括两项内容：关键字项其值为该其中包括两项内容：关键字项其值为该子表内的最大关键字和项指针指示该子表内的

19、最大关键字和项指针指示该子表的第一个元素在表中位置。子表的第一个元素在表中位置。 索索 引引 表表 最大关键字最大关键字起始地址起始地址 索引表按关键字有序，故表索引表按关键字有序，故表或者有序，或者分块有序。所谓或者有序，或者分块有序。所谓“分块有序分块有序 是指一个子表中一是指一个子表中一切元素的关键字均大于前一个子切元素的关键字均大于前一个子表的最大关键字。表的最大关键字。 索引顺序表的查找过程：索引顺序表的查找过程：1由索引确定记录所在区间；由索引确定记录所在区间；2在顺序表的某个区间内进展查找。在顺序表的某个区间内进展查找。留意：索引可以根据查找表的特点来构造。留意：索引可以根据查找

20、表的特点来构造。可见，可见， 索引顺序查找的过程也是一个索引顺序查找的过程也是一个“减少区间减少区间的查找过程。的查找过程。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38例如例如索引顺序查找的平均查找长度索引顺序查找的平均查找长度 = 查找查找“索引索引的平均查找长度的平均查找长度 + 查找查找“顺序表顺序表的平均查找长度的平均查找长度分块查找方法评价分块查找方法评价121)(21212111)1( 211ssn

21、ssnsbisjbASLsbnLLLLASLsibjbswbwbbs：用顺序查找确定所在块率相等，则：表中每个记录的查找概个记录，并设块，每块含的表平均分成若将表长为查找长度在块中查找元素的平均的平均查找长度查找索引表确定所在块其中：ns n查找方法比较查找方法比较ASL最大最大最小最小两者之间两者之间表构造表构造有序表、无序表有序表、无序表有序表有序表分块有序表分块有序表存储构造存储构造顺序存储构造顺序存储构造或线性链表或线性链表顺序存储构造顺序存储构造顺序存储构造顺序存储构造或线性链表或线性链表顺序查找顺序查找折半查找折半查找 分块查找分块查找9.2 动动 态态 查查 找找 表表动态查找表

22、的特点动态查找表的特点:表构造本身是在查找过程中动态表构造本身是在查找过程中动态生成。假设表中存在其关键字等于给定值生成。假设表中存在其关键字等于给定值key的记录的记录,阐明查找胜利；否那么插入关键字等于阐明查找胜利；否那么插入关键字等于key的记录。的记录。ADT DynamicSearchTable 笼统数据类型动态查找表的定义如下：笼统数据类型动态查找表的定义如下：数据对象数据对象D：数据关系数据关系R： 数据元素同属一个集合。数据元素同属一个集合。D是具有一样特性的数据是具有一样特性的数据元素的集合。元素的集合。每个数据元素含有类型一每个数据元素含有类型一样的关键字，样的关键字， 可

23、独一标可独一标识数据元素。识数据元素。InitDSTable(&DT)/构造一个空的动态查构造一个空的动态查找表找表DT。DestroyDSTable(&DT)/销毁动态查找表销毁动态查找表DT。SearchDSTable(DT, key);/查找查找 DT 中与关中与关键字键字key等值的元素。等值的元素。InsertDSTable(&DT, e);/假设假设 DT 中不存中不存在其关键字等于在其关键字等于 e.key 的的 数据元素，那么数据元素，那么插入插入 e 到到 DT。DeleteDSTable(&T, key);/删除删除DT中关键中关键字等于字等

24、于key的数据元素。的数据元素。TraverseDSTable(DT, Visit();/按某种次序按某种次序对对DT的每个结点调用函数的每个结点调用函数 Visit() 一次且一次且至多一次。至多一次。根本操作：根本操作：nextADT DynamicSearchTable一、二叉排序树二叉查找树一、二叉排序树二叉查找树二、二叉平衡树二、二叉平衡树三、三、B - 树树四、四、B+树树一、二叉排序树一、二叉排序树二叉查找树二叉查找树1定义定义2查找算法查找算法3插入算法插入算法4删除算法删除算法5查找性能的分析查找性能的分析1假设它的左子树不空，那么左子树上假设它的左子树不空，那么左子树上 一

25、切结点的值均小于根结点的值；一切结点的值均小于根结点的值；1定义：定义： 二叉排序树或者是一棵空树；或者二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：是具有如下特性的二叉树：3它的左、右子树也都分别是二叉它的左、右子树也都分别是二叉 排序树。排序树。2假设它的右子树不空，那么右子树上假设它的右子树不空，那么右子树上 一切结点的值均大于根结点的值；一切结点的值均大于根结点的值；503080209010854035252388例如例如:是二叉排序树是二叉排序树66不不 通常，取二叉链表作为通常，取二叉链表作为二叉排序树的存储构造二叉排序树的存储构造typedef struct BiTNod

26、e / 结点构造结点构造 struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;TElemType data; 1假设给定值等于根结点的关键字，假设给定值等于根结点的关键字，那么查找胜利；那么查找胜利； 2假设给定值小于根结点的关键字，假设给定值小于根结点的关键字，那么继续在左子树上进展查找；那么继续在左子树上进展查找； 3假设给定值大于根结点的关键字，假设给定值大于根结点的关键字，那么继续在右子树上进展查找。那么继续在右子树上进展查找。否那么否那么假设二叉排序树为空，那么查找不胜利；假设二叉排序树为空，那么查找不胜利

27、；50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找途径在查找过程中，生成了一条查找途径: 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点逐层向下直至关键字等于给定值的结点;或者或者 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为止。 查找胜利查找胜利 查找不胜利查找不胜利BiTree Se

28、archBST( BiTree T, KeyType key) /在根指针在根指针T所指二叉排序树中递归地查找某关键字所指二叉排序树中递归地查找某关键字 /等于等于Key的数据元素，假设查找胜利，那么前往指向的数据元素，假设查找胜利，那么前往指向 /该数据元素的指针，否那么前往空指针该数据元素的指针，否那么前往空指针 if (!T)| EQ(key, T-data.key) return (T);/查找终了查找终了 else if LT(key, T-data.key) return(SearchBST(T-lchild, key) else return (SearchBST(T-rchil

29、d, key); /SearchBST二叉排序树是一种动态树表，其特点是，二叉排序树是一种动态树表，其特点是，树的构造通常不是一次生成的，而是在查树的构造通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给找的过程中，当树中不存在关键字等于给定值的结点时进展插入。定值的结点时进展插入。新插入的结点一定是一个新添加的叶子结新插入的结点一定是一个新添加的叶子结点，并且是查找不胜利时查找途径上访问点，并且是查找不胜利时查找途径上访问的最后一个结点的左孩子或右孩子结点。的最后一个结点的左孩子或右孩子结点。为此将二叉树的查找算法改为如下算法为此将二叉树的查找算法改为如下算法算法描画如下：算法

30、描画如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指针在根指针 T 所指二叉排序树中递归地查所指二叉排序树中递归地查找其找其 / 关键字等于关键字等于 key 的数据元素，假设查找的数据元素，假设查找胜利，胜利， / 那么前往指针那么前往指针 p 指向该数据元素的结点，指向该数据元素的结点，并前往并前往 / 函数值为函数值为 TRUE; / SearchBST 否那么阐明查找不胜利，前往否那么阐明查找不胜利，前往 / 指针指针 p 指向查找途径上访问的最后一个结点，指向查找途径上访问的最后一个

31、结点， / 并前往函数值为并前往函数值为FALSE, 指针指针 f 指向当前访问指向当前访问 / 的结点的双亲，其初始调用值为的结点的双亲，其初始调用值为NULL30201040352523fT设设 key = 48fTfT22pfTfTTTTfffpif (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不胜利查找不胜利 p = T; return TRUE; / 查找胜利查找胜利SearchBST (T-lchild, key, T, p );

32、/ 在左子树中继续查找在左子树中继续查找SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找在右子树中继续查找Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / SearchBST 根据动态查找表的定义，根据动态查找表的定义，“插入插入操作在查找不胜利时才进展操作在查找不胜利时才进展;3二叉排序树的插入算法二叉排序树的插入算法 假设二叉排序树为空树，那么新插假设二叉排序树为空树，那么新插入的结点为新的根结点；否那么，入的结点为新的根结点；否那么，新插入的结点必为一个新的叶

33、子结新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。点，其插入位置由查找过程得到。303020302040302040103020401025302040102545Status Insert BST(BiTree &T, ElemType e ) if (!SearchBST ( T, e.key, NULL, p ) s = (BiTree) malloc (sizeof (BiTNode); / 为为新结点新结点 分配空间分配空间s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入插入 s 为新的根

34、结点为新的根结点else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入插入 *s 为为 *p 的左的左孩子孩子else p-rchild = s; / 插入插入 *s 为为 *p 的右的右孩子孩子return TRUE; / 插入胜利插入胜利 else return FALSE; / Insert BST1被删除的结点是叶子；被删除的结点是叶子；2被删除的结点只需左子树或者只需右子树；被删除的结点只需左子树或者只需右子树；3被删除的结点既有左子树，也有右子树。被删除的结点既有左子树，也有右子树。可分三种情况讨论：可分三种情况讨论： 和插入相反，

35、删除在查找胜利之后进展，并和插入相反，删除在查找胜利之后进展，并且要求在删除二叉排序树上某个结点之后，依且要求在删除二叉排序树上某个结点之后，依然坚持二叉排序树的特性。然坚持二叉排序树的特性。503080209085403588321被删除的结点是叶子结点被删除的结点是叶子结点例如例如:被删关键字被删关键字 = 2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空503080209085403588322被删的结点只需左子树或只需右子树被删的结点只需左子树或只需右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除

36、结点的左子树或右子树。被删关键字被删关键字 = 4080503080209085403588323被删除的结点既有左子树，也有右子树被删除的结点既有左子树，也有右子树4040按中序遍历写出序列，按中序遍历写出序列， 以被删以被删结点其前驱替代之，然后再删结点其前驱替代之，然后再删除该前驱结点除该前驱结点被删结点被删结点前驱结点前驱结点被删关键字被删关键字 = 50Status DeleteBST (BiTree &T, KeyType key ) / 假设二叉排序树假设二叉排序树 T 中存在其关键字等于中存在其关键字等于 key 的的 / 数据元素，那么删除该数据元素结点，并前往数据元

37、素，那么删除该数据元素结点，并前往 / 函数值函数值 TRUE，否那么前往函数值，否那么前往函数值 FALSE if (!T) return FALSE; else / DeleteBST算法描画如下：算法描画如下：(p230) if ( EQ (key, T-data.key) ) / 找到关键字等于找到关键字等于key的数据元素的数据元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 继续在左子树中进展查找继续在左子树中进展查找DeleteBST (

38、T-rchild, key ); / 继续在右子树中进展查找继续在右子树中进展查找void Delete ( BiTree &p ) / 从二叉排序树中删除结点从二叉排序树中删除结点 p， / 并重接它的左子树或右子树并重接它的左子树或右子树 if (!p-rchild) else if (!p-lchild) else / Delete其中删除操作过程如下所描画：其中删除操作过程如下所描画： / 右子树为空树那么只需重接它的左子树右子树为空树那么只需重接它的左子树q = p; p = p-lchild; free(q); pq/ 左子树为空树只需重接它的右子树左子树为空树只需重接它的

39、右子树q = p; p = p-rchild; free(q);pqq = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild; / s 指向被删结点的前驱指向被删结点的前驱/ 左右子树均不空左右子树均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接重接*q的左子树的左子树free(s); 对于每一棵特定的二叉排序树，均可按照平均查找长度对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的的定义来求它的 ASL 值，

40、显然，由值一样的值，显然，由值一样的 n 个关键字，构造个关键字，构造所得的不同形状的各棵二叉排序树的平均查找长所得的不同形状的各棵二叉排序树的平均查找长 度的值不同，度的值不同，甚至能够差别很大。甚至能够差别很大。由关键字序列由关键字序列 3，1，2，5，4构造构造而得的二叉排序树而得的二叉排序树由关键字序列由关键字序列 1，2，3，4，5构造而得的二叉排序树，构造而得的二叉排序树，例如：例如：2134535412ASL =1+2+3+4+5/ 5 = 3ASL =1+2+3+2+3/ 5 = 2.2101iiicp310/ )3443221 (二、二叉平衡树二、二叉平衡树 何谓何谓“二叉平

41、衡树二叉平衡树？ 如何构造如何构造“二叉平衡树二叉平衡树是平衡二叉树，不是平衡二叉树，不是完全二叉树是完全二叉树不是平衡二叉树不是平衡二叉树 二叉平衡树是二叉查找树的另一种方式，其特点为：树中每个结点的左、右子树深度之差平衡因子BF的绝对值不大于1 1RLhh例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树平衡二叉树平衡二叉树BF值011001220失去平衡的最小子树v 构造二叉平衡查找树的方法：v在插入过程中，采用平衡旋转技术。v例如:依次插入的关键字为5, 4, 3, 8, 19,1,2，25，2354543BF值101021由于插入节点由于插入节点3使得树不使得树不再平衡

42、，而再平衡，而3是插入在失去平衡是插入在失去平衡的最小子树根节点的最小子树根节点5的左子树根的左子树根节点节点4的左子树上。定义失去平的左子树上。定义失去平衡的最小子树根节点为衡的最小子树根节点为a，那么，那么该类不平衡可归纳为，在该类不平衡可归纳为，在a的左的左子树根节点的左子树上插入导子树根节点的左子树上插入导致的不平衡可运用单向右旋平致的不平衡可运用单向右旋平衡处置，可以记为左左衡处置，可以记为左左-右。右。543000435843584358190-10-100-1-2-24358190000-12由于插入节点19使得树不再平衡，而19是插入在失去平衡的最小子树根节点5的右子树根节点8

43、的右子树上。该类不平衡可归纳为，在a的右子树根节点的右子树上插入导致的不平衡可运用单向左旋平衡处置，可以记为右右-左。458190003211-120458190003212110458190003002010先向左旋再向右旋3在在3的左子树根节点的左子树根节点1的的右子树上插入节点右子树上插入节点2导致不平导致不平衡，可运用双向旋转：先使衡，可运用双向旋转：先使其子树左旋再整棵树右旋，其子树左旋再整棵树右旋，可记为左右可记为左右-左右。左右。45819-2-2030-2201025231045819-2-2030-220102325-10先向右旋458230-1030-12010251900

44、再向左旋4在在19的右子树根节点的右子树根节点25的左子树上插入节点的左子树上插入节点23导致导致不平衡，可运用双向旋转：不平衡，可运用双向旋转：先使其子树右旋再整棵树左先使其子树右旋再整棵树左旋，可记为右左旋，可记为右左-右左。右左。 构造二叉平衡查找树的方法是：构造二叉平衡查找树的方法是：在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如例如:依次插入的关键字为依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转向右旋转一次一次先向右旋转先向右旋转再向左旋转再向左旋转426589642895向左旋转一次继续插入关键字继续插入关键字 9单向右

45、旋转单向右旋转A2B1BLBrArhhhLL型A0B0BLBrArhhh旋转后保证中序序列不变旋转后保证中序序列不变A-2B-1BrBLALhhhRR型A0B0BrALBLhhh旋转后保证中序序列不变旋转后保证中序序列不变单向左旋转单向左旋转双向旋转，先左后右双向旋转，先左后右A2B-1ArhBLhLR型CCLh-1Crh-11A-1B0ArhBLhCLh-1Crh-1C0双向旋转，先右后左双向旋转，先右后左B-1A0BrhALhCLh-1Crh-1C0A-2B1BrhALhRL型CLh-1Crh-1C11200120180012028013001200800300120180-1300900

46、120180030-1900450120180030-290045-16001201800300900450600三、三、 B - 树树1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作B-B-树：一种平衡的多路查找树树：一种平衡的多路查找树, ,一棵一棵m m阶的阶的B-B-树或为空树，树或为空树，或为满足以下特性的或为满足以下特性的m m叉树：叉树：树中每个节点至多有树中每个节点至多有m m棵子树棵子树假设根结点不是叶子结点，那么至少有两棵子树假设根结点不是叶子结点，那么至少有两棵子树除根结点之外的一切非终端结点至少有除根结点之外的一切非终端结点至少有m/2m/2 棵子树棵子

47、树一切的非终端结点中包含以下信息数据一切的非终端结点中包含以下信息数据(n,A0,K1,A1,K2,A2,Kn,An)(n,A0,K1,A1,K2,A2,Kn,An) 其中其中Ki(i=1,n)Ki(i=1,n)为关键字，且为关键字，且KiKi+1,(i=1,n-1); KiKi+1,(i=1,n-1); Aj Aj0 0j jn n为指向子树根结点的指针，且为指向子树根结点的指针，且AjAj0 0jnjn 所指子树中一切结点的关键字均小所指子树中一切结点的关键字均小kj+1; Ankj+1; An所指子树中所指子树中 一切结点的关键字均大于一切结点的关键字均大于kn;kn; n nm/2m/

48、2-1-1n nm-1m-1为关键字的个数；为关键字的个数；n+1n+1为子树个为子树个数。数。1351182437811112713934753641994阶B-树，每个节点最多4棵子树，3个关键字。一棵m阶B-树每个节点最多有m棵子树m-1个关键字,最少有m/2棵子树m/2-1个关键字 非叶结点中的多个关键字均自小至大有非叶结点中的多个关键字均自小至大有序陈列，即：序陈列，即：K1 K2 Kn;K1 K2 key1.keynum中查找 i ，i使 得：p-Keyi=kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri;

49、/ q 指示 p 的双亲，在子树中查找 if (found) return (p,i,1); / 查找胜利 else return (q,i,0); / 查找不胜利 Search (Btree P , KeyType K) for (int i=0; iPkeynum &P keyi+1=k; i+); return i;3插入插入1插入后，该结点的关键字个数nm， 不修正指针; 例如在查找不胜利之后，需进展插入。显然，关键字插入的位置必定在最下层的非叶结点，有以下几种情况：2插入后，该结点的关键字个数插入后，该结点的关键字个数 n=m， 那么需进展那么需进展“结点分裂结点分裂，令，令

50、 s = m/2， 在原结点中保管在原结点中保管 A0，K1，。，。， Ks-1，As-1； 建新结点建新结点 As，Ks+1，。，。 ，Kn，An； 将将Ks，p插入双亲结点；例如插入双亲结点；例如3假设双亲为空，那么建新的根结点。假设双亲为空，那么建新的根结点。 例如例如例如例如:以下为以下为 3 阶阶B-树树50 20 40 80 插入关键字插入关键字 = 60, 60 80 90, 60 80 90 90 50 80 60 30, 40 20 30 50 808030 50 和插入的思索相反，首先必需找到待删关键字所和插入的思索相反，首先必需找到待删关键字所在结点，并且要求删除之，假设

51、该结点为最下层的在结点，并且要求删除之，假设该结点为最下层的非终端结点，且其中的关键字数目不小于非终端结点，且其中的关键字数目不小于m/2 ，那么删除完成，否那么要进展那么删除完成，否那么要进展“合并合并操作操作.4删除删除45abt24b53 90e3 12c37d50f61 70g100h下面我们只需讨论删除最小层非终端结点中的关键字情形，下面我们只需讨论删除最小层非终端结点中的关键字情形，分分3种情况讨论：种情况讨论：9084028150 20085 120508090 11584028150 20085 1205060 80删除60与1151208402820085 150508090

52、84028150 20085 12050801208402820085 150508084028150 200855080如在3阶B-树中依次删除关键字12,50，53，37，分为三种情况45abt24b53 90e3 12c37d50f61 70g100h3阶B-树45abt24b53 90e3 c37d50f61 70g100h(1)被删关键字(12)所在节点(c)中的关键字数目不小于m/2那么只须从该节点(c)中删去该关键字(12)和相应指针，树的其他部分不变。删除关键字1245abt24b53 90e3c37d50f61 70g100h2被删关键字(50)所在节点(f)中的关键字数目等

53、于m/2-1,其相邻的某个兄弟结点(g)左兄弟或右兄弟中的关键字数目大于m/2-1，那么将其兄弟结点(g)中的最小或最大关键字(61)上移至双亲结点中，而将双亲结点中小于或大于且紧靠该上移关键字(61)的关键字(53)下移至被删关键字(50)所在节点(f)中。45abt24b61 90e3c37d53f70g100h删除关键字503被删关键字(53)所在节点(f)和其相邻的兄弟结点(g)中的关键字数目均等于m/2-1(1), 假设该节点有右兄弟(g),在删去关键字(53)后，他所在结点(f)中剩余的关键字和指针加上双亲结点(e)中的关键字(61)一同合并到右兄弟结点(g)中。45abt24b9

54、0e3c37d61 70g100h45abt24b61 90e3c37d53f70g100h删除关键字53删除关键字37bt45 90e3 24c61 70g100h45abt24b90e3c37d61 70g100h45abtb90e3 24c61 70g100h假设删除后使双亲结点中的关键字数目小于m/2-1，那么依此类推层层向上合并。是是B-树的一种变型树的一种变型四、四、B+树树B+树树B+B+树是树是B-B-树的变型，树的变型，m m阶的阶的B+B+树和树和m m阶的阶的B-B-树的区树的区别是：别是：关键字个数和子树个数一样多关键字个数和子树个数一样多一切叶子结点中包含全部关键字信

55、息及指向含这一切叶子结点中包含全部关键字信息及指向含这些关键字记录的指针，且叶子节点本身依关键些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。字的大小自小而大顺序链接。一切非终端结点可看成索引，节点中仅含有其子一切非终端结点可看成索引，节点中仅含有其子树中的最大或最小关键字。树中的最大或最小关键字。59 97aroot15 44 59b72 97e10 15c21 37 44d51 59f63 72g85 91 97hsqt3阶B+树1B+树的构造特点：树的构造特点： 每个叶子结点中含有每个叶子结点中含有 n n 个关键字和个关键字和 n n 个指向记录的个指向记录的指针；并

56、且，一切叶子结点彼此相链接构成一个有序链表，指针；并且，一切叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；其头指针指向含最小关键字的结点； 每个非叶结点中的关键字每个非叶结点中的关键字 Ki Ki 即为其相应指针即为其相应指针 Ai Ai 所指所指子树中关键字的最大值或最小值；子树中关键字的最大值或最小值； 一切叶子结点都处在同一层次上，每个叶子结点中关一切叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于键字的个数均介于 m/2m/2和和 m m 之间。之间。59 97aroot15 44 59b72 97e10 15c21 37 44d51 59f63 72g

57、85 91 97hsqt3阶B+树2查找过程查找过程 在在 B+ B+ 树上，既可以进展减少范围的查树上，既可以进展减少范围的查 找，也可以进展顺序查找；找，也可以进展顺序查找； 在进展减少范围的查找时，不论胜利在进展减少范围的查找时，不论胜利 与否，都必需查到叶子结点才干终了；与否，都必需查到叶子结点才干终了； 假设在结点内查找时，给定值假设在结点内查找时，给定值KiKi， 那么那么 应继续在应继续在 Ai Ai 所指子树中进展查找；所指子树中进展查找；3插入和删除的操作插入和删除的操作类似于类似于B-树进展，即必要时，树进展，即必要时，也需求进展结点的也需求进展结点的“分裂分裂或或“归并归

58、并。9.3 哈哈 希希 表表哈希表的相关定义哈希表的相关定义哈希函数的构造方法哈希函数的构造方法处置冲突的方法处置冲突的方法哈希表的查找哈希表的查找哈希表的插入哈希表的插入哈希查找分析哈希查找分析USk1k2k3k5k40H(k1)H(k5)H(k2)=H(k4)H(k3)H(km-1)哈希查找哈希查找根本思想：在记录的存储地址和它的关键根本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素不经过比较，一次存取就能得到所查元素的查找方法。的查找方法。哈希函数哈希函数在记录的关键字与记录的存储地址之间建在记

59、录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映是从关键字空间到存储地址空间的一种映象。象。哈希表的相关定义哈希表的相关定义关键字关键字集合集合存储地址存储地址集合集合hashZhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例如：对于如下例如：对于如下 9 个关键字个关键字设设 哈希函数哈希函数 H(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3ChenZhaoQ

60、ianSunLiWuHanYeDei问题问题: 假设添加关键字假设添加关键字 Zhou , 怎样办？怎样办？能否找到另一个哈希函数？能否找到另一个哈希函数？1) 哈希函数是一个映象，即：哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上， 它的设置很灵敏，只需这个地址集合的它的设置很灵敏，只需这个地址集合的 大小不超出允许范围即可大小不超出允许范围即可;从这个例子可见，从这个例子可见，2) 由于哈希函数是一个紧缩映象，因此，由于哈希函数是一个紧缩映象，因此，在普通情况下，很容易产生在普通情况下，很容易产生“冲突景冲突景象，即：象，即： key1 key2，而，而 f(key1) = f(key2)。3) 很难找到一个不产生冲突的哈希函数。很难找到一个不产