資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學再平衡演算法
再平衡演算法可以透過以下方式執行：
Day-Stout-Warren 演算法
我們可以使用 Day-Stout-Warren 演算法實現實際的再平衡方法。它的時間複雜度與節點數量線性相關。
以下是 DSW 演算法的基本偽程式碼表示。
- 分配一個名為“偽根”的節點，並將樹的實際根節點作為偽根的右子節點。
- 呼叫 tree-to-vine 函式，將樹轉換為以偽根為引數的有序連結串列。
- 呼叫 vine-to-tree 函式，將有序連結串列再次轉換為樹，以偽根和樹的大小（元素數量）作為引數。
- 應構建樹的實際根節點等於偽根的右子節點。
- 最後應釋放偽根。
“寫時複製”樹
如果我們可以承受線性化不足（即，我們寫入一個值，但當我們立即搜尋它時找不到它；它最終會被找到，但在 100ms-10s 後），則可以應用“寫時複製”樹：所有寫入操作都由一個執行緒（帶有再平衡）執行，並且我們定期將樹複製到一個只讀副本中，該副本可以由讀取執行緒在沒有任何併發控制的情況下實現，我們需要以原子方式釋出它。
併發跳錶
另一個選擇是實現一個併發跳錶：它提供對數平均情況下的搜尋/刪除/插入時間，並且更容易並行化。如果您碰巧使用 Java 實現它，則有一個標準的無鎖實現。我們可以在這裡獲得有關併發跳錶和平衡搜尋樹的更多資訊。特別是，我們可以在這裡找到對色度樹的提及，它被表示為針對併發再平衡進行了最佳化的二叉搜尋樹。
更新於：2020年1月3日
637 次瀏覽
廣告