RB-Tree：搜索執行時間

我必須使用RB-trees爲「算法和數據結構」類項目實現一個區間樹，因此它被要求繪製插入和搜索T(n)。我知道這個函數必須以對數曲線爲上界，事實上這個曲線顯示了這一點，但我仍然對「奇怪的函數趨勢」有所懷疑。我已經寫了插入隨機的間隔和它搜索到樹在爲0 < N < 100000每個值相同步驟循環，這就是結果：RB-Tree：搜索執行時間

enter image description here

是不是期待類似的趨勢？

來源

2014-02-05 sscnapoli1926

我忘了說這個圖來自一個測試平臺版本，其中時間計算爲每個搜索函數迭代遞增一個計數器;這是因爲運行時環境應該錯誤地表示實際執行時間，所以我確信，如果存在問題，那麼進入數據結構/測試臺 – sscnapoli1926

檢查樹是否具有n = 2^k- 1，因爲在那種情況下樹應該是完全平衡的，因此對於隨機搜索將具有最小的搜索時間。當你搜索T（n）應該是平均的大量搜索。 –

是的，我確定我的樹是平衡的，因爲插入的T（n）非常接近對數行爲。此外，我試圖檢查每個插入/搜索週期rb樹屬性高度<= 2 *黑色高度是尊重和測試不失敗。我還嘗試插入按順序的區間值並搜索一個我確定無法存在的區間（例如，Integer.MAX_VALUE，Integer.MAX_VALUE），以強制算法訪問每個級別直到離開，但結果仍然相同 – sscnapoli1926

這是完全合理的期望。

插入到紅/黑樹中有兩個組件：基線Θ（log n）組件，用於下降到葉片以插入元素，然後進行一些額外的「修復」工作以保持紅色/黑色樹不變量。事實證明，這第二個組件是攤銷O（1），這意味着平均只需要一個恆定的工作量的修復，但時不時的修復工作增加。

如果你已經看到紅/黑樹和2-3-4樹之間的聯繫，這可能會更容易理解。在2-3-4樹中的插入通常只需向葉節點添加一個密鑰即可停止。無論何時，你必須拆分一個4節點並將一個密鑰傳播到樹中較高的節點，這通常會立即停止。然而，每隔一段時間，就必須分割一片葉子，然後將一個節點分割成上面的一個節點，然後向上傳播一個密鑰兩層。在進行像這樣的插入時，您會得到的典型模式是，您將得到一系列快速操作，然後是一個較慢的操作，然後是一些更快的操作，然後是一個較慢的操作，然後是一些更快的操作，那麼比其他人慢得多，等等。你好像在你的情節中得到了這個，所以我不認爲這是什麼可擔心的。

希望這會有所幫助！

來源

2014-05-22 15:52:26 templatetypedef

我已經讀了這個太晚了，但它是非常完整的....進一步，我已經實現了最大的投票，所以圖形應該是正確的....所以，投票並感謝相同！ – sscnapoli1926

RB-Tree：搜索執行時間

回答

相關問題