インターバルツリーのトラバーサル

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を含む区間が含まれないことです。

ノード自体にこれらの間隔がありません。

私inderstandingがここhttp://en.wikipedia.org/wiki/Interval_tree