我瞭解如何使用樹來修改持久數據結構（創建一個新節點並替換它的所有祖先）。持久數據結構的高效批量修改
但是如果我有一棵有10,000個節點的樹並且我需要修改其中的1000個樹呢？我不想通過創建1000個新的根，我只需要一次修改所有結果的新根。
例如： 讓我們以持久二叉樹爲例。在單個更新節點的情況下，它執行搜索直到找到節點，用修改和舊的子節點創建一個新的節點，並創建新的祖先到根節點。
在批量更新的情況下，我們可以這樣做： 而不是隻更新一個節點，而是一次更新1000個節點。
在根節點上，當前列表是完整列表。然後，您將該列表拆分爲與左側節點匹配的列表和與右側匹配的列表。如果沒有一個孩子與其中一個孩子相匹配，請不要下降。然後，您下降到左側節點（假設有匹配），將其搜索列表在其子節點之間分開，然後繼續。當你有一個節點和一個匹配時，你可以更新它並返回，根據需要替換和更新祖先和其他分支。
這將導致只有一個新的根，即使它修改了任意數量的節點。
這些「批量修改」操作有時稱爲批量更新。當然，細節取決於你正在使用什麼樣的數據結構以及你想要執行什麼樣的修改。
典型的操作類型可能包括「刪除所有滿足某些條件的值」或「增加與此列表中所有鍵相關聯的值」。通常情況下，這些操作可以在整個結構上進行一次，耗時O（n）。
您似乎對創建「1000根新根」所涉及的內存分配感到擔憂。一次執行一個操作的典型分配是O（k log n），其中k是被修改的節點的數量。在整個結構上執行單步行的典型分配將是O（n）。哪個更好取決於k和n。
在某些情況下，您可以通過特別注意發生更改時減少分配量 - 代價是更復雜的代碼。例如，如果您有一個返回樹的遞歸算法，則可以修改算法以返回樹布爾值，指示是否有任何更改。然後，該算法可以在分配新節點之前檢查那些布爾值，以查看舊節點是否可以安全地重新使用。但是，除非有證據表明額外內存分配實際上是一個問題，否則人們通常不會爲此額外支票而煩惱。
Clojure（和ClojureScript's）transients中提供了您正在尋找的特定實現。簡而言之，給定一個完全不可變的，持久的數據結構，它的一個瞬態版本將使用破壞性（分配高效）的變異進行變更，當你變成一個合適的持久數據結構完成您的性能敏感操作。只有在過渡到持久數據結構時纔會創建新的根（例如），從而將伴隨成本分攤到結構上執行的邏輯運算次數，而這些邏輯運算處於暫時形式。
感謝您的好消息。我沒有考慮走過整個結構。我在問題中增加了一個例子。在我看來，這個例子的內存佔用量要比1乘1的方法少得多。通過在每個分支處分割列表，它可能類似於搜索的O（k log n），但每個更新的節點（包括祖先節點）只更新一次。 1乘1的情況：（k log n）搜索每個節點，然後是另一個（k * avg深度）用於更新祖先（一些重複）。在問題的例子中，這不會顯着減少嗎？ – mentics 2011-06-18 05:20:28
當然，你的新二叉樹的例子基本上就是我所說的走遍整個結構，因爲一般來說它會在樹的兩邊進行遞歸調用。當然，在特殊情況下，您可能會提前停止並避免遍歷樹的某些部分。在其他情況下，您可能仍然需要遍歷樹的一部分，才能發現樹的該部分實際上沒有發生變化。這是當我提到的額外的布爾返回值可能會有用，如果你想避免不必要的分配。 – 2011-06-19 18:20:49
如果有更新的節點與該分支匹配，則只能沿分支走。它以與1乘1的情況完全相同的方式進行搜索，但它同時進行全部k次搜索。所以你永遠不需要返回一個關於它是否更新的布爾值，因爲除非它被更新，否則你不會沿着那個分支走下去。 – mentics 2011-06-20 09:45:14