Modeling a Node in a RangeTree

Question

I am currently implementing a 2D Range Tree. I am having trouble coming up with a plausible model (in Java) for my Node class.

A node in the tree may have any of the following: midrange value, right and left child pointer, subtree, data pointer and/or previous and next pointers.

I have broken down the Node into three separate logical pieces

• a) Node with just midRange value - every node has a midRange
• b) Node with left, right and subtree points. This represents a non-leaf node.
• c) Not with next, prev and data pointers. This represents a leaf node.

I tried applying Composite and Decorator patterns, but to no avail. I tried making:

1. Node interface with all the possible getters/setters, i.e.: getMidRange, getLeft, getRight, setLeft, setRight, etc...
2. Having two classes implement the interface: Node2D and LinkedNode (leaf node). Node2D did everything except keep the links to next and previous. While LinkedNode only kept links to next and previous.

It works like that, but I was wandering if there is a nicer way of modeling this as a set of classes?

EDIT: Range Tree (short info): In range trees - all data is stored in the Leaf nodes, and the tree is always balanced. Furthermore all leafs are at the same height. Also, the leaves are sorted, and linked together by a doubly linked list. Last, but not least, each non-leaf node has a subtree - which is also a range tree, but with the leaves sorted on next attribute (say y if original tree was sorted on 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;
}