二叉搜索樹分析

Question

在二叉搜索樹中，大多數操作的平均計算複雜度爲O（NlogN）。以下是來自Algo書中的文本片段：

內部路徑長度的平均值是D（n）= O（n log n）。因此， 的任何節點的預期深度是O（log n）。例如，隨機生成的500個節點的樹具有預期深度爲9.98的節點。

立即說這個結果意味着所討論的所有操作的平均運行時間，即插入， 在二叉搜索樹上查找min，find max，delete是O（log n），但是這個 並不完全正確。原因在於，由於 刪除，所有二叉搜索樹可能均等於 並不清楚。特別是，上述刪除算法有利於 使得左側子樹比右側更深，因爲我們總是用 替換具有來自右側子樹的節點的刪除節點。這種策略的確切效果仍然不得而知，但它似乎只是一個理論上的新穎性 。已經示出，如果我們交替插入 和缺失O（N 2）（即，n正方形的THETA）倍，則樹 將具有THETA平方根N.

的預期深度的四分之一之後百萬個隨機插入/刪除對，該樹有點右 - 重看起來明顯不平衡（平均深度= 12.51）。

我上面的文字片斷的問題是：

1. 什麼是筆者的意思是「因爲缺失的，目前尚不清楚，所有的二叉搜索樹都同樣可能」？
2. 作者如何達到500節點樹的預期深度9.98，因爲日誌500不是9.98？
3. 在最後一段中，他是如何獲得12.51的平均深度的？

謝謝！

Answer 1

1）它考慮由（有點均勻的）隨機插入和刪除序列生成的二叉樹。當只進行插入時，樹的所有可能的形狀（高達symetry !!）的大小都是相當可能的 - 你可以嘗試構建一個樹，其中所有可能的排列爲（1,2,3）或（1,2 ，3,4）。

在這裏描述的算法中，當刪除具有兩個子樹的節點時，它被右子樹取代，並且我猜左子樹在最下面。這不僅使得一些（不平衡的）形狀比沒有刪除的可能性更大，而且使得它們可能比左側樹枝上的樹更深於右側樹上的樹（看看當你移除或接近幾個節點時會發生什麼採用這種策略的平衡樹的根）

2）改爲考慮大小511。如果樹完全平衡，它將具有深度9（log（n + 1））這是具有許多元素的最小深度。對於隨機形狀，這是最小值，而不是平均值，平均值必須更大：有深度爲511的形狀（注意，雖然深度必須大於log2（N），但仍可能爲O（logN）） 。我不知道作者是如何得到這個數字的。也許聰明的數學，也許只是運行一個大樣本。

4）我相信在這種情況下運行一個樣本：樹有權重看起來。但很明顯，刪除將平均傾向於使樹木不那麼平衡