2-3树的Iterator对象

Question

我需要2-3树迭代器的帮助。我现在实现的方式是一种递归方法，它几乎类似于DFS。我从根目录初始化遍历，访问它的左分支，直到我到达一个叶节点，然后将它添加到链接列表中。一步一步地，当递归回溯时，左侧分支中的所有节点都会被添加，然后再添加根的第一个键来保持顺序。我也用中、右树枝做同样的事。一旦建立了链表，我只需返回它的迭代器。我想知道的是，这是为2-3树构建迭代器的最佳方法吗？我能改变什么来提高效率呢？我担心如果树变大了，递归调用可能会击中StackOverFlowError (lol，讽刺)。

private class Traversal
{
    LinkedList<Node> ordered;

    void traverseTree()
    {
        ordered = new LinkedList<>();                   // Reset the ordered list. traverseTree will be only called in case of modification
        traverse(root);                                 // Initialize traversal from the root.
    }

    void traverse(Node n)
    {
        if (n.children.size() == 0)                     // If it's a leaf node, add it to the linked list.
            ordered.add(n);
        else
        {
            traverse(n.children.get(0));                // Otherwise, first traverse the left branch
            ordered.add(new Node(n.keys.get(0)));       // When it is done, create a new node containing key 1 of the node n to keep it ordered.
            traverse(n.children.get(1));                // Then traverse the middle/right branch of n.
            if (n.children.size() == 3)                 // If there are 3 branches, then we still need to traverse it.
            {
                ordered.add(new Node(n.keys.get(1)));   // Before we traverse, create a new node containing the 2nd key of n to the list since everything is going to be greater than it in the right branch.
                traverse(n.children.get(2));            // Then traverse the last branch and add all encountered nodes in order.
            }
        }
    }
}

Answer 1

首先，必须提到的是，我将要描述的方式和您的方式都不允许进行“适当的”树遍历。您将始终只获得一个键，包装在一个Node对象中。如果要在树中进行实际迭代，并在x位置获得一个Node，而不是它的值，则可以修改您的版本和我的版本，以不返回非叶节点的键，而是返回节点本身的键。

还有一种不同的选择，就是在父母堆的基础上编写自己的迭代器。当涉及到时间约束时，这个选项并不一定更好，但是您将在没有递归的情况下进行操作，所以没有堆栈溢出是一个问题。如果你仔细考虑一下，你会发现，这只是一种“递归”的非常手工的方式。这是它的要点：

假设左下最下面的元素(在图示中)是您的第一个元素。我们叫它A吧。现在，要获得A，您必须遍历您的树，传递A的所有“父级”(显然它只有一个直接父级，但我指的是父级.)。现在，我们可以将A的每个父对象都推到Stack<Node>-type对象上。我们叫它S吧。现在，一旦我们到达A，我们将在S中获得A的路径(就像目录路径)。这足以让我们完成缓慢的递归。此遍历方法将手动执行递归方法“自动”执行的操作。在这里，我们实际上是在树中移动，而不是使用额外的List。

