Tag: 2 3 4树

什么额外的轮换是需要从自上而下删除2-3-4左红黑树？

我一直在实现一个LLRB包，应该能够以Sedgewick （ 代码改进的代码） 描述的自下而上2-3或自上而下2-3-4两种模式中的任何一种模式进行操作，尽pipe只处理2- 3棵树在这里 ，感谢RS指针）。 Sedgewick为2-3模式提供了一个非常清晰的树操作描述，尽pipe他花费了大量的时间来讨论2-3-4模式。 他还展示了如何简单地改变插入过程中的颜色翻转顺序，可以改变树的行为（或者在2-3-4的路上分割，或者在2-3的path上分割）： private Node insert(Node h, Key key, Value value) { if (h == null) return new Node(key, value); // Include this for 2-3-4 trees if (isRed(h.left) && isRed(h.right)) colorFlip(h); int cmp = key.compareTo(h.key); if (cmp == 0) h.val = value; else if (cmp < 0) h.left = insert(h.left, […]