邊緣標籤的實際實現細節/基樹中的分割

Question

這是關於在實踐中通常做什麼的問題。

假設我們有一個基數樹與一個條目（不管出於什麼原因，認爲這是對示範單個條目）：

"tests are really hard, no one likes taking tests, they're the worst" 

然後，我們希望把在第二項

"team" 

我們想從根邊緣結束了

"te" 

和兩個邊的從一與

"sts are really hard, no one likes taking tests, they're the worst" 

和一個與

"am" 

天真，我們可以創建新的字符串（字符數組，等等）爲 「TE」 和 「STS是真的...」。即使我們的新詞「團隊」很短，這也需要很多操作。

另外，我們也有「德」和「STS是真的...」標籤可以包含對同一原始字符串的引用，以及開始/結束值，即：

[0, 2] for "te" 

和

[2, <whatever it is>] for "sts are really..." 

這樣，我們避免任何複製，和「團隊」插入時間僅依賴於「國家隊」的長度，而不是其他的字符串，即「測試是真的長... 「 在這種情況下。

因此，O(k)中的k是指插入的字符串的長度，還是迄今爲止最長的字符串。

很明顯，後者的實現比較困難，實際上可能會使用更多的內存（因爲存儲了端點），但看起來理論上最差的情況是時間得到了改進。

我想知道是否有人知道在實踐中通常會做什麼？

感謝

編輯：我想後者實現一個問題會與缺失出現。如果你後來插入了「心靈感應」，但後來刪除了「測試真的很難......」，那麼「te」邊緣仍然存在，並且仍然比字符串更長。

Answer 1

刪除密鑰的算法是找到其葉節點，將其刪除，並且，如果該節點的父節點只有一個其他子節點，則拼接這兩個節點。

假設邊緣標籤以成對的索引形式存儲到整個鍵中，則拼接可以通過調整剩餘子的較低索引來完成。要「垃圾收集」已刪除密鑰的所有其他實例，可以掃描根部，重寫包含已刪除密鑰的邊緣標籤以引用兄弟。在最壞的情況下，我們必須一直掃描回到根目錄，而不會增加漸近運行時間，但對於隨機操作，重寫的預期次數是恆定的。目前還不清楚這種開銷是否值得保存的副本。