在RangeTree中建模节点

Question

我目前正在实施2D范围树.我在为我的Node类提出一个似乎合理的模型(用Java)时遇到了麻烦.

树中的节点可以具有以下任何一个:中间值,右和左子指针,子树,数据指针和/或前一个和下一个指针.

我将节点分解为三个独立的逻辑部分

• a)具有midRange值的节点 - 每个节点都有一个midRange
• b)具有左,右和子树点的节点.这表示非叶节点.
• c)不是next,prev和数据指针.这表示叶节点.

我尝试应用Composite和Decorator模式,但无济于事.我试过制作:

1. 节点接口包含所有可能的getter/setter,即:getMidRange,getLeft,getRight,setLeft,setRight等...
2. 有两个类实现接口:Node2D和LinkedNode(叶节点).Node2D做了所有事情,除了保持下一个和上一个的链接.虽然LinkedNode只保留了下一个和上一个的链接.

它是这样的,但是如果有一种更好的方法将它建模为一组类,我就会徘徊？

编辑:范围树(简短信息):在范围树中 - 所有数据都存储在Leaf节点中,并且树始终是平衡的.此外,所有叶子都处于相同的高度.此外,叶子被分类,并通过双向链表链接在一起.最后,但并非最不重要的是,每个非叶子节点都有一个子树 - 它也是一个范围树,但是叶子在下一个属性上排序(比如y,如果原始树在x上排序).

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