数据结构-查找技术.ppt课件.ppt

1、数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第第 7 章章 查找技术查找技术本章的主要内容是本章的主要内容是:查找的基本概念查找的基本概念线性表的查找技术线性表的查找技术树表的查找技术树表的查找技术散列表的查找技术散列表的查找技术 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社查找的基本概念查找的基本概念关键码关键码：可以标识一个记录的某个数据项。：可以标识一个记录的某个数据项。键值键值：关键码的值。：关键码的值。主关键码主关键码：可以唯一地标识一个记录的关键码。：可以唯一地标识一个记录的关键码。次关键码次关键码：不能：不能唯一地标识一个记录的关键码。唯一地标识一

2、个记录的关键码。7.1 概述概述50女女李爽李爽000525女女齐梅齐梅000447女女刘楠刘楠000325男男张亮张亮000238男男王刚王刚0001年龄年龄性别性别姓名姓名职工号职工号1972年年9月月2003年年7月月1979年年9月月2003年年7月月1990年年4月月参加工作参加工作数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社查找的基本概念查找的基本概念查找查找：在具有相同类型的记录构成的：在具有相同类型的记录构成的集合集合中找出满足中找出满足给给定条件定条件的记录。的记录。7.1 概述概述查找的结果查找的结果：若在查找集合中找到了与给定值相匹配：若在查找集合中找到了

3、与给定值相匹配的记录，则称的记录，则称查找成功查找成功；否则，称；否则，称查找查找失败失败。50女女李爽李爽000525女女齐梅齐梅000447女女刘楠刘楠000325男男张亮张亮000238男男王刚王刚0001年龄年龄性别性别姓名姓名职工号职工号1972年年9月月2003年年7月月1979年年9月月2003年年7月月1990年年4月月参加工作参加工作数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社静态查找静态查找：不涉及插入和删除操作的查找：不涉及插入和删除操作的查找。动态查找动态查找：涉及插入和删除操作的查找。：涉及插入和删除操作的查找。7.1 概述概述查找的基本概念查找的基本

4、概念静态查找适用于：查找集合一经生成，便只对其进行静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；查找之后，集中地进行插入和删除等修改操作；动态查找适用于：查找与插入和删除操作在同一个阶动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。当查找不成功时，要插入被查找的记录。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社7.1 概述

5、概述查找的基本概念查找的基本概念查找结构查找结构：面向查找操作的数据结构面向查找操作的数据结构，即查找基于的，即查找基于的数据结构。数据结构。查找结构查找结构 查找方法查找方法 集合中元素之间不存在明显的组织规律，不便查找。集合中元素之间不存在明显的组织规律，不便查找。集合集合 线性表线性表 树树 表表 散列表散列表 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社本章讨论的查找结构本章讨论的查找结构：线性表线性表：适用于静态查找，主要采用顺序查找技术、：适用于静态查找，主要采用顺序查找技术、折半查找技术。折半查找技术。树表树表：适用于动态查找，主要采用二叉排序树的查找：适用于动态

6、查找，主要采用二叉排序树的查找技术。技术。散列表散列表：静态查找和动态查找均适用，主要采用散列：静态查找和动态查找均适用，主要采用散列技术。技术。7.1 概述概述查找结构查找结构：面向查找操作的数据结构面向查找操作的数据结构，即查找基于的，即查找基于的数据结构。数据结构。查找的基本概念查找的基本概念数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社查找算法的性能查找算法的性能 查找算法时间性能通过关键码的比较次数来度量。查找算法时间性能通过关键码的比较次数来度量。关键码的比较次数与哪些因素有关呢？关键码的比较次数与哪些因素有关呢？算法；算法；问题规模；问题规模；待查关键码在查找集合中

