1、 本章中介绍下列主要内容：本章中介绍下列主要内容：l 静态查找表及查找算法：顺序查找、折半查找静态查找表及查找算法：顺序查找、折半查找l 动态查找表及查找算法：二叉排序树动态查找表及查找算法：二叉排序树l 哈希表及查找算法哈希表及查找算法7.1 基本概念基本概念7.2 静态查找静态查找7.3 动态查找动态查找7.4 哈希表哈希表7.5 应用举例应用举例 查找表查找表 用于查找的数据元素集合称为查找表。查找表用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。由同一类型的数据元素（或记录）构成。静态查找表静态查找表 若只对查找表进行如下两种操作：若只对查找表进行如下两种操
2、作：（1）在查找表中查看某个特定的数据元素是否在查找表中，）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为）检索某个特定元素的各种属性，则称这类查找表为静静态查找表态查找表。静态查找表在查找过程中查找表本身不发生变。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为化。对静态查找表进行的查找操作称为静态查找静态查找。动态查找表动态查找表 若在查找过程中可以将查找表中不存若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为素，则称
3、这类查找表为动态查找表动态查找表。动态查找表在查。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为的查找操作称为动态查找动态查找。关键字关键字 是数据元素中的某个数据项。唯一能标识是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为值互不相同，我们称这种关键字为主关键字主关键字；若查找；若查找表中某些元素的关键字值相同，称这种关键字为表中某些元素的关键字值相同，称这种关键字为次关次关键字键字。例如，银行帐户中的帐号是主
4、关键字，而姓名。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。是次关键字。查找查找 在数据元素集合中查找满足某种条件的数据在数据元素集合中查找满足某种条件的数据元素的过程称为元素的过程称为查找查找。最简单且最常用的查找条件是。最简单且最常用的查找条件是“关键字值等于某个给定值关键字值等于某个给定值”，在查找表搜索关键字，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样等于给定值的数据元素（或记录）。若表中存在这样的记录，则称的记录，则称查找成功查找成功，此时的查找结果应给出找到，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中记录的全部信息或指示找到
5、记录的存储位置；若表中不存在关键字等于给定值的记录，则称不存在关键字等于给定值的记录，则称查找不成功查找不成功，此时查找的结果可以给出一个空记录或空指针。若按此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。找，结果可能是多个记录，即结果可能不唯一。查找表的存储结构查找表的存储结构 查找表是一种非常灵活的数据查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构
6、。本提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。结构的各种查找算法。查找算法的时间效率查找算法的时间效率 查找过程的主要操作是关键查找过程的主要操作是关键字的比较，所以通常以字的比较，所以通常以“平均比较次数平均比较次数”来衡量查找来衡量查找算法的时间效率。算法的时间效率。查找查找也叫检索，是根据给定的某个值，在表中确定一也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素个关键字等于给定值的记录或数据元素关键字关键字是数据元素中某个数据项的值，它可以标识一
7、是数据元素中某个数据项的值，它可以标识一个数据元素个数据元素查找方法评价查找方法评价查找速度查找速度占用存储空间多少占用存储空间多少算法本身复杂程度算法本身复杂程度平均查找长度平均查找长度ASL(Average Search Length)ASL(Average Search Length)：为确定记：为确定记录在表中的位置，需和给定值进行比较的关键字的个录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的数的期望值叫查找算法的 正如本章第一节所述：静态查找是指在静态查找正如本章第一节所述：静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数表上进行的查找操作，
8、在查找表中查找满足条件的数据元素的存储位置或各种属性。本节将讨论以线性结据元素的存储位置或各种属性。本节将讨论以线性结构表示的静态查找表及相应的查找算法。构表示的静态查找表及相应的查找算法。7.2.1 7.2.1 顺序查找顺序查找1.1.顺序查找的基本思想顺序查找的基本思想 顺序查找是一种最简单的查找方法。其基本思想顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与元素的关键
9、字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。不相等，则查找失败，返回查找失败标志。/*顺序存储结构顺序存储结构 */typedef structtypedef struct ElemType ElemType *elemelem；/*数组基址数组基址 */int int length length；/*表长度表长度 */S_TBL S_TBL；/*链式存储结构结点类型链式存储结构结点
10、类型 */typedef structtypedef struct NODE NODE ElemType elem ElemType elem；/*结点的值域结点的值域 */structstruct NODE NODE *nextnext；/*下一个结点指针域下一个结点指针域 */NodeTypeNodeType；7.1 顺序查找顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较值的比较算法描述算法描述i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找646
11、4监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2.查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1顺序查找方法的顺序查找方法的ASL212)1(11111nnnnincpASLnpniniiii则概率相等设表中每个元素的查找niiicpASLn1个记录的表，对含有 7.2.2 7.2.2 折半查找折半查找1.1.折半查找的基本思想折半查找的基本思想 折半查找要求查找表用顺序存储结构存放且各数折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进
12、行查找。折半查找只适用于对有序顺序表进行查找。7.2 折半查找折半查找查找过程：每次将待查记录所在区间缩小一半查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表适用条件：采用顺序存储结构的有序表算法实现算法实现设表长为设表长为n，low、high和和mid分别指向待查元素所在区分别指向待查元素所在区间的上界、下界和中点间的上界、下界和中点,k为给定值为给定值初始时，令初始时，令low=1,high=n,mid=(low+high)/2 让让k与与mid指向的记录比较指向的记录比较若若k=rmid.key，查找成功，查找成功若若krmid.key，则，则low=mid+1
13、重复上述操作，直至重复上述操作，直至lowhigh时，查找失败时，查找失败算法描述算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lo
14、whighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：1 2 3 4 5 6 7 8 9
15、10 115 13 19 21 37 56 64 75 80 88 92算法评价算法评价判定树：描述查找过程的二叉树叫判定树：描述查找过程的二叉树叫有有n个结点的判定树的深度为个结点的判定树的深度为 log2n+1折半查找法在查找过程中进行的比较次数最多不超过其折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度判定树的深度折半查找的折半查找的ASL1)1(log1)1(log12111),1(log,122211112nnnnjncncpASLnphnhnhjjniiniiiih则：概率相等设表中每个记录的查找的满二叉树即判定树是深度为设表长7.3 分块查找分块查找查找过程：将表分成
16、几块，块内无序，块间有序；先确定查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找待查记录所在块，再在块内查找适用条件：分块有序表适用条件：分块有序表算法实现算法实现用数组存放待查记录用数组存放待查记录,每个数据元素至少含有关键字域每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针本块第一个结点的指针算法描述算法描述如：一个含全校学生的查找表首先可按系分类，每个系内按年级分类，年级内则按班分类。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1
17、7 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38子表中最大的关键字起始地址分块查找方法评价分块查找方法评价2)1(log)2(1)(21212111)1(211ssnASLssnsbisjbASLsbnLLLLASLbssibjbswbwbbs：用折半查找确定所在块：用顺序查找确定所在块查找概率相等，则：记录的个记录，并设表中每个块，每块含的表平均分成若将表长为均查找长度在块中查找元素的平块的平均查找长度查找索引表确定所在其中：ASL最大最小两者之间表结构有序表、无序表 有序表分块有序表存储结
18、构顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找 7.3.1 7.3.1 二叉排序树二叉排序树 二叉排序树是一种常用的动态查找表，下面首先给二叉排序树是一种常用的动态查找表，下面首先给出它的非递归形式。出它的非递归形式。二叉排序树是一棵二叉树，它或者为空，或者具有二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：如下性质：（1）任一非终端结点若有左孩子，则该结点的关键）任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值。字值大于其左孩子结点的关键字值。（2）任一非终端结点若有右孩子，则该结点的关键字）任一非终端结点若有右孩子，
19、则该结点的关键字值小于其右孩子结点的关键字值。值小于其右孩子结点的关键字值。二叉排序树也可以用递归的形式定义，即二叉排序树二叉排序树也可以用递归的形式定义，即二叉排序树是一棵树，它或者为空，或者具有如下性质：是一棵树，它或者为空，或者具有如下性质：（1）若它的左子树非空，则其左子树所有结点的关键）若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值。字值均小于其根结点的关键字值。（2）若它的右子树非空，则其右子树所有结点的关键）若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。字值均大于其根结点的关键字值。（3）它的左右子树都是二叉排序树。）它的左右子树
20、都是二叉排序树。例如，由关键字值序列（例如，由关键字值序列（62,15,68,46,65,12,57,79,35）构成的一棵二叉排序树如图构成的一棵二叉排序树如图7-4所示。所示。判断该二叉树是否为二叉排序树 图图 7-4 如果对上述二叉排序树进行中根遍历可以得到一如果对上述二叉排序树进行中根遍历可以得到一个关键字有序序列（个关键字有序序列（12,15,35,46,57,62,65,68,79），这），这是二叉排序树的一个重要特征，也正是由此将其称为是二叉排序树的一个重要特征，也正是由此将其称为“二叉排序树二叉排序树”。7.3.2 7.3.2 二叉排序树的查找二叉排序树的查找 二叉排序树的结构
21、定义中可看到：一棵非空二叉二叉排序树的结构定义中可看到：一棵非空二叉排序树中根结点的关键字值大于其左子树上所有结点排序树中根结点的关键字值大于其左子树上所有结点的关键字值，而小于其右子树上所有结点的关键字值，的关键字值，而小于其右子树上所有结点的关键字值，所以在二叉排序树中查找一个关键字值为所以在二叉排序树中查找一个关键字值为k 的结点的的结点的基本思想是：用给定值基本思想是：用给定值k与根结点关键字值比较，如果与根结点关键字值比较，如果k小于根结点的值，则要找的结点只可能在左子树中，小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查所以继续在左子树中
22、查找，否则将继续在右子树中查找，依此方法，查找下去，至直查找成功或查找失败找，依此方法，查找下去，至直查找成功或查找失败为止。二叉排序树查找的过程描述如下：为止。二叉排序树查找的过程描述如下：（1）若二叉树为空树，则查找失败，）若二叉树为空树，则查找失败，（2）将给定值）将给定值k 与根结点的关键字值比较，若相等，与根结点的关键字值比较，若相等，则查找成功，则查找成功，（3）若根结点的关键字值小于给定值）若根结点的关键字值小于给定值k，则在左子，则在左子树中继续搜索，树中继续搜索，（4）否则，在右子树中继续查找。）否则，在右子树中继续查找。假定二叉排序树的链式存储结构的类型定义如下：假定二叉排
23、序树的链式存储结构的类型定义如下：二叉排序树查找过程的描述是一个递归过程，若用二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：链式存储结构存储，其查找操作的递归算法如下所示：typedef struct NODE ElemTypeelem;/*数据元素字段数据元素字段*/struct NODE*lc,*rc;/*左、右指针字段左、右指针字段*/NodeType;/*二叉树结点类型二叉树结点类型*/int SearchElem(NodeType*t,NodeType*p,NodeType*q,KeyType kx)/*在二叉排序树在二叉排序树t上查找关
24、键码为上查找关键码为kx的元素，若找到，返回的元素，若找到，返回1，且，且q指向该结指向该结点，点，p指向其父结点；指向其父结点；*/*否则，返回否则，返回0，且，且p指向查找失败的最后一个结点指向查找失败的最后一个结点*/intflag=0;*q=t;while(*q)/*从根结点开始查找从根结点开始查找*/if(kx(*q)-elem.key)/*kx大于当前结点大于当前结点*q的元素关键码的元素关键码*/*p=*q;*q=(*q)-rc;/*将当前结点将当前结点*q的右子女置为新根的右子女置为新根*/elseif(kxelem.key)/*kx小于当前结点小于当前结点*q的元素关键码的元
25、素关键码*/*p=*q;*q=(*q)-lc;/*将当前结点将当前结点*q的左子女置为新根的左子女置为新根*/elseflag=1;break;/*查找成功，返回查找成功，返回*/*while*/return flag;int SearchBST(BSTree T,KeyType kval,BSTree f,BSTree&p)/根指针根指针T所指二叉查找树中递归查找关键字等于所指二叉查找树中递归查找关键字等于kval的数据元素的数据元素,若查找成若查找成/功功,则指针则指针p指向该数据元素结点指向该数据元素结点,并返回并返回TRUE,否则指针否则指针p指向指向查找路径上访查找路径上访/问的最后
26、一个结点并返回问的最后一个结点并返回FALSE,指针指针f指向指向T的双亲的双亲,其初始调其初始调用值为用值为NULLif(!T)p=f;return 0;/查找不成功查找不成功else if(key=T-data.key)p=T;return 1;/查找成功查找成功else if(key data.key)return SearchBST(T-lchild,key,T,p);/返回在左子树中继续返回在左子树中继续查找所得结果查找所得结果else return SearchBST(T-rchild,key,T,p);/返回在右子树中继续返回在右子树中继续查找所得结果查找所得结果/SearchB
27、ST 7.3.3 7.3.3 二叉排序树的插入二叉排序树的插入 在一棵二叉排序树中插入一个结点可以用一个递归在一棵二叉排序树中插入一个结点可以用一个递归的过程实现，即：若二叉排序树为空，则新结点作为的过程实现，即：若二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。点的关键字值大于根结点的值，则插入在右子树上。下面是二叉排序树插入操作的递归算法。下面是二叉排序树插入操作的递归算法。int
28、InsertNode(NodeType*t,KeyType kx)/*在二叉排序树在二叉排序树*t上插入关键码为上插入关键码为kx的结点的结点*/NodeType*p=*t,*q,*s;int flag=0;if(!SearchElem(*t,&p,&q,kx);/*在在*t为根的子树上查找为根的子树上查找*/s=(NodeType*)malloc(sizeof(NodeType);/*申请结点，并赋申请结点，并赋值值*/s-elem.key=kx;s-lc=NULL;s-rc=NULL;flag=1;/*设置插入成功标志设置插入成功标志*/if(!p)t=s;/*向空树中插入时向空树中插入时
29、*/elseif(kxp-elem.key)p-rc=s;/*插入结点为插入结点为p的右子女的右子女*/elsep-lc=s;/*插入结点为插入结点为p的左子女的左子女*/这个算法也可以用非递归的形式实现，如下所示：这个算法也可以用非递归的形式实现，如下所示：void bt_insert 2(Bin_Sort_Tree*bt,Bin_Sort_Tree_Node*pn)p=bt;while(p!=NULL&p-key!=pn-key)q=p;if(p-key pn-key)p=p-lchild;else p=p-rchild;if(p=NULL)if(q-key pn-key)q-lchild
30、=pn;else q-rchild=pn-key;利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想为：由一棵空二叉树开始，经过一系列的查找插操作，其基本思想为：由一棵空二叉树开始，经过一系列的查找插入操作生成一棵二叉排序树。入操作生成一棵二叉排序树。上面曾提及，由于对二叉查找树进行中序遍历得到的是一个有序序列，上面曾提及，由于对二叉查找树进行中序遍历得到的是一个有序序列，所以二叉查找树实质上是一个有序表。则由上述插入过程可见，可所以二叉查找树实质上是一个有序表。则由上述插入过程可见，可以通过生成一棵二叉查找树将
31、一个以通过生成一棵二叉查找树将一个无序序列无序序列变为一个变为一个有序序列有序序列，由此二叉查找树又称由此二叉查找树又称二叉排序树二叉排序树 例如，由结点关键字序列例如，由结点关键字序列（62,15,68,46,65,12,57,79,35）构造二叉排序树的过程为：从空二叉树开）构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排序树中插入，在插始，依次将每个结点插入到二叉排序树中插入，在插入每个结点时都是从根结点开始搜索插入位置，找到入每个结点时都是从根结点开始搜索插入位置，找到插入位置后，将新结点作为叶子结点插入，经过插入位置后，将新结点作为叶子结点插入，经过9次的次的查找和
32、插入操作，建成由这查找和插入操作，建成由这9个结点组成的二叉排序树。个结点组成的二叉排序树。创建二叉排序树的算法如下：创建二叉排序树的算法如下：Bin_Sort_Tree_Node*bt_bulid(Bin_Sort_Tree a,int n)/在数组在数组a的的a1an单元中存放着将要构成二叉排序单元中存放着将要构成二叉排序树的树的n个结点内容个结点内容 bt=NULL;for(i=1;i key=ai.key;p-otheritem=ai.otheritem;p-lchile=NULL;p-rchile=NULL;bt_insert1(&bt,p);return(bt);7.3.4 7.3
33、.4 二叉排序树的删除二叉排序树的删除 在一棵二叉树上，删除其中某个结点将隔断其祖先和子在一棵二叉树上，删除其中某个结点将隔断其祖先和子孙的关系，因此在二叉树的抽象数据类型的定义中只孙的关系，因此在二叉树的抽象数据类型的定义中只有删除一棵子树的基本操作，而没有删除一个结点的有删除一棵子树的基本操作，而没有删除一个结点的基本操作。而对二叉查找树而言，由于它表示的是动基本操作。而对二叉查找树而言，由于它表示的是动态查找表，因此可以并有必要进行删除一个结点的操态查找表，因此可以并有必要进行删除一个结点的操作。作。下面分四种情况讨论一下如何确保从二叉树中删除一个下面分四种情况讨论一下如何确保从二叉树中
34、删除一个结点后，不会影响二叉排序树的性质：结点后，不会影响二叉排序树的性质：（1）若要删除的结点为叶子结点，可以直接进行删）若要删除的结点为叶子结点，可以直接进行删除。除。（2）若要删除结点有右子树，但无左子树，可用其）若要删除结点有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。右子树的根结点取代要删除结点的位置。（3）若要删除结点有左子树，但无右子树，可用其）若要删除结点有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位置，与步骤左子树的根结点取代要删除结点的位置，与步骤类似。类似。（4）若要删除结点的左右子树均非空，则首先找到）若要删除结点的左右子树均非空，则首先
35、找到要删除结点的右子树中关键字值最小的结点（即子树中要删除结点的右子树中关键字值最小的结点（即子树中最左结点），利用上面的方法将该结点从右子树中删除，最左结点），利用上面的方法将该结点从右子树中删除，并用它取代要删除结点的位置，这样处理的结果一定能并用它取代要删除结点的位置，这样处理的结果一定能够保证删除结点后二叉树的性质不变。够保证删除结点后二叉树的性质不变。Int DeleteBST(BiTree&T,KeyType kval)/若二叉查找树若二叉查找树T中存在关键字等于中存在关键字等于 kval 的数据元素时，则删除的数据元素时，则删除/该数据元素结点该数据元素结点*p，并返回，并返回
36、TRUE；否则返回；否则返回 FALSEif(!T)return 0;/不存在关键字等于不存在关键字等于kval的数据元素的数据元素else if(kval=T-data.key)DeleteNode(T);/找到关键字等于找到关键字等于 kval 的数据元素的数据元素return 1;else if(kval data.key)return DeleteBST(T-lchild,kval);/返回在左子树上查找的结果返回在左子树上查找的结果else return DeleteBST(T-rchild,kval);/返回在右子树上查找的结果返回在右子树上查找的结果/else/DeleteBST
37、其中删除操作过程如下所描述：其中删除操作过程如下所描述：void DeleteNode(BiTree&p)/从二叉查找树中删除结点从二叉查找树中删除结点 p，并重接它的左或右子树，并重接它的左或右子树if(!p-rchild)/右子树空则只需重接它的左子树右子树空则只需重接它的左子树q=p;p=p-lchild;delete q;else if(!p-lchild)/只需重接它的右子树只需重接它的右子树q=p;p=p-rchild;delete q;else/左右子树均不空左右子树均不空q=p;s=p-lchild;while(!s-rchild)q=s;s=s-rchild;p-data=s
38、-data;/s 指向被删结点的前驱指向被删结点的前驱if(q!=p)q-rchild=s-lchild;else q-lchild=s-lchild;/重接重接*q 的左子树的左子树delete s;/Delete 对删除操作对删除操作 需作三点说明：需作三点说明：(1)叶子结点的情况可归入到叶子结点的情况可归入到“右子树空右子树空”的情况，的情况，此时因左子树也空，自然此时因左子树也空，自然 p=NULL；(2)注意，注意，T在函数在函数 DeleteBST 中是一个递归调用的引中是一个递归调用的引用型参数，第一次调用时的参数是指向根结点的指针，用型参数，第一次调用时的参数是指向根结点的指
39、针，当继续在子树中进行查找时，自然就是双亲结点的左当继续在子树中进行查找时，自然就是双亲结点的左指针或右指针，因此在函数指针或右指针，因此在函数 DeleteNode(p)中修改指针中修改指针 p，实际上修改的是被删结点的双亲结点的指针域；，实际上修改的是被删结点的双亲结点的指针域；(3)在被删结点的左右子树均不空时，需删除其在被删结点的左右子树均不空时，需删除其 前驱前驱结点结点*s，一般情况下应将，一般情况下应将*s 的左子树接为其双亲的的左子树接为其双亲的右子树，但当右子树，但当*s 即为被删结点的左子树根时，应将即为被删结点的左子树根时，应将*s 的左子树接为其双亲的左子树。的左子树接
40、为其双亲的左子树。从二叉查找树的查找过程可见，二叉查找树的查找性能从二叉查找树的查找过程可见，二叉查找树的查找性能取决于它的深度，然而由于二叉查找树是在查找过程取决于它的深度，然而由于二叉查找树是在查找过程中逐个插入构成，因此它的深度取决于关键字先后插中逐个插入构成，因此它的深度取决于关键字先后插入的次序。例如，含关键字入的次序。例如，含关键字1,2,3,4,5的二叉查找树，其的二叉查找树，其深度可能为深度可能为3或或4或或5，若按，若按1,2,3,4,5的次序得到的二叉的次序得到的二叉查找树的深度为查找树的深度为5，若按，若按3,1,2,4,5的次序得到的二叉查的次序得到的二叉查找树的深度则
41、为找树的深度则为3 由此需要考察它的平均性能。由此需要考察它的平均性能。不失一般性，假设在不失一般性，假设在 n 个关键字的序列中，个关键字的序列中，k个关键字个关键字小于第小于第1个关键字，个关键字，n-k-1 个关键字大于第个关键字大于第1个关键字，个关键字，则由它生成的二叉查找树的左子树中含则由它生成的二叉查找树的左子树中含 k 个结点，右个结点，右子树中含子树中含 n-k-1 个结点，其平均查找长度是个结点，其平均查找长度是 n 和和 k 的的函数，设为函数，设为 P(n,k)0kn-1。假设含假设含 n 个结点的二叉查找树的平均查找长度为个结点的二叉查找树的平均查找长度为 P(n)，
42、并假设生成二叉查找树是一个，并假设生成二叉查找树是一个“随机随机”序列序列（即（即 k 取取0至至 n-1 中任一值的可能性相同），则中任一值的可能性相同），则 而在等概率查找的情况下，而在等概率查找的情况下，由此可得，由此可得，这是一个递归方程，可求得其解为：这是一个递归方程，可求得其解为：由此可见，在随机的情况下，二叉查找树的查找性能是由此可见，在随机的情况下，二叉查找树的查找性能是和和 logn 等数量级的。等数量级的。称二叉树为称二叉树为“平衡平衡”指的是，它或是空树，或具有下列特指的是，它或是空树，或具有下列特性：其左子树和右子树都是平衡二叉树，且左右子树深性：其左子树和右子树都是平
43、衡二叉树，且左右子树深度之差的绝对值不大于度之差的绝对值不大于1。例如右侧上的两棵二叉树为平。例如右侧上的两棵二叉树为平衡树，右侧下的两棵二叉树不是平衡树。树中结点内的衡树，右侧下的两棵二叉树不是平衡树。树中结点内的数值称作结点的数值称作结点的“平衡因子平衡因子”，定义为左子树的深度减，定义为左子树的深度减去右子树的深度。换句话说，平衡树上所有结点的平衡去右子树的深度。换句话说，平衡树上所有结点的平衡因子的绝对值均不大于因子的绝对值均不大于1。平衡平衡“处理的原则是保证二叉查找树始终处于平衡状态。处理的原则是保证二叉查找树始终处于平衡状态。从空树起（空树是平衡树），每插入一个关键字都需要从空树
44、起（空树是平衡树），每插入一个关键字都需要检查二叉查找树是否失去平衡，如因插入新的结点引起检查二叉查找树是否失去平衡，如因插入新的结点引起不平衡，则需对它进行不平衡，则需对它进行”平衡旋转平衡旋转“处理处理 为什么只需要对为什么只需要对最小不平衡子树最小不平衡子树进行旋转处理？进行旋转处理？因为经过旋转处理之后的子树的深度和插入新的关键字因为经过旋转处理之后的子树的深度和插入新的关键字之前的子树深度相同，因而不因插入而改变其所有祖先之前的子树深度相同，因而不因插入而改变其所有祖先结点的平衡因子的值。结点的平衡因子的值。假设关键字序列为假设关键字序列为5,4,2,8,6,9 从空树起，依次插入从
45、空树起，依次插入5和和4之后，二叉查找树仍为平衡树，之后，二叉查找树仍为平衡树，但在插入但在插入2之后，它不再是平衡树。之后，它不再是平衡树。所谓所谓平衡旋转平衡旋转处理是，在保持处理是，在保持查找树查找树的特性前提下的特性前提下改变结点之间的关系。例如在此时的左子树深度偏大的改变结点之间的关系。例如在此时的左子树深度偏大的情况下，令左子树根为整棵树的根，而让原来的根结点情况下，令左子树根为整棵树的根，而让原来的根结点成为它的右子树根。在继续插入关键字成为它的右子树根。在继续插入关键字8和和6之后，二叉之后，二叉查找树重新失去平衡，此时因为以查找树重新失去平衡，此时因为以5为根的子树为为根的子
46、树为最小最小不平衡子树不平衡子树，故仅需对以，故仅需对以5为根的子树进行旋转处理，为根的子树进行旋转处理，但由于是因为在但由于是因为在的的右子树的左子树右子树的左子树上插入结点引起上插入结点引起的不平衡，则不能简单地进行向左旋转，而是首先令的不平衡，则不能简单地进行向左旋转，而是首先令为为的左子树根（向右旋转），然后令的左子树根（向右旋转），然后令为为的右子树的右子树根（向左旋转）。最后由于插入关键字根（向左旋转）。最后由于插入关键字9使查找树失去使查找树失去平衡，此时以平衡，此时以为根的二叉树是最小不平衡子树，并且为根的二叉树是最小不平衡子树，并且因为是在因为是在的的右子树的右子树右子树的右
47、子树上插入结点引起的不平上插入结点引起的不平衡，故仅需进行一次衡，故仅需进行一次向左旋转向左旋转处理即可。处理即可。7.4 哈希查找哈希查找基本思想：在记录的存储地址和它的关键字之间建立基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法取就能得到所查元素的查找方法定义定义哈希函数哈希函数在记录的关键字与记录的存储地址在记录的关键字与记录的存储地址之间建立的一种对应关系叫之间建立的一种对应关系叫哈希函数是一种映象，是从关键字空间到存储哈希函数是一种映象，是从关键字空间到存储地址空间的一
48、种映象地址空间的一种映象哈希函数可写成：哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素是表中的一个元素addr(ai)是是ai的存储地址的存储地址ki是是ai的关键字的关键字关键字集合存储地址集合hash哈希表哈希表应用哈希函数，由记录的关键字确定记录在应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫表中的地址，并将记录放入此地址，这样构成的表叫哈希查找哈希查找又叫散列查找，利用哈希函数进行查找的又叫散列查找，利用哈希函数进行查找的过程叫过程叫例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族.1 北京2 上海.以编号作关键字
49、，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19从例子可见：从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之要使任何关键字的哈希函数值都落在表长允许的范围之内即可内即可冲突：冲突：key1 key2，但，但H(key1)=H(key2)的现象叫的现象叫同义词：具有相同函数值的两个关键字同义词：具有相同函数值的两个关键字哈希函数通常
50、是一种压缩映象，所以冲突不可避免哈希函数通常是一种压缩映象，所以冲突不可避免，只能，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法尽量减少；同时，冲突发生后，应该有处理冲突的方法取关键字或关键字的某个线性函数值为哈希地址。如年龄；取关键字或关键字的某个线性函数值为哈希地址。如年龄；E.G.：人口普查：人口普查：H(age)=ageAge ：1 2.98 99 100Hash address：1 2.98 99 100H(year)=year-1900Birth year :1900 1901 1902.1998 1999Hash address:0 1 2 .98 99特点：简单、无冲突
