紅黑樹：在log（n）時間中拆分/連接時間

但是，我仍然不相信拆分的運行時間是真的。

這個想法是分裂使用最壞情況下的log（n）級聯。這些concat的執行速度很快，因爲我們可以通過從最後的連接中記住p來找到節點p。

問題是，串聯啓動修復（平衡）算法，據我所知，它採用O（log n）（請參見連接的僞代碼中的步驟5）。這給了我一個log（n）* log（n）的運行時間，因爲拆分會導致最壞情況的log（n）級聯。

Ron Wein，在他的論證中沒有將修復算法計算在內。我在分析中錯過了什麼，或算法錯誤？

可能是暗示的修正不是每個人真的是昂貴 – 2015-03-13 10:49:25

沒想好分期付款的說法，不過是這樣的話，最終的結果將至少處於攤銷時間，而事實並非如此。所以不這麼認爲。但是，謝謝你的回答 – 2015-03-13 10:56:10

這不是我的意思。如果您可以在拆分操作（例如，通過分期付款）內限制fixup *的總工作量，則會得到適當的最差情況下的拆分限制。 – 2015-03-13 10:57:42

未來。如果有任何問題再次出現：與Ron Wein相比，Tarjan在算法上存在一些重要差異。我仍然無法看到Wein在他的算法中是正確的，但是Tarjan是。所以我建議你改用他。

重要的一點是，平衡算法的成本爲O（log（d）），其中d是您開始進行平鋪的深度。然後，Tarjan的算法通過在分割鍵處開始並在根路徑上移動而有所不同。通過這樣做，你會看到你連接的子樹有相同的深度。因此「d」總是很小。因此它可以做得更快。

第二件事是，Tarjan建議增加所有節點，使他們知道他們的等級（它的子樹的黑深度+它自己）。通過這樣做，我們能夠知道哪一棵樹在O（1）時間內是最大的。也有可能找到O（1）時間在那裏的高度差異。

我建議大家讀Tarjans紙代替的Wein的

2015-04-10 09:04:11

請問，你可以發佈一個鏈接到Tarjan算法？我有一些問題要找到它。 – 2018-01-28 20:16:22

回答