Интервал обхода дерева

Вот функция, которую я написал для обхода дерева интервалов. Я заметил, что он не может посетить некоторые узлы, хотя. Предполагая, что код довольно ясен, я хочу знать, где он терпит неудачу.

public boolean searchTree(Node node,int x)
{

            while(node!=null&&!node.getInterval().containsPoint(x))
            {
                if(node.getNodeLeft()!=null&&(node.getNodeLeft().getMax()>=x))
                {
                    node=node.getNodeLeft();
                }
                else
                {
                    node=node.getNodeRight();
                }       
            }
           return node!=null;
}
Источник

1 ответ

Любой узел в дереве центрирован вокруг точки, скажем, p. Левое поддерево содержит все интервалы, которые находятся слева от p, правое поддерево содержит все интервалы, которые находятся справа от p. Сам узел содержит все интервалы, которые перекрывают p.

Теперь, если ваше x

Таким образом, вы пропустите эти интервалы в самом узле.

Я не знал, что такое интервальное дерево, поэтому мое понимание отсюда http://en.wikipedia.org/wiki/Interval_tree

Источник
Другие вопросы по тегам