我目前正在实现二维范围树。我无法为我的 Node 类想出一个合理的模型(用 Java)。
树中的节点可能具有以下任何一项:中间值、左右子指针、子树、数据指针和/或上一个和下一个指针。
我已将节点分解为三个独立的逻辑部分
- a) 只有 midRange 值的节点 - 每个节点都有一个 midRange
- b) 具有左、右和子树点的节点。这表示一个非叶节点。
- c) 不适用于 next、prev 和数据指针。这代表一个叶节点。
我尝试应用复合模式和装饰模式,但无济于事。 我尝试制作:
- 具有所有可能的 getter/setter 的节点接口(interface),即:getMidRange、getLeft、getRight、setLeft、setRight 等...
- 让两个类实现接口(interface):Node2D 和 LinkedNode(叶节点)。除了保留指向下一个和上一个的链接之外,Node2D 做了所有事情。而 LinkedNode 仅保留指向下一个和上一个的链接。
它是这样工作的,但我在想是否有更好的方法将其建模为一组类?
编辑:范围树(简短信息):在范围树中 - 所有数据都存储在叶节点中,并且树始终是平衡的。此外,所有叶子都处于相同的高度。此外,叶子被排序,并通过双向链表链接在一起。最后但并非最不重要的一点是,每个非叶节点都有一个子树——它也是一个范围树,但是叶子在下一个属性上排序(如果原始树是在 x 上排序的,则说 y ).
最佳答案
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;
}
关于java - 对 RangeTree 中的节点建模,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4980065/