97 年 097年公務人員高等考試三級考試暨普通考試・資料結構 申論 2有一個二元搜尋樹（Binary Search Tree）T 如下：㈠若欲搜尋的鍵值（Key）平均分布在1 到100 之間，請算出該值於搜尋樹中平均要比較幾次。（5 分）㈡設鍵值K＝2 時，其機率為0.5，K＝5 時其機率為0.3，K＝9 時其機率為0.103，其餘97 個數機率均為0.001，請算出該值於搜尋樹中要比較幾次。（10 分）㈢設各鍵值的機率如上述第㈡小題，是否能將此搜尋樹重新安排以獲得較佳的平均比較次數？請說明原因或理由。（10 分） 看答案與解析