5

現在、2D 範囲ツリーを実装しています。Node クラスのもっともらしいモデル (Java で) を考え出すのに苦労しています。

ツリー内のノードは、次のいずれかを持つことができます: 中間値、右および左の子ポインター、サブツリー、データ ポインター、および/または前および次のポインター。

ノードを 3 つの個別の論理ピースに分割しました

  • a) midRange 値のみを持つノード - すべてのノードに midRange があります
  • b) 左点、右点、およびサブツリー ポイントを持つノード。これは非リーフ ノードを表します。
  • c) next、prev、および data ポインターを使用しない。これは葉ノードを表します。

Composite パターンと Decorator パターンを適用しようとしましたが、役に立ちませんでした。私は作ってみました：

  1. 可能なすべてのゲッター/セッターを備えたノード インターフェイス、つまり、getMidRange、getLeft、getRight、setLeft、setRight など...
  2. Node2D と LinkedNode (リーフ ノード) の 2 つのクラスでインターフェイスを実装します。Node2D は、次と前へのリンクを保持すること以外はすべて行いました。一方、LinkedNode は次と前へのリンクのみを保持していました。

それはそのように機能しますが、これを一連のクラスとしてモデル化するより良い方法があるかどうか、私はさまよっていましたか?

編集:範囲ツリー(短い情報): 範囲ツリーでは、すべてのデータがリーフ ノードに格納され、ツリーは常にバランスが取れています。さらに、すべての葉は同じ高さです。また、リーフはソートされ、二重リンク リストによってリンクされます。最後になりましたが、葉ではない各ノードにはサブツリーがあります。これは範囲ツリーでもありますが、葉は次の属性でソートされています (元のツリーがxでソートされていた場合はyとします)。

RangeTreeBreakdown

4

1 に答える 1

1 
abstract class AbstractNode {
    int midRange;
}

class InnerNode extends AbstractNode {
    AbstractNode left;
    AbstractNode right;
    AbstractNode subtree;
}

class LeafNode extends AbstractNode {
    LeafNode next;
    LeafNode prev;
    Object data;
}
于 2011-02-13T04:24:04.193 に答える