我們常常希望, 建好一個 BST 後,
不只可以問當中某個資料在哪
像Search(data=70) 來找資料 70
也希望可以問: 第 3 小 (rank=3) 的資料到底為何?
也就是, Search(rank=3) 希望得到資料 40.
這就叫 Search a BST by Rank.
本來, 一個 BST (with n data), 若用 inorder traversal,
就可得到資料的排序, 若放在一維陣列 A[1...n]中,
則, 就知 Search(rank=i) 的資料為 A[i], 時間 O(1);
但 inorder traversal 需要 O(n) (data 若經過修改, 加資料或刪資料,
則要重新做 inorder traversal).
為了避免 inorder traversal, 加快 Search(rank=?) 速度,
標準做法是: 把每一個 data 都多一欄位, 叫 left_size.
若一個 data 在 BST 中, 其左子樹有 k 個資料, 則此 data 的 left_size 為 k+1.
這 left_size 的欄位, 就可幫助我們做 Search(rank=i).
這道理是利用一個簡單的性質:
某一節點 x 的 left_size 若跟 rank 相等, 譬如都是 i,
則 x 的資料就是第 i 小的資料.
因此 Search(rank) 的基本方法是:
For the node X in BST,
if X.left_size = rank, then X.data is answer.
if X.left_size < rank,
then the answer is the (rank)th data in the left subtree of X.
if X.left_size > rank,
then the answer is the (rank-left_size)th data in the right subtree of X.
當我們設計程式的時候
你可能會用到迴圈
而執行回圈的次數就會影響到你程式的速度
而BINARY SEARCH 是一種搜尋程式
當你的資料有排序有次序的時候
譬如 1 2 56 78 211 222 789 958 1002
這時候我想查一個儲存位址叫做789的檔案
1我可以先排列這些檔案(依照他的位址大小)
2再用BINARY SERCH
3我們知道有九個檔案 所以找中間那個(就是第五個)
4結果是222所以我們知道789會在222後面
再從222開始找中間那個 結果是958
5 958比789大所以我們之道789在958與222的中間也就是第七個
想想看如果從第一個開始一個一個找要多少次??要七次才會找到
可是用二元搜尋,就只須要三次就找到了
