連接紅黑樹

Question

OCaml標準庫有一個美妙的Set實現，它使用非常有效的分而治之算法來計算兩組的union。我相信它需要從一個集合中取出整個子樹（不僅僅是單個元素），並將它們插入另一個集合中，必要時重新平衡。

我想知道這是否需要保存在OCaml使用的AVL樹中的高度信息，或者紅黑樹也可以這樣做。例如，是否可以更有效地連接一對紅黑樹，而不是簡單地迭代第二棵樹，將其元素附加到第一棵樹的末尾？

Answer 1

如果您對設置聯合或串聯或兩者都感興趣，或者您只對OCaml中常見的持久數據結構感興趣，或者對臨時結構感興趣，我不確定您的問題的措辭。

執行red-black trees with fingers is described by Heather D. Booth in a chapter from her thesis。用手指，一棵大小爲n的紅黑樹可以分成兩棵大小爲p和q的樹，按攤還O（lg（min（p，q）））的時間，兩棵尺寸爲p和q的紅黑樹可以是連接在同一個綁定中。此外，可以在分攤的O（1）時間內在rb樹的任一端添加或刪除元素。通過這些操作，可以實現平攤的O（p lg（q/p））時間設置聯合（對於p < q），這是信息理論上最優的。也許獲得這些界限的關鍵想法是逆轉左側和右側脊柱上的子指針。

上述界限按傳統意義攤銷。對於像OCaml這樣的函數式語言，人們可能希望在持久使用數據結構時應用邊界。當這些樹被持續使用時，我認爲布斯的描述不會達到所有這些界限。例如，插入手指可以採用ω（1）重新着色。這可以通過lazy recolorings discussed in Driscoll et al.'s "Making Data Structures Persistent"來解決。另一方面，我認爲Booth的分析可能表明即使在持續使用時級聯仍然是O（lg（max（p，q）））。我對工會的界限不那麼樂觀。

在功能設置中可以設置具有漸近最優時間範圍的運算。那些described by Hinze & Paterson達到分期付款（但持續）意義上的界限，treaps described by Blandford & Blelloch achieve the bounds in a randomized sense和那些described by Kaplan & Tarjan在最差情況下實現它們。後者也提供O（lg lg（min（p，q）））級聯，但Hinze & Paterson對這種說法持懷疑態度。這些樹不是你的問題的直接答案，這是針對紅黑樹的問題，但他們希望給出一種可能的風味，並且包括代碼和has been verified correct using Coq，它們可以提取到OCaml代碼。

您可能感興趣的另外兩個指針：Brodal et al. presented search trees with O(lg n) find, insert, and delete and O(1) concat even in a functional setting。此外，Atallah et al. claim to describe a red-black tree that has amortized O(1) concat (presumably ephemerally only)，但是Buchsbaum and Goodrich claim that there are several flaws in that structure。

一個關於紅黑樹的效用最後要注意的：在對這個問題的答案的一個一個評論，你說：

紅黑樹的唯一好處是，輔助信息（紅色或黑色）每個分支只有1位。通過增加高度，你已經失去了這個優勢，而不是僅僅使用高度平衡的樹。

還有其他的優點。例如，計算幾何中使用的一些數據結構是基於二叉搜索樹的，但樹的旋轉成本很高。 Red-black trees can be rebalanced in at most 3 rotations per insert and delete，而AVL trees can take Ω(lg n) rotations for these operations。 As Ralf Hinze noticed,Okasaki's rebalancing scheme for red-black trees（代碼可用於ML,Haskell,Java, and Ada）不提供相同的界限，並且最終可能在插入時做Ω（lg n）旋轉。 （岡崎不存在刪除）

此外，可以存儲高度平衡的搜索樹（甚至AVL樹），以便每個節點僅使用一位餘額信息。有些樹木在每個節點上只有兩個可能的平衡位置，如單側高度平衡樹木，但每個節點最多有四個可能的平衡位置的樹木可以在每個孩子中存儲一位平衡信息，如initially explained by Brown和更高版本expanded upon by Haeupler et al.

編輯：

