優化二叉樹插入到O（1）與哈希映射爲寫入重樹

首先，我想我已經錯過了一些重要的事情時想到這一點，但我仍然想要張貼它看看我是否真的沒有'不會錯過任何東西，對它...優化二叉樹插入到O（1）與哈希映射爲寫入重樹

我有一個漂亮的重寫二叉樹（大約50/50之間的寫入和讀取），並在回家的路上我正在考慮如何優化這種方法，特別是寫得更快 - 這是我想出的。

考慮到將x添加到樹T的操作add（T，x）首先包含find（T，x）以查看x是否已經存在，並且在這種情況下它不會返回父項，所以我們可以添加它而不是父母的空葉子之一。

如果我們添加一個哈希表作爲中間緩存添加操作，所以當我們調用add（T，x）時，真正發生的是x被哈希並插入到哈希映射M中。就是這樣。當我們在其他地方要求查找（T，x）時，現在當我們搜索將要到葉節點的樹時，優化發生，因爲x尚未插入樹中（它只存在於散列映射M中），我們散列x並將它與M中的鍵進行比較，以查看它是否應該在樹中。如果它在M中找到，那麼我們將它添加到樹中並從M中刪除它。

這將消除add（T，x）上的find（T，x）操作並將其減少爲add（M，x）這是O（1）。然後（ab）-使用我們第一次查找節點時執行的find（T，x）操作來插入它。

來源

2009-12-07 thr

這將需要你維護2個結構，並應用一個足夠的哈希alogrith來避免大型結構中的碰撞。你有沒有看過這個額外的開銷？ – 2009-12-07 20:00:08

@astander：不，我沒有，這就是爲什麼我問這裏是否有明顯的缺陷，我可以在我選擇的平臺（.NET）中使用內置的哈希表，這應該是足夠好的。碰撞檢測並不困難（如果我嘗試插入一個已經存在於M中的散列值，比較兩個值，如果它們不相等，則在第二個碰撞的元素上執行正常的二進制插入） – thr 2009-12-07 20:04:03

另外，您可能想要檢查N個添加和N個查找的複雜性（假設爲50/50），而不是單個添加或查找。我認爲你拖延了工作而不是優化工作。 – 2009-12-07 20:06:32

爲什麼不使用散列表的一切，並完全省略二叉樹？

這一切都取決於你爲什麼首先使用二叉樹。如果您選擇了二叉樹來增強共享，那麼您將失去散列表緩存，因爲散列表不會共享。

緩存不會比較兩個映射更容易。

編輯：

如果採取樹木的特異性的優勢業務是罕見的（你提到利用的事實，RB樹進行排序），如果，在另一方面，你經常擡頭一最近添加的密鑰，或者替換最近添加的密鑰的值，使用其他結構實現的小型緩存可能是有意義的。您也可以考慮使用散列表表示法，偶爾轉換爲樹。

這個緩存層的額外複雜性可能意味着你在實踐中沒有獲得任何時間，或者不足以償還像這樣的特定數據結構的技術債務。

來源

2009-12-07 20:00:05

那麼我使用二叉樹，因爲它是排序的。樹（在這種情況下是RB樹）被用作頻繁更新的排序索引。 – thr 2009-12-07 20:02:10

如果你需要的是有一個具有O（1）插入，並大約爲O（n）攤銷有序迭代的結構，我有同樣的問題：

Key-ordered dict in Python

答案（保持哈希和一個部分排序的列表，並使用像TimSort這樣的部分排序結構友好的排序）在我的情況下在實踐中效果很好。

來源

2009-12-07 20:15:43 LeMiz

優化二叉樹插入到O（1）與哈希映射爲寫入重樹

回答

相關問題