折半查找判定樹及平均查找長度

從折半查找的過程看，以有序表的中間記錄作為比較對象，并以中間記錄將表分割為兩個子表，對子表繼續上述操作。所以，對表中每個記錄的查找過程，可用二叉樹來描述，二叉樹中的每個結點對應有序表中的一個記錄，結點中的值為該記錄在表中的位置。通常稱這個描述折半查找過程的二叉樹為折半查找判定樹。

長度為n的折半查找判定樹的構造方法為：

⑴ 當n=0時，折半查找判定樹為空；

⑵ 當n＞0時，折半查找判定樹的根結點是有序表中序號為mid=(n+1)/2的記錄，根結點的左子樹是與有序表r[1] ~ r[mid-1]相對應的折半查找判定樹，根結點的右子樹是與r[mid+1] ~ r[n]相對應的折半查找判定樹。

例如，長度為10的折半查找判定樹的具體生成過程為：

⑴ 在長度為10的有序表中進行折半查找，不論查找哪個記錄，都必須先和中間記錄進行比較，而中間記錄的序號為(1+10)/2=5（注意是整除即向下取整），即判定樹的根結點是5，如圖7-2(a)所示；

⑵ 考慮判定樹的左子樹，即將查找區間調整到左半區，此時的查找區間是

[1，4]，也就是說，左分支上為根結點的值減1，代表查找區間的高端high，此時，根結點的左孩子是(1+4)/2=2，如圖7-2(b)所示；

⑶ 考慮判定樹的右子樹，即將查找區間調整到右半區，此時的查找區間是

[6，10]，也就是說，右分支上為根結點的值加1，代表查找區間的低端low，此時，根結點的右孩子是(6+10)/2=8，如圖7-2(c)所示；

⑷ 重復⑵⑶步，依次確定每個結點的左右孩子，如圖7-2(d)所示。

對于折半查找判定樹，需要補充以下兩點：?
⑴ 折半查找判定樹是一棵二叉排序樹，即每個結點的值均大于其左子樹上所有結點的值，小于其右子樹上所有結點的值；?
⑵ 折半查找判定樹中的結點都是查找成功的情況，將每個結點的空指針指向一個實際上并不存在的結點——稱為外結點，所有外結點即是查找不成功的情況，如圖7-2(e)所示。如果有序表的長度為n，則外結點一定有n+1個。 在折半查找判定樹中，某結點所在的層數即是查找該結點的比較次數，整個判定樹代表的有序表的平均查找長度即為查找每個結點的比較次數之和除以有序表的長度。例如，長度為10的有序表的平均查找長度為：?
ASL=(1×1+2×2+3×4+4×3)/10=29/10?
在折半查找判定樹中，查找不成功時的比較次數即是查找相應外結點時與內結點的比較次數。整個判定樹代表的有序表在查找失敗時的平均查找長度即為查找每個外結點的比較次數之和除以外結點的個數。例如，長度為10的有序表在查找失敗時的平均查找長度為：?
ASL=(3×5+4×6)/11=39/11

總結

以上是生活随笔為你收集整理的折半查找判定树及平均查找长度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。