algorithm - 区间树遍历

Question

这是我为遍历区间树而编写的函数。我注意到它无法访问某些节点。假设代码非常清晰，我想知道哪里出错了。

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;
}

Answer 1

树中的任何节点都以一个点为中心，比如 p。左子树包含 p 左边的所有区间，右子树包含 p 右边的所有区间。节点本身包含与 p 重叠的所有区间。

现在，如果您的 x < p，则左子树可能存在包含 x 的区间，但也可能存在来自节点本身的区间，其中包含 x(和 p)。唯一的保证是右子树不会包含包含 x 的区间。

因此您在节点本身中遗漏了这些间隔。

我不知道什么是区间树，所以我的理解来自这里http://en.wikipedia.org/wiki/Interval_tree