在回答你的你的問題的最後具體的查詢，這裏是一個算法用於連接兩個紅黑樹的描述。它需要O（lg（max（| L |，| R |）））時間，這對於我上面描述的漸近最優聯合時間來說太長了。爲了比較，我期望the "join" implementation for AVL sets in OCaml's stdlib獲得O（h1-h2）性能，其中h1是較高樹的高度，儘管它實際上連接兩個AVL樹，只要給出一個適合它們的元素，而下面的算法必須找到並刪除來自其論據之一的迫擊炮元素。您可以通過僅將元素存儲在樹葉中來避免這種情況，就像在B +樹中一樣，但是這樣做會造成空間懲罰，必須在非葉節點中保留一堆指向元素的指針以指導搜索。在任何情況下，它都不會像OCaml stdlib中的AVL連接代碼那樣爲樹高度相同的樹創建連接時間，因爲您仍然必須計算每棵樹的黑色高度，如下所述。給定兩個非空紅黑樹L和R，我們將產生一個新的紅黑樹，它是L和R的連接。這將花費與O成正比的時間（lg（L（t）| L |，| R |））），其中| L |表示在L中的節點的數量。

首先，從L，c中除去最大的元素。接下來，找到L和R的黑色高度。「黑色高度」是指從根到葉子的任何路徑上的黑色節點數。通過紅黑樹不變量，這在任何給定樹的所有路徑上都是不變的。調用L's黑色高度p和R的黑色高度q，並假設爲 w.l.g.g q。

從R的根部，跟隨左邊的孩子，直到到達高度爲p的黑色節點R'。用根元素c製作一棵新的紅色樹C，左邊的小孩L和右邊的小孩R'。由於L本身就是一棵紅黑樹，所以它的根部是黑色的，並且顏色不變量在C處或以下不違​​反。此外，C 的黑色高度是p。

但是，我們不能簡單地將C重新拼接回R而不是R'。首先，如果p = q，R'是R，但C有一個紅色根。在這種情況下，只需重新着色C黑色的根。這是你的 新的連接樹。

其次，如果R'不是根，它可能有一個紅色的父項。紅色的父母不允許有紅孩子，所以我們必須重新平衡。這裏我們只是將岡崎的再平衡 方案一路向上R'（現在替換爲C）和R的根之間的脊椎。

有兩種可能的情況。如果C沒有祖父母，顏色C的父母黑色。樹現在是有效的。

如果C有祖父母，它必須是黑色和黑色高度p + 1，因爲C的父母是紅色的。用一棵新的紅色樹替代C的祖父母，它的根源是C父母的根，其左邊的孩子是C，重新着黑色，右邊的孩子是一棵黑色的樹，由C的兄弟姐妹C的祖父母的根，和C的叔叔，在 那個順序。這並不會增加C的祖父母的黑色高度，但它會將其顏色更改爲紅色，這可能會使其成爲紅色父母的紅色孩子的根或紅色，因此我們必須重新平衡，等等。樹

• 發現兩棵樹的黑色高度：O（LG | L |）+ O（LG | R |）
• [R跟蹤到正確的位置：O（LG | R | - LG | L |）
• 輪作一路備份到根：O（LG | R | - LG | L |）

這些都不比O（LG更大| R | + LG | （lg（min（| L |，| R |）））），首先反轉脊柱指針。然後，您不需要較大樹的黑色高度，只需計算黑色脊椎節點，直到一棵樹用完脊椎。然後，使用原始（不是岡崎的）重新平衡方案，以確保您只重新平衡O（1）個節點。最後，在稍後有必要的時候標記不需要重新平衡進行懶惰重新着色的脊柱的其餘部分。

Answer 2

當你將樹與低重疊結合時，你可能會贏得一些東西，但總的來說，你將不得不重新節點。平衡你有更糟糕的情況，因爲有可能只有一個節點後觸發旋轉的規則。

Answer 3

因爲你似乎在談論連擊+添加到年底，好像你有以下問題：

Given two red-black trees T1 and T2, such that keys of T1 <= keys of T2, 
find union of the two. 

這就是所謂的樹木，在這種情況下，連接操作，有可能在O（log n）時間做樹的加入，請查看：http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf

也檢出：http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm，問題14.2。

Answer 4

在連接時可以比O（log^2（n））做得更好，而不是在每個節點中增加具有高度信息的樹。 您可以在2 * [log（n1）+ log（n2）]中連接，其中n1和n2表示您要連接的樹中的節點數。在計算O（log（n））中的高度後，沿着樹向下找到正確的連接點時，請在每個節點中使用Balance信息！