二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(23)

支的树。课本上顺序查找从an开始，当然也可以

开始。

每查分从a1

时间复杂度

从平均查找长度看顺序查找的时间复杂度是O(n)。

折半查找

思路

待查找的表必须是有序的，先从中间开始比较，比较一次至少抛弃一半元素，逐渐缩小范围，直到查找成功或失败。

算法

要熟练掌握该算法。设a[]升序有序，有以下算法：

int BinarySearch ( DataType a[], int n, DataType x )

{

low = 0; high = n-1;

while ( low <= high ) {

mid = ( low + high )/2; // 折半

if ( a[mid]==x )

return mid; // 找到

else if ( x<a[mid] ) // x位于低半区 [low..mid-1]

high = mid ? 1;

else // x位于高半区 [mid+1..high]

low = mid + 1;

}

return -1; // -1表示未找到

}

或者有递归版本：

int BinarySearch ( DataType a[], int low, int high, DataType x )

{

if ( low>high ) return -1; // 查找失败

mid = (low+high)/2; // 折半

if ( a[mid]==x )

return mid; // 找到

else if ( x<a[mid] )

return BinarySearch (a, low, mid-1, x);

else

return BinarySearch (a, mid+1, high, x);

}

另外，程序可有多种写法。

例：a[]递减有序，折半查找，请填空。

int bs ( T a[], int n, T x )

{

i = n-1; j = 0;

while (____a____) {m = ____b____;

if (____c____)

return m; // succeeded

else if (____d____)i = ____e____;

else____f____;

}

return -1; // not found

21}

分析

特点：速度很快，要求查找表是有序的，而且随机访问(以便计算折半的下标)。所以，链表不能进行折半查找(但可以采用二叉排序树等形式进行快速的查找)。

判定树

折半查找的判定树类似于完全二叉树，叶子结点所在层次之差最多为1，其深度为?logn??1。

查找过程就是走了一条从根到该结点的路径。

如：表长n=10的有序表折半查找的判定树如下。 21 答案：a: j<=i b: (i+j)/2 c: a[m]==x d: x>a[m] e: m-1 f: j=m+1

1

2 3 4

平均查找长度

结论：等概率查找成功时的平均查找长度

n?501hn?1j?1ASLbs??j2?log(n?1)?1?log(n?1)?1 nj?1n

分析方法：对等概率情况，假设查找n次，且每个查找1次，共比较关键字c次，则平均c/n次。

例：表长为n = 10，平均查找长度如下。

ASL?3?2?3?4?1?3?4?2?3?429??2.9

时间复杂度

结论：O(logn)，根据平均查找长度计算。

有时对需要反复查找的数据预先排序，再折半查找也是划算的。比如有1000个数据，顺序查找100次，平均比较约100×500=50000次；快排大约比较1.44nlogn = 1.44×1000×10 = 14400，100次折半查找比较不超过100×9×2=1800次(考虑到同一关键字的两次比较)，排序后折半查找合计比较不超过大约16200次。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-23.html