排序值的红黑树插入操作的行为

Question

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

让我用数据集10，5，2来说明。

因此，最初的10将被插入，并将是树的根和它的颜色将是黑色的。10

​

接下来，我们将在根10下添加5。5的颜色将是红色(从现在起，它没有违反任何属性)。

​

现在，我们将添加be 2。在加法后，树看起来如下:-

添加2(其颜色为红色)将违反规则，不允许红色的孩子下红色的父母。红黑树有3例:-所有3例均假定parentOf(newlyInsertedNode)有兄弟姐妹.但在我的例子中，parentOf(2) =5没有兄弟姐妹。那么，如何在红黑树算法中处理这个场景呢？

Answer 1

根据文章/书籍/实现的不同，红黑树的细节可能会有所不同。

然而，算法简介(CLRS)使用了一个非常常见的变体。在这个变体中，有一些特殊的NIL儿童。一个NIL子包含一个特殊的“空”键，表示它只是一个叶子。

RB树的不变量是：

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

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

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

1. 10岁的孩子
2. 5岁的孩子
3. 两个左右的孩子

5岁的孩子是你错过的兄弟姐妹。