红黑树：Kahrs 版本
Red Black Trees: Kahrs version
我目前正在尝试理解 Okasaki 提供的红黑树实现和 Kahrs (the untyped version) 提供的删除方法。
在删除实现中使用了一个函数app，似乎"merging" 节点的子节点被删除。再一次，该算法似乎使用相同的 "break" 红-红 属性 而不是黑色高度（如果我错了请纠正我）。我们总是在创建红色节点（即使我们打破 Red-Red 属性)。沿着以被删除节点为根的子树走下去，纠正红-红违规，一旦我们到达叶子，我们开始沿着路径向上走（从创建的 "new tree" 合并开始）修复红-红违规路径。
app :: RB a -> RB a -> RB a
app E x = x
app x E = x
app (T R a x b) (T R c y d) =
case app b c of
T R b' z c' -> T R(T R a x b') z (T R c' y d)
bc -> T R a x (T R bc y d)
app (T B a x b) (T B c y d) =
case app b c of
T R b' z c' -> T R(T B a x b') z (T B c' y d)
bc -> balleft a x (T B bc y d)
app a (T R b x c) = T R (app a b) x c
app (T R a x b) c = T R a x (app b c)
- 我看不出我们是如何 "not creating" / "fixing" 黑色高度违规？删除黑色节点会在路径上方的某个节点处创建
bh-1 和 bh 子树。
- 来自 this paper 的结果，看起来这个实现非常快，"merge" 方法可能是解决速度提高的关键。
任何指向此 "merge" 操作的解释的指针都会很棒。
请注意，这不是作业问题或其他任何问题。我正在独立研究 Okasaki 中给出的实现并填写 "messy" 删除。
谢谢。
考虑到关于这个话题可以说的很多，我会尽量贴近您的问题，但如果我错过了一些重要的事情，请告诉我。
app 到底在干什么？
你是正确的，app 在下降的过程中打破了红色的不变量而不是黑色的不变量，并在返回的过程中修复了它。
它app结束或合并两个服从顺序属性，黑色不变，红色不变，并且具有相同black-depth的子树成为一个新的也服从顺序 属性、黑色不变式和红色不变式的树。一个值得注意的例外是根或 app rb1 rb2 有时是红色的并且有两个红色子树。这样的树被称为"infrared"。这在 delete 中通过在这一行中将根设置为黑色来处理。
case del t of {T _ a y b -> T B a y b; _ -> E}
声明 1 (Order 属性) 如果输入 rb1 和 rb2 分别服从命令 属性 （左子树 < 节点值 < 右子树）并且 rb1 中的最大值小于 rb2 中的最小值，则 app rb1 rb2 也服从顺序 属性.
这个很容易证明。事实上，您甚至可以在查看代码时看到它 - as 始终位于 bs 或 b's 的左侧，后者始终位于左侧cs 或 c's，它们始终位于 ds 的左侧。并且 b's 和 c's 也遵循此 属性 因为它们是使用子树 b 和 c 递归调用 app 的结果满足要求。
声明 2（红色不变量） 如果输入 rb1 和 rb2 服从红色不变量（如果一个节点是红色的，那么它的 children 是黑色的），那么 app rb1 rb2 中的所有节点也是黑色的，除了可能的根节点。但是，仅当其参数之一具有红色根时，根才可以是 "infrared"。
证明证明是通过在模式上分支。
- 对于案例
app E x = x 和 app x E = x，索赔是微不足道的
- 对于
app (T R a x b) (T R c y d)，索赔假设告诉我们所有a、b、c和d都是黑色的。由此可见 app b c 完全服从红色不变量（它不是红外线）。
- 如果
app b c 匹配 T R b' z c' 那么它的子树 b' 和 c' 必须是黑色的（并且服从红色不变量），所以 T R (T R a x b') z (T R c' y d) 服从red-invariant有红外根。
- 否则，
app b c产生黑色节点bc，所以T R a x (T R bc y d)服从红色不变量。
对于app (T B a x b) (T B c y d)我们只关心app b c本身会服从red-invariant
- 如果
app b c是红色节点，它可以是红外线，但是它的子树b'和c'，另一方面，必须完全服从红色不变量。这意味着 T R (T B a x b') z (T B c' y d) 也服从红色不变量。
现在，如果bc结果是黑色，我们调用balleft a x (T B bc y d)。这里巧妙的是，我们已经知道可以触发 balleft 的哪两种情况：取决于 a 是红色还是黑色
balleft (T R a x b) y c = T R (T B a x b) y c
balleft bl x (T B a y b) = balance bl x (T R a y b)
在第一种情况下，最终发生的是我们将左子树的颜色从红色交换为黑色（这样做不会破坏 red-invariant）并将所有内容放入红色子树。然后 balleft a x (T B bc y d) 实际上看起来像 T R (T B .. ..) (T B bc y d)，并且服从红色不变量。
否则，对balleft的调用会变成balance a x (T R bc y d)，而balance的全部意义在于它修复了根级别的红色违规。
对于app a (T R b x c)我们知道a和b一定是黑色的，所以app a b不是红外的，所以T R (app a b) x c服从红色不变量。 app a (T R b x c) 也是如此，但字母 a、b 和 c 被置换。
声明 3（黑色不变量） 如果输入 rb1 和 rb2 服从黑色不变量（从根到叶子的任何路径都有相同数量的黑色节点）并且具有相同的black-depth，app rb1 rb2也服从黑色不变量并且具有相同的black-depth。
证明证明是通过在模式上分支。
- 对于案例
app E x = x 和 app x E = x，索赔是微不足道的
- 对于
app (T R a x b) (T R c y d)，我们知道由于T R a x b和T R c y d具有相同的黑色深度，因此它们的子树a、b、c，和 d。根据声明（记住，这是归纳法！）app b c 也将服从黑色不变量并具有相同的黑色深度。现在，我们将证明分支到 case app b c of ...
- 如果
app b c 匹配 T R b' z c' 它是红色的，它的子树 b' 和 c' 将具有与 app b c （本身）相同的黑色深度，它又具有与 a 和 d 相同的黑色深度，因此 T R (T R a x b') z (T R c' y d) 服从黑色不变量并且具有与其输入相同的黑色深度。
- 否则，
app b c 产生了一个黑色节点 bc，但该节点再次具有与 a 和 d 相同的黑色深度，因此 T R a x (T R bc y d)作为一个整体仍然服从黑色不变量并且具有与其输入相同的黑色深度。
- 对于
app (T B a x b) (T B c y d)，我们再次立即知道那个子树a、b、c 和 d 都具有与 app b c 相同的黑色深度。和以前一样，我们在 case app b c of ... 上分支证明
- 如果
app b c 是 T R b' z c' 形式的红色节点，我们再次得到 b'、c'、a 和 d 具有相同的 black-depth，因此 T R (T B a x b') z (T B c' y d) 也具有相同的黑色深度
- 现在，如果
bc 结果是黑色的，我们应用与之前声明相同的推理来确定输出 balleft a x (T B bc y d) 实际上具有以下形式
T R (T B .. ..) (T B bc y d) 其中 (T B .. ..) 只是 a 重新着色为黑色，因此整个树将满足黑色不变量并且 black-depth 比任何 a、b、c 或 d，也就是说 black-depth 与输入 T B a x b 和 T B c y d) 相同。
balance a x (T R bc y d) 和 balance 保持黑色不变量。
- 对于
app a (T R b x c)或app (T R a x b) c，我们知道a、b和c都具有相同的black-depth，因此，这意味着 app a b 和 app b c 有相同的 black-depth，这意味着 T R (app a b) x c 和 T R (app a b) x c 也有相同的 black-depth
为什么快？
我的球拍有点生锈，所以我没有很好的答案。通常，app 允许您分两步完成所有操作，从而加快删除速度：向下移动到目标站点，然后继续向下合并子树，然后返回并修复不变量，一直到根。
在你引用的 paper 中，一旦你到达目标站点，你就会调用 min/delete （我认为这是关键的区别 - 否则旋转看起来非常相似）这将递归调用自身以在子树中找到可以放入目标站点的元素，以及在该元素被取出后子树的状态。我相信最后一部分会损害该实现的性能。
我目前正在尝试理解 Okasaki 提供的红黑树实现和 Kahrs (the untyped version) 提供的删除方法。
在删除实现中使用了一个函数app，似乎"merging" 节点的子节点被删除。再一次，该算法似乎使用相同的 "break" 红-红 属性 而不是黑色高度（如果我错了请纠正我）。我们总是在创建红色节点（即使我们打破 Red-Red 属性)。沿着以被删除节点为根的子树走下去，纠正红-红违规，一旦我们到达叶子，我们开始沿着路径向上走（从创建的 "new tree" 合并开始）修复红-红违规路径。
app :: RB a -> RB a -> RB a
app E x = x
app x E = x
app (T R a x b) (T R c y d) =
case app b c of
T R b' z c' -> T R(T R a x b') z (T R c' y d)
bc -> T R a x (T R bc y d)
app (T B a x b) (T B c y d) =
case app b c of
T R b' z c' -> T R(T B a x b') z (T B c' y d)
bc -> balleft a x (T B bc y d)
app a (T R b x c) = T R (app a b) x c
app (T R a x b) c = T R a x (app b c)
- 我看不出我们是如何 "not creating" / "fixing" 黑色高度违规？删除黑色节点会在路径上方的某个节点处创建
bh-1和bh子树。 - 来自 this paper 的结果，看起来这个实现非常快，"merge" 方法可能是解决速度提高的关键。
任何指向此 "merge" 操作的解释的指针都会很棒。
请注意，这不是作业问题或其他任何问题。我正在独立研究 Okasaki 中给出的实现并填写 "messy" 删除。
谢谢。
考虑到关于这个话题可以说的很多，我会尽量贴近您的问题，但如果我错过了一些重要的事情，请告诉我。
app 到底在干什么？
你是正确的，app 在下降的过程中打破了红色的不变量而不是黑色的不变量，并在返回的过程中修复了它。
它app结束或合并两个服从顺序属性，黑色不变，红色不变，并且具有相同black-depth的子树成为一个新的也服从顺序 属性、黑色不变式和红色不变式的树。一个值得注意的例外是根或 app rb1 rb2 有时是红色的并且有两个红色子树。这样的树被称为"infrared"。这在 delete 中通过在这一行中将根设置为黑色来处理。
case del t of {T _ a y b -> T B a y b; _ -> E}
声明 1 (Order 属性) 如果输入 rb1 和 rb2 分别服从命令 属性 （左子树 < 节点值 < 右子树）并且 rb1 中的最大值小于 rb2 中的最小值，则 app rb1 rb2 也服从顺序 属性.
这个很容易证明。事实上，您甚至可以在查看代码时看到它 - as 始终位于 bs 或 b's 的左侧，后者始终位于左侧cs 或 c's，它们始终位于 ds 的左侧。并且 b's 和 c's 也遵循此 属性 因为它们是使用子树 b 和 c 递归调用 app 的结果满足要求。
声明 2（红色不变量） 如果输入 rb1 和 rb2 服从红色不变量（如果一个节点是红色的，那么它的 children 是黑色的），那么 app rb1 rb2 中的所有节点也是黑色的，除了可能的根节点。但是，仅当其参数之一具有红色根时，根才可以是 "infrared"。
证明证明是通过在模式上分支。
- 对于案例
app E x = x和app x E = x，索赔是微不足道的 - 对于
app (T R a x b) (T R c y d)，索赔假设告诉我们所有a、b、c和d都是黑色的。由此可见app b c完全服从红色不变量（它不是红外线）。- 如果
app b c匹配T R b' z c'那么它的子树b'和c'必须是黑色的（并且服从红色不变量），所以T R (T R a x b') z (T R c' y d)服从red-invariant有红外根。 - 否则，
app b c产生黑色节点bc，所以T R a x (T R bc y d)服从红色不变量。
- 如果
对于
app (T B a x b) (T B c y d)我们只关心app b c本身会服从red-invariant- 如果
app b c是红色节点，它可以是红外线，但是它的子树b'和c'，另一方面，必须完全服从红色不变量。这意味着T R (T B a x b') z (T B c' y d)也服从红色不变量。 现在，如果
bc结果是黑色，我们调用balleft a x (T B bc y d)。这里巧妙的是，我们已经知道可以触发balleft的哪两种情况：取决于a是红色还是黑色balleft (T R a x b) y c = T R (T B a x b) y c balleft bl x (T B a y b) = balance bl x (T R a y b)在第一种情况下，最终发生的是我们将左子树的颜色从红色交换为黑色（这样做不会破坏 red-invariant）并将所有内容放入红色子树。然后
balleft a x (T B bc y d)实际上看起来像T R (T B .. ..) (T B bc y d)，并且服从红色不变量。否则，对
balleft的调用会变成balance a x (T R bc y d)，而balance的全部意义在于它修复了根级别的红色违规。
- 如果
对于
app a (T R b x c)我们知道a和b一定是黑色的，所以app a b不是红外的，所以T R (app a b) x c服从红色不变量。app a (T R b x c)也是如此，但字母a、b和c被置换。
声明 3（黑色不变量） 如果输入 rb1 和 rb2 服从黑色不变量（从根到叶子的任何路径都有相同数量的黑色节点）并且具有相同的black-depth，app rb1 rb2也服从黑色不变量并且具有相同的black-depth。
证明证明是通过在模式上分支。
- 对于案例
app E x = x和app x E = x，索赔是微不足道的 - 对于
app (T R a x b) (T R c y d)，我们知道由于T R a x b和T R c y d具有相同的黑色深度，因此它们的子树a、b、c，和d。根据声明（记住，这是归纳法！）app b c也将服从黑色不变量并具有相同的黑色深度。现在，我们将证明分支到case app b c of ...- 如果
app b c匹配T R b' z c'它是红色的，它的子树b'和c'将具有与app b c（本身）相同的黑色深度，它又具有与a和d相同的黑色深度，因此T R (T R a x b') z (T R c' y d)服从黑色不变量并且具有与其输入相同的黑色深度。 - 否则，
app b c产生了一个黑色节点bc，但该节点再次具有与a和d相同的黑色深度，因此T R a x (T R bc y d)作为一个整体仍然服从黑色不变量并且具有与其输入相同的黑色深度。
- 如果
- 对于
app (T B a x b) (T B c y d)，我们再次立即知道那个子树a、b、c和d都具有与app b c相同的黑色深度。和以前一样，我们在case app b c of ...上分支证明- 如果
app b c是T R b' z c'形式的红色节点，我们再次得到b'、c'、a和d具有相同的 black-depth，因此T R (T B a x b') z (T B c' y d)也具有相同的黑色深度 - 现在，如果
bc结果是黑色的，我们应用与之前声明相同的推理来确定输出balleft a x (T B bc y d)实际上具有以下形式T R (T B .. ..) (T B bc y d)其中(T B .. ..)只是a重新着色为黑色，因此整个树将满足黑色不变量并且 black-depth 比任何a、b、c或d，也就是说 black-depth 与输入T B a x b和T B c y d)相同。
balance a x (T R bc y d)和balance保持黑色不变量。
- 如果
- 对于
app a (T R b x c)或app (T R a x b) c，我们知道a、b和c都具有相同的black-depth，因此，这意味着app a b和app b c有相同的 black-depth，这意味着T R (app a b) x c和T R (app a b) x c也有相同的 black-depth
为什么快？
我的球拍有点生锈，所以我没有很好的答案。通常，app 允许您分两步完成所有操作，从而加快删除速度：向下移动到目标站点，然后继续向下合并子树，然后返回并修复不变量，一直到根。
在你引用的 paper 中，一旦你到达目标站点，你就会调用 min/delete （我认为这是关键的区别 - 否则旋转看起来非常相似）这将递归调用自身以在子树中找到可以放入目标站点的元素，以及在该元素被取出后子树的状态。我相信最后一部分会损害该实现的性能。