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 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
TreesPart of Computer Science Notes
Series on Data Structures
Abstract data type: Trees/ADT
Preorder traversal: Trees/Preorder
Postorder traversal: Trees/Postorder
In-Order traversal: Binary Trees/Inorder
Breadth-First Search: BFS
Breadth-First Traversal: BFT
Depth-First Search: DFS
Depth-First Traversal: DFT
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT
Flags · Template:TreesFlagBase · e