2-3 树的迭代器对象
Iterator object for a 2-3 Tree
我需要有关 2-3 树迭代器的帮助。我现在正在实施的方式是一种递归方法，它几乎类似于 DFS。我从根初始化遍历，访问它的左分支，直到我找到一个叶节点，然后将它添加到链表中。一步一步，随着递归回溯，左分支中的所有节点都被添加，然后添加根的第一个键以保持顺序。我对中间和右边的分支做同样的事情。建立链表后，我只是 return 它是迭代器。我想知道的是，这是为 2-3 树构建迭代器的最佳方式吗？我可以改变什么来提高效率？我担心如果树变得很大，递归调用可能会遇到 WhosebugError（哈哈，讽刺。）
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.
}
}
}
}
首先，重要的是要提到我将要描述的方式和您的方式都不允许 "proper" 树遍历。您将始终只获得一个密钥，包裹在 Node object 中。如果您想实际遍历树并在位置 x 处获得 Node 而不是它的值，您可以修改您和我的版本以不 return non-leaf 节点的键但是节点本身。
也可以有一个不同的选择，即根据 parent 的堆栈编写您自己的迭代器。当涉及时间限制时，此选项不一定更好，但您将在没有递归的情况下进行操作，因此堆栈溢出不是问题。如果你稍微考虑一下，你会发现，这只是一种非常手动的做事方式 "recursively"。这是它的要点：
假设 left-bottom-most 元素（在图示中）是您的第一个元素。我们称它为 A。现在要得到你 A 你将不得不遍历你的树，传递 A 的所有 "the parents" （显然它只有一个直接 parent 但我指的是 parent 的 parent...）。现在我们可以将 A 的每个 parent 推到 Stack<Node> 类型的 object 上。我们称它为 S。现在，一旦我们到达 A，我们将在 S 中获得 A 的路径（类似于目录路径）。这足以让我们进行慢速递归。这种遍历方法将手动执行您的递归方法执行的操作 "automatically"。在这里，我们实际上在树中四处移动，而不是使用额外的 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 的 Iterator 接口中指定的 next() 方法（由于您使用的语法，我猜这就是您正在使用的方法）。请记住，您还必须实施 hasNext() 和可选的 remove()，在这种情况下，它现在实际上将从您的树中删除。 hasNext() 可以通过
实现
a) 在构造迭代器时找到 right-most 元素，并在调用 hasNext() 时将 current 与它进行比较。这种方法使其成为静态的，这意味着不会考虑对树的更改。
b) 检查 current 是否已经是 right-most 元素。如果你想这样做，只需在我们遍历根时查看代码并检查我们现在所在的节点是否是最右边的节点（请注意你必须克隆 Stack否则你将失去所有 parents).
后一种检查是动态的，但速度很慢。因此，第一次检查在时间效率方面更好。
总的来说，此方法不会导致 stack overflow，并且由于我们在 Tree 本身中移动，因此它使用的内存较少。另一方面，它在访问期间较慢，在运行时 O(d) d 是树的深度，是最大时间复杂度。另一个问题是 hasNext() 方法需要链接到 right-most 元素以提高时间效率 (O(1))。否则它总是 O(d) 来确定你的迭代器是否有下一个元素。因此，从不抛出 WhosebugError 的优势在于与更高的总体时间复杂度竞争。对您来说更重要的是您的决定。 （编辑：您应该记住，最坏情况下的复杂度是 O(d) 而不是 O(n) （其中 n 是树中元素的数量）。）
你问你可以做些什么来提高效率：什么都没有。你总会在某处失去一些效率。我喜欢你将所有数据放在一个列表中并使用它的迭代器的方法，它很好而且很流畅，而且 肯定 比我提出的变体更有效。我只是想给你一个不同的角度，因为即使你的问题很广泛，它也是有道理的。简单的答案仍然是你正在做的是最有效的遍历，你只需要告诉自己没有人会创建一个大到足以破坏它的Tree。
也不要逐字逐句地接受代码，它可能不是 100% 没有错误的。我没有心情像您一样构建 Node class，因此它可能无法 100% 与您现有的配合使用。如果您真的需要 2-3 棵巨大的树的东西并选择我的方法，请根据您的需要重写它。
我需要有关 2-3 树迭代器的帮助。我现在正在实施的方式是一种递归方法，它几乎类似于 DFS。我从根初始化遍历，访问它的左分支，直到我找到一个叶节点，然后将它添加到链表中。一步一步，随着递归回溯，左分支中的所有节点都被添加，然后添加根的第一个键以保持顺序。我对中间和右边的分支做同样的事情。建立链表后，我只是 return 它是迭代器。我想知道的是，这是为 2-3 树构建迭代器的最佳方式吗？我可以改变什么来提高效率？我担心如果树变得很大，递归调用可能会遇到 WhosebugError（哈哈，讽刺。）
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.
}
}
}
}
首先，重要的是要提到我将要描述的方式和您的方式都不允许 "proper" 树遍历。您将始终只获得一个密钥，包裹在 Node object 中。如果您想实际遍历树并在位置 x 处获得 Node 而不是它的值，您可以修改您和我的版本以不 return non-leaf 节点的键但是节点本身。
也可以有一个不同的选择，即根据 parent 的堆栈编写您自己的迭代器。当涉及时间限制时，此选项不一定更好，但您将在没有递归的情况下进行操作，因此堆栈溢出不是问题。如果你稍微考虑一下，你会发现，这只是一种非常手动的做事方式 "recursively"。这是它的要点：
假设 left-bottom-most 元素（在图示中）是您的第一个元素。我们称它为 A。现在要得到你 A 你将不得不遍历你的树，传递 A 的所有 "the parents" （显然它只有一个直接 parent 但我指的是 parent 的 parent...）。现在我们可以将 A 的每个 parent 推到 Stack<Node> 类型的 object 上。我们称它为 S。现在，一旦我们到达 A，我们将在 S 中获得 A 的路径（类似于目录路径）。这足以让我们进行慢速递归。这种遍历方法将手动执行您的递归方法执行的操作 "automatically"。在这里，我们实际上在树中四处移动，而不是使用额外的 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 的 Iterator 接口中指定的 next() 方法（由于您使用的语法，我猜这就是您正在使用的方法）。请记住，您还必须实施 hasNext() 和可选的 remove()，在这种情况下，它现在实际上将从您的树中删除。 hasNext() 可以通过
a) 在构造迭代器时找到 right-most 元素，并在调用 hasNext() 时将 current 与它进行比较。这种方法使其成为静态的，这意味着不会考虑对树的更改。
b) 检查 current 是否已经是 right-most 元素。如果你想这样做，只需在我们遍历根时查看代码并检查我们现在所在的节点是否是最右边的节点（请注意你必须克隆 Stack否则你将失去所有 parents).
后一种检查是动态的，但速度很慢。因此，第一次检查在时间效率方面更好。
总的来说，此方法不会导致 stack overflow，并且由于我们在 Tree 本身中移动，因此它使用的内存较少。另一方面，它在访问期间较慢，在运行时 O(d) d 是树的深度，是最大时间复杂度。另一个问题是 hasNext() 方法需要链接到 right-most 元素以提高时间效率 (O(1))。否则它总是 O(d) 来确定你的迭代器是否有下一个元素。因此，从不抛出 WhosebugError 的优势在于与更高的总体时间复杂度竞争。对您来说更重要的是您的决定。 （编辑：您应该记住，最坏情况下的复杂度是 O(d) 而不是 O(n) （其中 n 是树中元素的数量）。）
你问你可以做些什么来提高效率：什么都没有。你总会在某处失去一些效率。我喜欢你将所有数据放在一个列表中并使用它的迭代器的方法，它很好而且很流畅，而且 肯定 比我提出的变体更有效。我只是想给你一个不同的角度，因为即使你的问题很广泛，它也是有道理的。简单的答案仍然是你正在做的是最有效的遍历，你只需要告诉自己没有人会创建一个大到足以破坏它的Tree。
也不要逐字逐句地接受代码，它可能不是 100% 没有错误的。我没有心情像您一样构建 Node class，因此它可能无法 100% 与您现有的配合使用。如果您真的需要 2-3 棵巨大的树的东西并选择我的方法，请根据您的需要重写它。