有序表的查找: 折半查找( Binary search) 确定待查记录的区间,逐步缩小范围直到找到或找不到该记 录为山 例子:数据元素有序表如下查找关键字key=21的数据元素 21(05,13,19,21,37,56,64,75,80,88,92) la下标:01234567891011 05,13,19,21,37,56,64,75,80,88,92 个1ow 个mid 个high d=[(low+high)/2];key=ST.elem[mid].key查找成功; 口当key〈ST. elem[mid.key时,下一个待查区间为[low,mid-1] 05,13,19,21,37,56,64,75,80,88,92 0个1ow个mid个high D当key>ST.elem[mid.key时下一个待查区间为mid+1,high]
有序表的查找: 折半查找（Binary Search） 确定待查记录的区间，逐步缩小范围直到找到或找不到该记 录为止。 例子： 数据元素有序表如下,查找关键字key=21的数据元素。 21(05，13，19，21，37，56，64，75，80，88，92） 下标: 0 1 2 3 4 5 6 7 8 9 10 11 05，13，19，21，37，56，64，75，80，88，92 low mid high mid = [(low+high)/2]; key=ST.elem[mid].key查找成功; 当key<ST.elem[mid].key时,下一个待查区间为[low,mid-1] 05，13，19，21，37，56，64，75，80，88，92 low mid high 当key>ST.elem[mid].key时下一个待查区间为[mid+1,high]
折半查找的性能分析 查找上例中所有元素的判定二叉树为 6 判定树上每个结点需要的 查找次数刚好为该结点所 在的层数 查找成功时查找次数不会 超过判定树的深度 n个结点的判定树的深度 2 5 8)(11)为on+1 折半查找的算法复杂度为 判定树 logan+I
折半查找的性能分析 查找上例中所有元素的判定二叉树为 6 3 1 4 7 9 5 10 2 8 11 判定树 判定树上每个结点需要的 查找次数刚好为该结点所 在的层数. 查找成功时查找次数不会 超过判定树的深度 n个结点的判定树的深度 为[log2n]+1. 折半查找的算法复杂度为 [log2n]+1
9.2动态查找表 921二又排序树 什么是二叉排序树( Binary Sort tree)? 二叉排序树是空树或者是具有以下性质的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于 0它的根结点的值; d(2)若右子树非空,则右子树上所有结点的值均大于 它的根结点的值; n(3它的左、右子树也分别为二又排序树
9.2 动态查找表 9.2.1 二叉排序树 什么是二叉排序树(Binary Sort Tree) ? 二叉排序树是空树,或者是具有以下性质的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于 它的根结点的值; (2)若右子树非空,则右子树上所有结点的值均大于 它的根结点的值; (3)它的左、右子树也分别为二叉排序树