二叉排序樹的不成功的平均查詢長度怎麼求

1樓：匿名使用者

找到所有的外結點，也就是查詢失敗的點，然後計算asl

就你的bst，結果如下：

15的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、30、15一共3次。

48的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、30、15、48一共4次。

56的右子樹為空，也就是右子樹是外結點，失敗時需要比較62、30、56一共3次。

74的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、74一共2次。

因此外結點總數為2 *3 + 1 = 7 （其實這個數量一定是關鍵字個數加1）

所以asl = 2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) /7 = 21 / 7 = 3

2樓：舞陽人樂園

需要有一定的公司才能夠求出來的，不過這個公司相對來說比較簡單的。

n個結點的二叉排序樹在最壞的情況下的平均查詢長度為______

3樓：仁昌居士

n個結點的二抄叉排序樹在最壞的情況下的平均查詢長度為（n+1）/2。

二叉排序樹每個結點的c（i）為該結點的層次數。最壞情況下，當先後插入的關鍵字有序時，構成的二叉排序樹蛻變為單支樹，樹的深度為其平均查詢長度（n+1）/2（和順序查詢相同），最好的情況是二叉排序樹的形態和折半查詢的判定樹相同，其平均查詢長度和log 2 （n）成正比。

4樓：油條大巴

當n=1, 只有乙個根結點，成功找到根結點只需要1次，平均查詢長度為：

asl = n+1)/2 = 1+1)/2 = 1

當n=2, 有兩個結點，假設是往右傾斜，成功找到結點1需要1次，成功找到結點2需要2次，平均查詢長度為： (1+2)/2 = 3/2

用公式計算 asl= (2+1)/2 = 3/21\

2當n=3, 有三個結點，最壞的情況是整個二叉排序樹往右傾斜(或者左傾斜),成功找到結點1需要1次，成功找到結點2需要2次，成功找到結點3需要3次，平均查詢長度為： (1+2+3)/3 = 6/3 = 2

用公式計算 asl= (3+1)/2 = 4/2 = 21\

2\3如果結點的總數量是n, 最壞的情況是整個二叉排序樹往右傾斜(或者左傾斜),成功找到結點1需要1次，成功找到結點2需要2次，成功找到結點3需要3次，..

成功找到結點n需要n次，平均查詢長度為： (1+2+3+..n) /n

上述 1+2+3+..n 就是等差數列求和，數學公式是 (n+1)*n / 2

所以， (1+2+3+..n) /n = n+1)*n / 2 / n = n+1)/2

也就是， n個結點的二叉排序樹在最壞的情況下的平均查詢長度為 (n+1)/2

二叉樹示意圖，整個二叉排序樹往右傾斜，成了單向鍊錶：1\

n-2-1

給定二叉排序樹的資料求平均查詢長度

5樓：匿名使用者

我感覺，二叉排序樹的平均查詢長度，與構造的，二叉排序樹的形態有關，所以這道題的答案應該不是唯一的吧。

為什麼採用二叉排序樹查詢的平均查詢長度為o(log_{2}n)