同一个数据集是否可以存在多个有效的左倾红黑树？

Question

我有这 2-3 棵树：

我的老师让我在插入值 8 后创建一个左倾的红黑树。

我的回答是：

但老师给出的预期答案是：

他们将其标记为错误。虽然它显然是一棵不同的树，但在我看来这棵树仍然有效。

我想知道在给定相同的 2-3 树的情况下，是否可能有多个 valid 左倾红黑树。只要满足LLRB的条件，这能有多种表示吗？

Answer 1

你回答的树打破了中序遍历应该产生排序序列的规则。情况并非如此，因为在 8 点之前访问了 11 点。

这是获得所需解决方案的程序：

输入的2-3树为：

         ___(12 16)___
        /      |      \
     (2 11) (13 15) (20 22)

插入8导致叶子节点溢出：

          ___(12 16)___
         /      |      \
    (2 8 11) (13 15) (20 22)

...所以它需要拆分，将中间值向上移动：

       __(8 12 16)______
      /    |   \        \
    (2)  (11) (13 15) (20 22)

...现在顶层节点溢出了，所以需要分裂，创建一个新的根节点：

           __(12)__
          /        \        
       (8)        _(16)_
      /   \      /      \
    (2)  (11) (13 15) (20 22)

最后需要将这棵2-3树映射到左倾的红黑树。在此转换中，3 节点获得红色边缘：

         __12__
        /      \        
       8       16
      / \     /  \
     2  11  15    22
           /R    /R
          13    20

多个有效的 LLRB 树？

是的，同一个数据集可以有多个有效的 LLRB 树，但它们同样会映射到同一个数据集的不同 2-3 棵树。

假设你被要求在given 2-3树中插入值8，并且插入一个值遵循严格的算法，结果是唯一的2-3树，所以对应的LLRB树也是唯一定义。

您遇到的挑战只有一个正确的解决方案。