7、的位置；待查关键码在查找集合中的位置；查找频率。查找频率。7.1 概述概述查找频率与算法无关，取决于具体应用。查找频率与算法无关，取决于具体应用。通常假设通常假设pi是已知的。是已知的。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社查找算法的性能查找算法的性能 查找算法时间性能通过关键码的比较次数来度量。查找算法时间性能通过关键码的比较次数来度量。查找算法的时间复杂度是问题规模查找算法的时间复杂度是问题规模n和待查关键码和待查关键码在查找集合中的位置在查找集合中的位置k的函数，记为的函数，记为T(n，k)。同一查找集合、同一查找算法，关键码的比较同一查找集合、同一查找算法，关键码

8、的比较次数与哪些因素有关呢？次数与哪些因素有关呢？7.1 概述概述数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社平均查找长度：平均查找长度：将查找算法进行的关键码的比较次数将查找算法进行的关键码的比较次数的数学期望值定义为的数学期望值定义为平均查找长度平均查找长度。计算公式为：。计算公式为：其中：其中：n：问题规模，查找集合中的记录个数；问题规模，查找集合中的记录个数；pi：查找第查找第i个记录的概率；个记录的概率；ci：查找第查找第i个记录所需的关键码的比较次数。个记录所需的关键码的比较次数。结论结论：ci取决于算法；取决于算法；pi与算法无关，取决于具体应用。与算法无关，取决

9、于具体应用。如果如果pi是已知的，则平均查找长度只是问题规模的函数。是已知的，则平均查找长度只是问题规模的函数。7.1 概述概述查找算法的性能查找算法的性能 ASL=niiicp1数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社顺序查找顺序查找（线性查找）（线性查找）基本思想基本思想：从线性表的一端向另一端逐个将关键码与：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。等的关

10、键码，则查找失败，给出失败信息。10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i7.2 线性表的查找技术线性表的查找技术例：查找例：查找k35iii数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社顺序查找顺序查找（线性查找）（线性查找）7.2 线性表的查找技术线性表的查找技术int SeqSearch1(int r,int n,int k)/数组数组r1 rn存放查找集合存放查找集合 i=n;while(i0&ri!=k)i-;return i;数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社基本思想基本思想：设置：设置“哨兵

11、哨兵”。哨兵就是待查值，将它放。哨兵就是待查值，将它放在查找方向的在查找方向的尽头尽头处，免去了在查找处，免去了在查找过程中每一次比过程中每一次比较后都要判断查找位置是否较后都要判断查找位置是否越界越界，从而提高查找速度，从而提高查找速度。7.2 线性表的查找技术线性表的查找技术改进的顺序查找改进的顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例：查找例：查找k35iii哨兵哨兵35查找方向查找方向数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社基本思想基本思想：设置：设置“哨兵哨兵”。哨兵就是待查值，将它放。哨兵就是待查值，

12、将它放在查找方向的在查找方向的尽头尽头处，免去了在查找处，免去了在查找过程中每一次比过程中每一次比较后都要判断查找位置是否较后都要判断查找位置是否越界越界，从而提高查找速度，从而提高查找速度。7.2 线性表的查找技术线性表的查找技术改进的顺序查找改进的顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例：查找例：查找k25ii25查找方向查找方向iiiiiii数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社int SeqSearch2(int r,int n,int k)/数组数组r1 rn存放查找集合存放查找集合 r0=k;i=

