2

我是数据结构的新手。我已经完成了红黑树插入算法的实现。我无法理解，算法如何处理排序值的插入。

让我用数据集 [10, 5, 2] 来说明。

因此，Initial 10 将被插入，并将成为树的根，其颜色将为黑色。10在此处输入图像描述

接下来，我们将在根 10 下添加 5。5 的颜色将为红色（截至目前，它不违反任何属性）。 在此处输入图像描述

现在，我们将添加添加 2。添加后，树将如下所示：- 在此处输入图像描述 添加 2（其颜色为红色）将违反不允许红色父级下的红色子级的规则。红黑树中有 3 种情况：- 所有三种情况都假设 parentOf(newlyInsertedNode) 有兄弟姐妹。但在我的情况下， parentOf(2) = 5 没有兄弟姐妹。那么，红黑树算法将如何处理这种情况。

4

1 回答 1

1

红黑树的细节可能会有所不同，具体取决于文章/书籍/实现。

然而，算法介绍 (CLRS)使用了一个非常常见的变体。在这个变体中，有特殊的NIL孩子。一个NIL孩子包含一个特殊的“Null”键，表明它只是一片叶子。

RB 树的不变量是：

  1. 每个节点不是红色就是黑色。
  2. 根是黑色的。
  3. 每片叶子 ( NIL) 都是黑色的。
  4. 如果一个节点是红色的，那么它的两个子节点都是黑色的。
  5. 对于每个节点，从节点到后代叶子的所有简单路径都包含相同数量的黑色节点

请特别注意，不变的 3 -NIL节点是黑色的。

使用这个常见的变体，你的 RB 树有 4 个额外的节点：

  1. 10岁的右孩子

  2. 5的右孩子

  3. 2的左右孩子

5 的右孩子是您失踪的兄弟姐妹。

于 2016-11-03T13:36:13.107 回答