5

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).

RangeTreeBreakdown

OmG
  • 18,337
  • 10
  • 57
  • 90
Andriy Drozdyuk
  • 58,435
  • 50
  • 171
  • 272
  • 1
    If nodes do not switch between leaf and non-leaf status as the structure evolves, I would be tempted to create an abstract class out of A with B and C being its two concrete subclasses. If, as in a binary search tree, a node is a leaf simply because it currently has no children but may get children later, I would use a single class. I don't see any meaningful patterns here since there are no interactions, but I'm not familiar with range trees. – David Harkness Feb 12 '11 at 20:49
  • Yes, nodes do not switch from leaf to non-leaf. All data is stored in the leafs. Sorry about that, I'll edit the question. – Andriy Drozdyuk Feb 12 '11 at 21:19

1 Answers1

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;
}
Dave O.
  • 2,231
  • 3
  • 21
  • 25