Итератор объекта для 2-3 дерева
Мне нужна помощь с итератором для 2-3 дерева. То, как я сейчас реализую, - это рекурсивный подход, который почти аналогичен DFS. Я инициализирую обход из корня, посещаю его левую ветвь, пока не достигну узла листа, а затем добавляю его в Linked-List. Шаг за шагом, по мере возврата рекурсии, добавляются все узлы в левой ветви и затем 1-й ключ корня, чтобы сохранить порядок. Я делаю то же самое со средней и правой веткой. Как только связанный список построен, я просто возвращаю его итератор. То, что я хотел знать, что это лучший способ построить итератор для дерева 2-3? Что я могу изменить, чтобы сделать его эффективным? Я беспокоюсь, что если дерево станет огромным, рекурсивные вызовы могут попасть в StackOverFlowError (смеется, ирония).
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.
}
}
}
}
1 ответ
Прежде всего, важно отметить, что ни способ, которым я собираюсь описать, ни ваш способ не допускают "правильного" обхода дерева. Вы всегда получите только один ключ, завернутый в Node объект. Если вы хотите на самом деле перебрать дерево и получить Node в позиции x, а не в ее значении, вы можете изменить как свою, так и мою версию, чтобы она не возвращала ключи неконечных узлов, а сами узлы.
Там также может быть другой вариант, написав свой собственный итератор на основе стеков родителей. Этот параметр не обязательно лучше, когда речь идет о временных ограничениях, но вы будете работать без рекурсии, поэтому переполнение стека не является проблемой. Если вы немного подумаете об этом, то увидите, что это просто очень ручной способ делать вещи "рекурсивно". Вот суть этого:
Предположим, что самый левый нижний элемент (на графической иллюстрации) является вашим первым элементом. Давайте назовем это A, Теперь, чтобы получить вас A вам придется пройти через свое дерево, пройдя всех "родителей" A (очевидно, у него есть только один прямой родитель, но я имею в виду родителя родителя...). Теперь мы можем подтолкнуть каждого родителя A на Stack<Node>тип объекта Давайте назовем это S, Теперь, когда мы достигаем A у нас будет путь A в S (как путь к каталогу). Это достаточно хорошо для нас, чтобы сделать нашу медленную рекурсию. Этот метод обхода будет вручную выполнять то, что выполнял ваш рекурсивный метод "автоматически". Здесь мы на самом деле движемся в дереве, а не работать с дополнительным 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
Так что это только next() метод, указанный в Iterator интерфейс Java (я догадался, что это то, что вы используете из-за синтаксиса, который вы используете). Пожалуйста, имейте в виду, что вы также должны реализовать hasNext() и опционально remove(), который в этом случае теперь будет фактически удален из вашего дерева. hasNext() может быть реализовано
а) найти самый правый элемент при создании итератора и сравнить current к нему всякий раз, когда hasNext() называется. Этот подход делает его статичным, что изменения дерева не будут приниматься во внимание.
б) проверка, если current это самый правый элемент уже. Если вы хотите сделать это, просто смотрите на код всякий раз, когда мы возвращаемся к корню, и проверяем, является ли узел, в котором мы сейчас находимся, узлом, расположенным наиболее справа (помните, что вы должны клонировать Stack в противном случае вы потеряете всех родителей).
Последняя проверка является динамической, но очень медленной. Первая проверка, таким образом, намного лучше для эффективности времени.
В целом этот метод сохраняется, чтобы не вызывать stack overflow и он использует меньше памяти, так как мы движемся в Tree сам. С другой стороны, это медленнее во время доступа, с O(d) во время выполнения d быть глубиной вашего дерева, быть максимальной временной сложностью. Другая проблема заключается в том, что hasNext() метод должен быть связан с самым правым элементом, чтобы экономить время (O(1)). Иначе это всегда будет O(d) чтобы узнать, есть ли у вашего итератора следующий элемент. Таким образом, преимущество не бросать StackruError конкурирует с более высокой временной сложностью в целом. Что для вас важнее, это решать вам. (РЕДАКТИРОВАТЬ: Вы должны иметь в виду, что сложность наихудшего случая O(d) и не O(n) (где n это количество элементов в дереве).)
Вы спросили, что вы можете сделать, чтобы сделать это эффективным: ничего. Вы всегда будете где-то терять эффективность. Мне нравится ваш подход, состоящий в том, чтобы просто поместить все ваши данные в список и использовать его итератор, это красиво и плавно, и определенно более эффективно, чем мой предложенный вариант. Я просто хотел дать вам другой взгляд на это, потому что, хотя ваш вопрос широк, он оправдан. Простой ответ по-прежнему заключается в том, что то, что вы делаете, наиболее эффективно для обхода, и вы просто должны сказать себе, что никто никогда не создаст Tree достаточно большой, чтобы сломать его.
Также не принимайте кодовое слово в слово, это, вероятно, не на 100% без ошибок. Я не был в настроении, чтобы построить Node класс так же, как ваш, так что он не может работать на 100% с тем, что у вас есть. Если вам действительно нужно что-то для огромных 2-3 деревьев и выберите мой подход, перепишите его для своих нужд.