樹的平均查詢長度怎麼算?怎麼代的公式？

計算每個元素的訪問長度並相加最終除以總元素個數就是查詢成功時的平均訪問長度了。

第一行的訪問長度是1，有一個元素，即1x1

第二行的訪問長度是2，有兩個元素，即2x2

第三行的訪問長度是3，有四個元素，即3x4

第四行的訪問長度是4，有六個元素，即4x6

以上相加除以元素個數總和（13）即3。154。

實際上就是在化簡公式後再進行套用，化簡是基於隱含的假設條件（每個元素被訪問的機率相等）：

查詢失敗的情況同理：

這邊兩個特殊失敗路徑長度是3：

小於73→小於25→小於1

大於73→小於108→小於74

其他長度都是4，共有14種路徑（每個葉子節點各兩種+特殊情況兩種），最終平均查詢長度是3。857。

這裡的查詢失敗時的平均查詢長度3。857我覺得並不合理，上演算法導論的時候一般老師都會強調：平均時間複雜度必須要考慮分佈，那麼這邊查詢失敗的情形之間是等機率的麼？

如果我們要查詢的數字是在正整數集合上等機率平均分佈的，那麼失敗的平均查詢長度應該無限接近於4。

相反如果我們要查詢的數字是在負整數集合上等機率平均分佈的，那麼失敗的平均查詢長度應該無限接近於3