1

これは、インターバルツリーをトラバースするために私が書いた関数です。ただし、一部のノードにアクセスできないことに気付きました。コードがかなり明確であると仮定すると、どこで失敗したかを知りたいです。

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

1 に答える 1

0

ツリー内のすべてのノードは、p などの点を中心としています。左のサブツリーには p の左側にあるすべての区間が含まれ、右のサブツリーには p の右側にあるすべての区間が含まれます。ノード自体には、p と重複するすべての間隔が含まれます。

x < p の場合、x を含む左側のサブツリーからの間隔が存在する可能性がありますが、x (および p) を含むノード自体からの間隔も存在する可能性があります。唯一の保証は、右のサブツリーに x を含む間隔が含まれないことです。

したがって、ノード自体にこれらの間隔がありません。

インターバルツリーが何であるかを知らなかったので、私の理解はここからですhttp://en.wikipedia.org/wiki/Interval_tree

于 2012-04-27T08:40:23.140 に答える