我需要一個有效的資料結構來存盤，我需要插入并可能訂購。但是，不需要在每次插入后保持順序，我認為排序比插入要少得多。
我正在考慮紅黑樹，但我不確定在 RB 樹中插入節點的速度有多快（例如，與將其插入串列相比）；然而，在 RB 樹中排序更省時。
哪種資料結構最有效？
謝謝你的時間
uj5u.com熱心網友回復：
我不確定在 RB 樹中插入節點的速度有多快（例如，與將其插入到串列中相比）
插入的平均時間復雜度為：
- RB 樹（也是最壞的情況）：O(logn)
- 排序串列：O(n)
- 未排序串列：O(1)
按排序順序遍歷所有值：
- RB樹：O(n)
- 排序串列：O(n)
- 未排序串列：O(nlogn)
因此，對于漸近增加的資料大小，插入最終將在 RB 上比在排序串列上運行得更快，盡管對于小尺寸的串列可以更快（因為它具有較少的恒定開銷）。實際的臨界點將取決于實作方面，包括編程語言和要比較的值的結構。但是插入到未排序的串列中當然會勝過兩者。
根據未排序串列的需要對串列進行排序是有成本的，但與 O(n) 相比，它“僅”是 O(nlogn)。因此，如果排序不必那么頻繁地發生，它可能是一個可行的選擇。同樣，臨界點——即幾個插入和排序的總運行時間比其他選項快——取決于實作方面。
哪種資料結構最有效？
在實踐中，我發現 B 樹是快速插入的不錯選擇。就像 RB 樹一樣，它們的插入時間為 O(logn)，但是可以調整具有不同塊大小的資料結構，試圖找出最適合您的實際情況的資料結構。這對于 RB 樹是不可能的。此外，B 樹的排序串列位于已排序塊的鏈表中，因此按排序順序進行迭代是微不足道的。沒有什么能比得上它的速度了。
另一個有趣的選擇是跳過串列。它有點像 B 樹，但它的操作更容易實作。由于沒有塊和更多的指標，它使用了更多的記憶體（相同的復雜性）。
哪一個效果最好取決于實作/平臺因素。最后，您將希望實作一些替代方案并將它們與基準測驗進行比較。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/489004.html