class TreeIterator implements Iterator
{
Node current, recentChild;
Stack<Node> parentsOfCurrentNode; //our S

TreeIterator(Node root)
{
    current = root;
    while(current.children.size() != 0)
    {
        parentsOfCurrentNode.push(current);
        current = current.children.get(0); //getting our initial A
    }
}
public Node next()
{
    if(current.children.size() == 0)
    {
        recentChild = current;
        current = parentsOfCurrentNode.pop();
        return current;
    }
    else if(recentChild == current.children.get(0))
    {//We just came from the left child so now we go to the middle one
        Node out = new Node(current.keys.get(0));// will always exist
        current = current.children.get(1); //middle path
        while(current.children.size() != 0)
        {
            parentsOfCurrentNode.push(current);
            current = current.children.get(0); /*traversing again to the lowest value
                 in the path with no children, 
                 triggering the first if-case when next is called*/
        }
        return out;
    }
    else if(recentChild == current.children.get(1))
    {//We just came from the right/middle child so now we go to the parent/right node
        if(current.children.size() == 2)
        {
            recentChild = current;
            if(!parentsOfCurrentNode.isEmpty())
            {
                current = parentsOfCurrentNode.pop();
                while(current.children.get(current.children.size()-1) == recentChild)
                {//testing for always rigth-most Node
                    if(parentsOfCurrentNode.isEmpty())
                    {
                        return null; //no more elements
                    }
                    recentChild = current;
                    current = parentsOfCurrentNode.pop();
                }
                //we are now guaranteed to be at a point where the most recent node was not the right most node
                if(recentChild == current.children.get(0))
                {//We just came from the left child so now we go to the middle one
                    Node out = new Node(current.keys.get(0));// will always exist
                    current = current.children.get(1); //middle path
                    while(current.children.size() != 0)
                    {
                        parentsOfCurrentNode.push(current);
                        current = current.children.get(0); /*traversing again to the lowest value
                            in the path with no children, 
                            triggering the first if-case when next is called*/
                    }
                    return out;
                }
                else if(recentChild == current.chidren.get(1))
                {//Can only happen for size 3 de facto
                    Node out = new Node(current.keys.get(1)//
                            current = current.children.get(2); //right path
                    while(current.children.size() != 0)
                    {
                        parentsOfCurrentNode.push(current);
                        current = current.children.get(0); /*traversing again to the lowest value
                            in the path with no children, 
                             triggering the first if-case when next is called*/
                    }
                    return out;
                }   
            }   
        }
        else
        { //this is size 3 so we continue
            Node out = new Node(current.keys.get(1));//
            current = current.children.get(2); //right path
            while(current.children.size() != 0)
            {
                parentsOfCurrentNode.push(current);
                current = current.children.get(0); /*traversing again to the lowest value
                 in the path with no children, 
                 triggering the first if-case when next is called*/
            }
            return out;
        }
    }
    else
    {//we are coming from right child and current is of size 3
        recentChild = current;
        if(!parentsOfCurrentNode.isEmpty())
        {
            current = parentsOfCurrentNode.pop();
            while(current.children.get(current.children.size()-1) == recentChild)
            {//testing for always rigth-most Node
                if(parentsOfCurrentNode.isEmpty())
                {
                    return null; //no more elements
                }
                recentChild = current;
                current = parentsOfCurrentNode.pop();
            }
            //we are now guaranteed to be at a point where the most recent node was not the right-most node
            if(recentChild == current.children.get(0))
            {//We just came from the left child so now we go to the middle one
                Node out = new Node(current.keys.get(0));// will always exist
                current = current.children.get(1); //middle path
                while(current.children.size() != 0)
                {
                    parentsOfCurrentNode.push(current);
                    current = current.children.get(0); /*traversing again to the lowest value
                        in the path with no children, 
                        triggering the first if-case when next is called*/
                }
                return out;
            }
            else
            {//Can only happen for size 3 de facto
                Node out = new Node(current.keys.get(1));//
                        current = current.children.get(2); //right path
                while(current.children.size() != 0)
                {
                    parentsOfCurrentNode.push(current);
                    current = current.children.get(0); /*traversing again to the lowest value
                        in the path with no children, 
                         triggering the first if-case when next is called*/
                }
                return out;
            }
        }
    }
    return null; //if it ever gets here something is seriously wrong
}
} //end of class

因此，这只是Java接口中指定的next()方法(我猜这就是您所使用的语法)。请记住，您还必须实现hasNext()和可选的remove()，在本例中，这实际上将从树中删除。可以通过以下方式实现hasNext()

( a)在构造迭代器并在每次调用current时将hasNext()与其进行比较时，找到最正确的元素。这种方法是静态的，这意味着对树的更改不会被考虑在内。

( b)检查current是否已经是最正确的元素。如果您想这样做，只要在我们返回到根时查看代码，并检查我们现在所在的节点是否是最右边的节点(请注意，您必须克隆Stack，否则您将失去所有父节点)。

后一种检查是动态的，但速度非常慢。因此，第一次检查对时间效率的影响要好得多。

从整体上讲，这个方法是保存起来的，不会导致stack overflow，而且它使用的内存更少，因为我们在Tree本身中移动。另一方面，它在访问过程中速度较慢，运行时的O(d)是树的深度，是最大的时间复杂度。另一个问题是，hasNext()方法需要链接到最右边的元素，以提高时间效率(O(1))。否则，将始终由O(d)来确定您的迭代器是否有下一个元素。因此，不抛出StackOverflowError的优势在于与整个时间复杂度更高的竞争。对你来说更重要的是由你来决定。(编辑:您应该记住，最糟糕的情况复杂性是O(d)而不是O(n) (其中n是树中的元素数)。

你问过你能做些什么来提高效率:什么都没有。在某个地方你总是会失去一些效率。我喜欢您将所有数据放在一个列表中并使用它的迭代器的方法，它很好，而且很流畅，而且肯定比我建议的变体更高效。我只是想给你们一个不同的角度，因为即使你的问题很广泛，但这是有道理的。简单的答案仍然是，您所做的对于遍历是最有效的，您只需告诉自己，没有人会创建一个足够大的Tree来破坏它。

也不要一字一句地取代码，这可能不是100%的错误。我没有心情构建一个像您这样的Node类，所以它可能不会100%地使用您所拥有的。如果你真的需要2到3棵巨大的树的东西，选择我的方法，重写它来满足你的需要。