string - 畸形二叉树

Question

我正在尝试实现一个绳索树作为字符串的替代数据结构。

维基百科页面不清楚拆分树的规则，但这些规则起初似乎有效。然而，经过几次拆分操作，我最终得到了一个无效的树：

          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（如果我们假设基于 1 的索引，则位于位置 7），您将Index(r, 7)根据 Wikipedia 文章运行。这是“日志”：

• 找出 7 < 9，所以返回Index(a, 7)
• 找出 7 > 4，所以返回Index(b, 3)
• 找出 3 > 2，所以返回Index(C, 1)
• 返回的第一个字符C

附录：

请注意，维基百科文章提出了以下（不同的！）不变量：

每个节点的“权重”等于其字符串的长度加上其左子树中所有权重的总和。

这个公式与它上面的图片不匹配：

根据上述不变量，B图片中的节点的权重必须为 15。