From charlesreid1

Notes on object oriented principles when implementing binary trees.

Delegating responsibility for tasks:

  • for example how do you decide if the left/right method should be node.left, node.getLeft(), or tree.left(node)?
  • when designing a data structure, think ahead to the concrete implementation and how this will be extended.
  • trees have a complicated potential inheritance diagram...
    • Different concrete implementations - linked vs array
    • Different functionality (expressions vs search)
    • Further, internal classes and utilities might change (AVL trees)
    • Trees are used by other data structures (maps, sets, sorting, etc.)
  • Nail down the scope before you start
  • Not sure why, but it seems better to build it into the TREE whenever possible
  • However, if you can access data directly, like node.left = new Node(), why not do it that way?

Positions vs. Nodes

  • The Goodrich book makes a big deal about separating tree positions vs. tree nodes
  • This over-complicates things, but it boils down to this: the user is going to need positions in a tree for various algorithms, so the Position class gives them an object that they can use to point at particular nodes.
  • This avoids the cost of looking an item up if it is used over and over again - you just pass the position in, and get the node. (But what's the cost of looking up the node?)
  • The tree then has a validate() method, which turns Position objects into Node objects, so that it can manipulate the tree itself.
  • The book doesn't explicitly cover this kind of extra-layer-of-protection object model, but it is worth nothing.

Reusability and adaptability:

  • Hook methods, particular application in this case was the Euler tour and the previsit/postvisit action hooks
  • Hook methods give you a pseudo-virtual method - can be extended, not just from class to class, but from action to action

Generic types

  • Generic types for node data, extends to tree structure
  • Decide whether you want an elements-and-values based structure <E> or a key-value based structure <K,V> early