是否只有一种方法可以在具有给定数字序列的纸张上创建回铃音？

Question

假设我有不同的随机数序列<1, 30>。即 20, 23, 27, 15, 14, 13, 2。在纸上绘制红黑树只有一种方法吗？ （即考试期间）。我的意思是我选择的旋转与某些开发的算法给我的旋转不同？

我前几天遇到的一些案例： 第一

我想添加“2”。 第二

那么另一个问题是：这两棵树加“2”后可以接受吗？

我尝试了所有来源：c

Answer 1

我们可以在 2 作为叶子添加之后查看以下子树，无需应用任何重新着色或旋转 - 我用括号标记红色节点：

        (14)
        /  \ 
      12    15
     /
  (10)
  /
(2)

首先请注意，新叶子总是呈红色，因为这样我们就可以保持“黑色属性”。

引入的违规涉及直接连接的两个红色节点（10 和 2）。这个问题需要解决。

维基百科 - 红黑树中描述的算法将执行节点 10 和 12 的旋转，然后应用重新着色：这是其过程中的“插入情况 I6”。

您应用了不同的算法，显然通过对节点 10 和 12 重新着色来解决红-红冲突，因此现在红-红冲突发生在节点 14 和 12 处：

        (14)
        /  \ 
     (12)   15
     /
   10
  /
(2)

然后执行节点 12 和 14 的旋转，对节点 14 和 15 重新着色：

     (12)
     /  \
   10    14
  /        \
(2)        (15)

这是一个有效的红黑树，但是：

• 需要更多节点重新着色（4 个而不是 2 个），并且

• 如果您将此作为考试问题的答案，您可能会得到不好的分数，因为很明显您没有应用标准算法。为了算作有效答案，考试审核者必须知道您应用了哪种替代算法，以及将算法的特定部分应用于这种情况的一般前提条件是什么。然后，您最好通过完整规范来扩展您的考试答案，说明您将应用于您可能遇到的每种可能的配置的算法，或者至少提供该算法的信誉良好的来源的参考，以便考试审阅者可以验证其正确性（如果他们对使用替代算法的学生开放）。