13、n;while(ri!=k)i-;return i;7.2 线性表的查找技术线性表的查找技术改进的顺序查找改进的顺序查找ASL=niicp1+-=niiinp1)1(i=(n+1)/2=O(n)数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社平均查找长度较大，特别是当待查找集合中元素较多平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。时，查找效率较低。7.2 线性表的查找技术线性表的查找技术顺序查找的缺点：顺序查找的缺点：算法简单而且使用面广。算法简单而且使用面广。对表中记录的存储没有任何要求，顺序存储和链接对表中记录的存储没有任何要求，顺序存储和链接存储均可；存储

14、均可；对表中记录的有序性也没有要求，无论记录是否按对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。关键码有序均可。顺序查找的优点：顺序查找的优点：数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社折半查找折半查找使用条件使用条件：线性表中的记录必须按关键码线性表中的记录必须按关键码有序有序；必须采用必须采用顺序顺序存储存储。基本思想基本思想：在有序表中，取：在有序表中，取中间中间记录作为比较对象，记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若若给定值与中间记录的关键码相等，则查找成功；若给定值给定值小于小于中间记录的关键码，则在中间记录的中间记录的关键码

15、，则在中间记录的左半左半区继续查找；若给定值区继续查找；若给定值大于大于中间记录的关键码，则在中间记录的关键码，则在中间记录的中间记录的右半右半区继续查找。不断重复上述过程，直区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。到查找成功，或所查找的区域无记录，查找失败。7.2 线性表的查找技术线性表的查找技术数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社折半查找的基本思想折半查找的基本思想7.2 线性表的查找技术线性表的查找技术 r1 rmid-1 rmid rmid+1 rn 如果如果krmid 查找左半区查找左半区 查找右半区查找右半区k（mid=(

16、1+n)/2）数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社例：查找值为例：查找值为14的记录的过程：的记录的过程：0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 311418147221822low=4mid=4 21high数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社int BinSearch1(int r,int n,int k)/数组数组r1 rn存放查找集合存放查找集合 low=

17、1;high=n;while(low=high)mid=(low+high)/2;if(krmid)low=mid+1;else return mid;return 0;7.2 线性表的查找技术线性表的查找技术折半查找折半查找非递归算法非递归算法数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社int BinSearch2(int r,int low,int high,int k)/数组数组r1 rn存放查找集合存放查找集合 if(lowhigh)return 0;else mid=(low+high)/2;if(krmid)return BinSearch2(r,mid+1,hig

18、h,k);else return mid;7.2 线性表的查找技术线性表的查找技术折半查找折半查找递归算法递归算法数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社折半查找判定树折半查找判定树 判定树判定树：折半查找的过程可以用二叉树来描述，树中折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该的每个结点对应有序表中的一个记录，结点的值为该记录在记录在表中的位置。通常称这个描述折半查找过程的表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称二叉树为折半查找判定树，简称判定树判定树。7.2 线性表的查找技术线性表的查找技术数据结构（数

19、据结构（C+版）版）清华大学出版社清华大学出版社 当当n=0时，折半查找判定树为空；时，折半查找判定树为空；当当n0时，折半查找判定树的根结点是有序表中时，折半查找判定树的根结点是有序表中序号为序号为mid=(n+1)/2的记录，根结点的左子树是与有的记录，根结点的左子树是与有序表序表r1 rmid-1相对应的折半查找判定树，根结相对应的折半查找判定树，根结点的点的右子树是与右子树是与rmid+1 rn相对应的折半查找判相对应的折半查找判定树。定树。7.2 线性表的查找技术线性表的查找技术判定树的构造方法判定树的构造方法数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社7.2 线性表

20、的查找技术线性表的查找技术 11223344510111191089785667内部结点内部结点外部结点外部结点3691011784512判定树的构造方法判定树的构造方法数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社 折半查找有序表（折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元）。若查找表中元素素58，则它将依次与表中，则它将依次与表中 比较大小，比较大小，查找结果是失败。查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社 假定

21、对有序表：（假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答）进行折半查找，试回答下列问题：下列问题：画出描述折半查找过程的判定树；画出描述折半查找过程的判定树；若查找元素若查找元素54，需依次与哪些元素比较？，需依次与哪些元素比较？若查找元素若查找元素90，需依次与哪些元素比较？，需依次与哪些元素比较？假定每个元素的查找概率相等，求查找成功时假定每个元素的查找概率相等，求查找成功时的平均查找长度。的平均查找长度。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社具有具有n个结个结点的折半查找判定树的深度为点的折半查找判定树的深度为

22、 查找成功查找成功：在表中查找任一记录的过程，即是折半查：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。的比较次数等于该记录结点在树中的层数。查找不成功查找不成功：查找失败的过程就是走了一条从根结：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。较次数等于该路径上内部结点的个数。7.2 线性表的查找技术线性表的查找技术。1log2+n折半查找性能分析折半查找性能分析 数据

23、结构（数据结构（C+版）版）清华大学出版社清华大学出版社二叉排序树二叉排序树二叉排序树二叉排序树（也称（也称二叉查找树二叉查找树）：或者是一棵空的二）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：叉树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均若它的左子树不空，则左子树上所有结点的值均小于根结点的值；小于根结点的值；若它的右子树不空，则右子树上所有结点的值均若它的右子树不空，则右子树上所有结点的值均大于根结点的值；大于根结点的值；它的左右子树也都是二叉排序树。它的左右子树也都是二叉排序树。7.3 树表的查找技术树表的查找技术二叉排序树的定义采用的是递归方法。二

24、叉排序树的定义采用的是递归方法。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社二叉排序树二叉排序树 非二叉排序树非二叉排序树二叉排序树二叉排序树7.3 树表的查找技术树表的查找技术6390554258104567837063605582581045678370中序遍历二叉排序树可以得到一个按关键码有序的序列中序遍历二叉排序树可以得到一个按关键码有序的序列 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社二叉排序树的存储结构二叉排序树的存储结构以二叉链表形式存储，类声明如下：以二叉链表形式存储，类声明如下：class BiSortTree public:BiSortTr

25、ee(int a,int n);BiSortTree()();void InsertBST(BiNode*root,BiNode*s);void DeleteBST(BiNode*p,BiNode*f);BiNode*SearchBST(BiNode*root,int k);private:BiNode*root;7.3 树表的查找技术树表的查找技术数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社二叉排序树的插入二叉排序树的插入分析：分析：若二叉排序树为空树，则新插入的结点为新若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子的根结点；否则，新插入的

26、结点必为一个新的叶子结点，其插入位置由查找过程得到。结点，其插入位置由查找过程得到。7.3 树表的查找技术树表的查找技术void InsertBST(BiNode*root,BiNode*s);数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社例：插入值为例：插入值为98的结点的结点7.3 树表的查找技术树表的查找技术63559058 70985563root90587098sroot数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社void BiSortTree:InsertBST(BiNode*root,BiNode*s)if(root=NULL)root=s;else

27、 if(s-datadata)InsertBST(root-lchild,s);else InsertBST(root-rchild,s);7.3 树表的查找技术树表的查找技术二叉排序树的插入算法二叉排序树的插入算法数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社二叉排序树的构造二叉排序树的构造从空的二叉排序树开始，依次插入一个个结点从空的二叉排序树开始，依次插入一个个结点。例：关键码集合为例：关键码集合为63，90，70，55，58，二二叉排序树的构造过程为：叉排序树的构造过程为：7.3 树表的查找技术树表的查找技术63559058 70数据结构（数据结构（C+版）版）清华大学出

28、版社清华大学出版社BiSortTree:BiSortTree(int r,int n)for(i=0;in;i+)s=new BiNode;s-data=ri;s-lchild=s-rchild=NULL;InsertBST(root,s);7.3 树表的查找技术树表的查找技术二叉排序树的构造算法二叉排序树的构造算法数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社 一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列变成一个有序序列;每次插入的新结点都是二叉排序树上新的叶子每次插入的新结点都是二叉排序树上新的叶子结点结点;找到插入位置后，

29、不必移动其它结点，仅需修找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；改某个结点的指针；在左子树在左子树/右子树的查找过程与在整棵树上查右子树的查找过程与在整棵树上查找过程相同；找过程相同；新插入的结点没有破坏原有结点之间的关系。新插入的结点没有破坏原有结点之间的关系。小小 结：结：7.3 树表的查找技术树表的查找技术数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社 在一棵空的二叉查找树中依次插入关键在一棵空的二叉查找树中依次插入关键字序列为字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。，请画出所得到的二叉查找树。数据结构（数据结

30、构（C+版）版）清华大学出版社清华大学出版社二叉排序树的删除二叉排序树的删除在二叉排序树上删除某个结点之后，仍然保持二叉排在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。序树的特性。分三种情况讨论：分三种情况讨论：被删除的结点是叶子；被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点只有左子树或者只有右子树；被删除的结点既有左子树，也有右子树被删除的结点既有左子树，也有右子树。7.3 树表的查找技术树表的查找技术数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社情况情况1被删除的结点是叶子结点被删除的结点是叶子结点7.3 树表的查找技术树表的查找技术50

31、302080908588403532503020809085403532操作：操作：将双亲结点中相应指针域的值改为空。将双亲结点中相应指针域的值改为空。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社情况情况2被删除的结点只有左子树或者只有右子被删除的结点只有左子树或者只有右子树树操作：操作：将双亲结点的相应指针域的值指向被删除将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。结点的左子树（或右子树）。7.3 树表的查找技术树表的查找技术50302080908588403532503020908588403532数据结构（数据结构（C+版）版）清华大学出版社清华大学出版

32、社情况情况3被删除的结点既有左子树也有右子树被删除的结点既有左子树也有右子树操作：操作：以其前驱（左子树中的最大值）替代以其前驱（左子树中的最大值）替代之，然后再删除该前驱结点。之，然后再删除该前驱结点。7.3 树表的查找技术树表的查找技术50302080908588403532403020809085883532数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社1.若结点若结点p是叶子，则直接删除结点是叶子，则直接删除结点p；2.若结点若结点p只有左子树，则只需重接只有左子树，则只需重接p的左子树；的左子树；若结点若结点p只有右子树，则只需重接只有右子树，则只需重接p的右子树；的右

33、子树；3.若结点若结点p的左右子树均不空，则的左右子树均不空，则 3.1 查找结点查找结点p的右子树上的最左下结点的右子树上的最左下结点s及其双亲结点及其双亲结点par；3.2 将结点将结点s数据域替换到被删结点数据域替换到被删结点p的数据域；的数据域；3.3 若结点若结点p的右孩子无左子树，的右孩子无左子树，则将则将s的右子树接到的右子树接到par的右子树上；的右子树上；否则，将否则，将s的右子树接到结点的右子树接到结点par的左子树上；的左子树上；3.4 删除结点删除结点s；7.3 树表的查找技术树表的查找技术二叉排序树的删除算法二叉排序树的删除算法伪代码伪代码数据结构（数据结构（C+版）

34、版）清华大学出版社清华大学出版社二叉排序树的查找二叉排序树的查找在二叉排序树中查找给定值在二叉排序树中查找给定值k的过程是：的过程是：若若root是空树，则查找失败；是空树，则查找失败；若若kroot-data，则查找成功；否则则查找成功；否则 若若kroot-data，则在则在root的左子树上查找；否则的左子树上查找；否则 在在root的右子树上查找。的右子树上查找。上述过程一直持续到上述过程一直持续到k被找到或者待查找的子树为被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。空，如果待查找的子树为空，则查找失败。二叉排序树的查找效率在于只需查找二个子树之一。二叉排序树的查找效

35、率在于只需查找二个子树之一。7.3 树表的查找技术树表的查找技术数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社例：在二叉排序树中查找关键字值为例：在二叉排序树中查找关键字值为35，95的过程：的过程：7.3 树表的查找技术树表的查找技术50302080908588403532二叉排序树的查找二叉排序树的查找50302080908588403532数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社BiNode*BiSortTree:SearchBST(BiNode*root,int k)if(root=NULL)return NULL；else if(root-data=

36、k)return root;else if(k(k-data)return SearchBST(root-lchild,k);else return SearchBST(root-rchild,k);7.3 树表的查找技术树表的查找技术二叉排序树的查找二叉排序树的查找数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社二叉排序树的查找性能分析二叉排序树的查找性能分析由序列由序列3,1,2,5,4得到二叉排序树：得到二叉排序树：由序列由序列1,2,3,4,5得到二叉排序树：得到二叉排序树：ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2二叉排序树的查找性能取决于二叉排序树的形状，二叉排序树的查找性能取决于二叉排序树的形状，在在O(log2n)和和O(n)之间。之间。7.3 树表的查找技术树表的查找技术1234531254