java - 对 RangeTree 中的节点建模

Question

我目前正在实现二维范围树。我无法为我的 Node 类想出一个合理的模型(用 Java)。

树中的节点可能具有以下任何一项:中间值、左右子指针、子树、数据指针和/或上一个和下一个指针。

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

• a) 只有 midRange 值的节点 - 每个节点都有一个 midRange
• b) 具有左、右和子树点的节点。这表示一个非叶节点。
• c) 不适用于 next、prev 和数据指针。这代表一个叶节点。

我尝试应用复合模式和装饰模式，但无济于事。我尝试制作:

1. 具有所有可能的 getter/setter 的节点接口(interface)，即:getMidRange、getLeft、getRight、setLeft、setRight 等...
2. 让两个类实现接口(interface):Node2D 和 LinkedNode(叶节点)。除了保留指向下一个和上一个的链接之外，Node2D 做了所有事情。而 LinkedNode 仅保留指向下一个和上一个的链接。

它是这样工作的，但我在想是否有更好的方法将其建模为一组类？

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

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