格式不正確的二進制繩索樹

Question

我想實現一個rope tree作爲字符串的替代數據結構。

維基百科頁面不清楚拆分樹的規則，但these rules似乎起初工作。但是經過幾次分裂操作我結束了一個無效的樹：

  6 
      /\ 
     /\ 
     4 \ 
     /\  \  
    /\  \ 
    / 2  4 
    / /\ /\ 
    4  2 3 4 7 
    A  B C D E 

上的數字代表節點的重量，和子在葉的情況下的長度。在這個格式不正確的樹中，子串C永遠不可能到達。

一棵好樹的例子。按照維基百科的解釋，每個角色都可以到達。

 6 
     /\ 
    /\ 
    / 7  
    / /\ 
    4 3 \ 
/\/\ \ 
    4 2 3 4 7 
    A B C D E 

我沒有CS背景，所以我不知道樹有什麼問題。我甚至不知道如何正確地用這棵樹來表達問題。這棵樹有什麼問題（用CS術語說），我該如何解決它？

Answer 1

根違反下列不變：

每個節點的權重是所有葉子權在其左子樹的總和。

您的第二棵樹通過更改結構來修復不變量，但這不是必需的。下面是使用不同的權重具有相同的結構修正版本：

 r: 9 
     /\ 
    /\ 
    a: 4 \ 
    /\  \  
/\  \ 
/b: 2  4 
/ /\ /\ 
4  2 3 4 7 
A  B C D E 

要達到C第一個字符（一個在位7，如果我們假設爲基礎1索引），你會根據維基百科的運行Index(r, 7)文章。這裏的 「日誌」：

• 發現，7 < 9，所以返回Index(a, 7)
• 發現，7> 4，所以返回Index(b, 3)
• 發現，3> 2，所以返回Index(C, 1)
• 返回C

增補的第一個字符：

注意，維基百科的文章提出了以下不變（不同！）：

每個節點都有一個「權重」等於其字符串的長度加上所有的權重中其左子樹的總和。

該製劑不畫面立即匹配它上面：

根據上述不變的，在畫面節點B將必須具有的15