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