排序值的红黑树插入操作的行为
behavior of red-black tree insert operation for sorted values
我是数据结构的新手。我已经完成了红黑树插入算法的实现。我无法理解算法如何处理排序值的插入。
让我用数据集 [10, 5, 2] 来说明。
因此，将插入 Initial 10 并将其作为树的根，其颜色为黑色。
10
接下来，我们将在根 10 下添加 5。5 的颜色将为红色（截至目前，它不违反任何属性）。
现在，我们将添加 2。添加后，树将如下所示：-
添加 2（其颜色为红色）将违反不允许红色父项下的红色子项的规则。红黑树中有 3 种情况：-
所有这三种情况都假设 parentOf(newlyInsertedNode) 有兄弟节点。但在我的例子中，parentOf(2) = 5 没有兄弟姐妹。那么，红黑树算法将如何处理这种情况。
red-black 树的细节可能会因 article/book/implementation 的不同而略有不同。
但是，Introduction To Algorithms (CLRS) 使用了一个非常常见的变体。在这个变体中，有特殊的NILchildren。 NIL child 包含一个特殊的 "Null" 键，表明它只是一片叶子。
RB 树的不变量是：
- 每个节点不是红色就是黑色。
- 根是黑色的
- 每片叶子（
NIL）都是黑色的。
- 如果一个节点是红色的，那么它的 children 都是黑色的。
- 对于每个节点，从该节点到后代叶子的所有简单路径都包含相同数量的黑色节点
请特别注意，不变量 3 - NIL 节点是黑色的。
使用这个常见的变体，你的 RB 树有 4 个额外的节点：
右边child10
右child5
2左右children
5 中右边的 child 是您缺少的兄弟姐妹。
我是数据结构的新手。我已经完成了红黑树插入算法的实现。我无法理解算法如何处理排序值的插入。
让我用数据集 [10, 5, 2] 来说明。
因此，将插入 Initial 10 并将其作为树的根，其颜色为黑色。
10
接下来，我们将在根 10 下添加 5。5 的颜色将为红色（截至目前，它不违反任何属性）。
现在，我们将添加 2。添加后，树将如下所示：-
red-black 树的细节可能会因 article/book/implementation 的不同而略有不同。
但是，Introduction To Algorithms (CLRS) 使用了一个非常常见的变体。在这个变体中，有特殊的NILchildren。 NIL child 包含一个特殊的 "Null" 键，表明它只是一片叶子。
RB 树的不变量是：
- 每个节点不是红色就是黑色。
- 根是黑色的
- 每片叶子（
NIL）都是黑色的。 - 如果一个节点是红色的，那么它的 children 都是黑色的。
- 对于每个节点，从该节点到后代叶子的所有简单路径都包含相同数量的黑色节点
请特别注意，不变量 3 - NIL 节点是黑色的。
使用这个常见的变体，你的 RB 树有 4 个额外的节点：
右边child10
右child5
2左右children
5 中右边的 child 是您缺少的兄弟姐妹。