标签: 2-3-4-tree

我一直在实现一个LLRB软件包,它应该能够在Sedgewick描述的两种模式中的任何一种操作,Bottom-Up 2-3或Top-Down 2-3-4 (代码 - 改进代码,但只处理2- 这里有 3棵树,感谢RS指针).

Sedgewick为2-3模式提供了非常清晰的树操作描述,尽管他花了很多时间谈论2-3-4模式.他还展示了在插入过程中对颜色翻转顺序的简单改变如何改变树的行为(在向下分割2-3-4或在向上分割2-3分割时):

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, key, value);
    else              h.right = insert(h.right, key, value);

    if (isRed(h.right) && !isRed(h.left))    h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left)) h = …

我对2-3-4树在操作后如何维持高度平衡属性操作有了基本的了解,以确保即使最坏的情况操作也是O(n logn).

但我不明白它知道为什么只有2-3-4？

为什么不2-3或2-3-4-5等？

我正在尝试将2-3-4树转换为java中的红黑树,但我很难搞清楚它.

我写了这两个基本类如下,以使问题简单明了,但无法弄清楚从哪里开始.

public class TwoThreeFour<K> {
    public List<K> keys;
    public List<TwoThreeFour<K>> children;
}

public class RedBlack<K> {
    public K key;
    public boolean isBlack;
    public RedBlack<K> left,right;
    public RedBlack<K key, boolean isBlack, RedBlack<K> left, RedBlack<K> right){
        this.key = key; this.isBlack = isBlack; this.left = left; this.right = right;
    }
}

我假设2-3-4树是有效的,并且想要在调用方法时返回一个红黑树.

我也试过以下代码而没有运气:

public convert(TwoThreeFour<K> tTF){
    if (ttf.keys.size() == 3)
        RedBlack<K> node = RedBlack<ttf.keys[1], true, RedBlack<ttf.keys[0], false, /* not sure what to put here for left */, /* not sure what to …

我对红黑树和2-3-4树都有基本的了解,以及它们如何保持高度平衡,以确保最坏情况下的操作是O(n logn).

但是,我无法理解维基百科的这篇文章

2-3-4树是红黑树的等轴测图,这意味着它们是等效的数据结构.换句话说,对于每2-3-4树,存在至少一个具有相同顺序的数据元素的红黑树.此外,2-3-4树上的插入和删除操作会导致节点扩展,拆分和合并,这相当于红黑树中的颜色翻转和旋转.

我不知道这些操作是如何相同的.维基百科上的引用是否准确？怎么能看到操作是等效的？

在下面描述的2-3-4树中(来自Java中的数据结构和算法,第2版),为什么插入99会导致节点分裂,83/92/104当它看起来像是99已经被插入到正确的孩子(C孩子,进入紧接着发现97)没有任何分裂吗？

首先，这个问题不是家庭作业。我目前正在阅读 Robert Lafore 的“数据结构和算法第 2 版”一书。在第 10 章中，我们学习了 2-3-4 棵树，然后被要求编写一个方法来找到这棵树中的最小值。

从概念的角度来看，我理解最小值在哪里。它只是叶子中最左边的数据项。

从编程的角度来看，我对如何实现一种方法来查找此数据项感到有些困惑。我有一个布尔值可以判断节点是否是叶子。所以我最初做的是这样的：

  public long minValue() {
   Node curNode = root; // current node = root
   long min = curNode.getMin();
   while(!curNode.isLeaf()) { // while current node is NOT a leaf
       curNode = getNextChild(curNode, min);
   } // end while
   return min;
} // end minValue()

这是做什么的（至少我认为它应该做的是创建一个从根节点开始的 curNode。然后创建一个存储 curNode.getMin 的最小值。getMin() 只是在索引 0 处获取数组中的值（其中应该保持最小值。那么，当当前节点不是叶子时，我们应该从最小值点遍历到下一个子节点。一旦当前节点是叶子，它应该返回最小值。

但这不起作用。有没有人知道如何实现这一点？提示或建议或其他任何东西？

编辑：要查看每个类以及它们如何交互，这里是每个单独类的链接。我把最小值方法放在我的 Tree234 类中

DataItem、Node、Tree234以及程序运行的地方Tree234App

我正在复习数据结构课上的材料，我对这三种树的用法有点困惑。那么什么情况下我们最好分别使用二叉搜索树、2-3树和B树呢？有什么优点和缺点？

太感谢了！我对数据结构很陌生......