Admin at 06:51, 8 July 2017

2017-07-08T06:51:16Z

← Older revision		Revision as of 06:51, 8 July 2017
Line 27:		Line 27:
	* Generic types for node data, extends to tree structure		* 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		* Decide whether you want an elements-and-values based structure <E> or a key-value based structure <K,V> early



			[[Category:Trees]]
			[[Category:Binary Trees]]
			[[Category:OOP]]
			[[Category:Java]]

			{{TreesFlag}}

Admin at 06:50, 8 July 2017

2017-07-08T06:50:47Z

← Older revision		Revision as of 06:50, 8 July 2017
Line 26:		Line 26:
	Generic types		Generic types
	* Generic types for node data, extends to tree structure		* 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

Admin: Created page with "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 no..."

2017-07-08T06:50:15Z

Created page with "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 no..."

New page

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

Binary Trees/OOP - Revision history

Admin at 06:51, 8 July 2017

Admin at 06:50, 8 July 2017

Admin: Created page with "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 no..."