Trees Study Guide - Revision history

Admin: /* ADTs and Interfaces */

2017-09-04T01:02:22Z

ADTs and Interfaces

← Older revision		Revision as of 01:02, 4 September 2017
Line 64:		Line 64:

	Tree navigation and node methods:		Tree navigation and node methods:
	* ~~root - get root node~~		* getRoot(p) - gets root node of tree containing p
	* is root(p) - ~~check if this node is~~ root node		* getParent(p) - returns node that is parent of p
	* ~~parent~~(p) - ~~get~~ parent of p		* getChildren(p) - iterator over children of p
	* ~~numChildren~~(p) - ~~number of~~ children of p		* isRoot(p) - boolean, is p the root node
	* ~~children~~(p) - ~~iterator over~~ p~~'s children~~		* isLeaf(p) - boolean, is p a leaf node
	* isLeaf(p) - ~~check if node~~ is leaf		* numChildren(p) - int, number of children of p


	Tree construction methods:		Tree construction methods:

Admin: /* Definitions */

2017-09-04T00:08:32Z

Definitions

← Older revision		Revision as of 00:08, 4 September 2017
Line 40:		Line 40:

	'''full binary tree''' - same thing as proper		'''full binary tree''' - same thing as proper

			'''complete binary tree''' - (think heaps) each hierarchical level of the tree is populated completely before moving on to the next hierarchical level

	'''level numbering''' - utilized for array-based binary tree storage		'''level numbering''' - utilized for array-based binary tree storage

Admin: /* Flags */

2017-07-09T20:06:31Z

Flags

← Older revision		Revision as of 20:06, 9 July 2017
Line 380:		Line 380:
	{{StudyGuideFlag}}		{{StudyGuideFlag}}
	[[Category:Study Guide]]		[[Category:Study Guide]]

			{{TreesFlag}}

Admin: /* OOP Principles */

2017-07-09T20:06:15Z

OOP Principles

← Older revision		Revision as of 20:06, 9 July 2017
Line 357:		Line 357:

	=OOP Principles=		=OOP Principles=

			Delegating responsibility for tasks:
			* Many decisions to make about inheritance, protection, ownership of operations
			* Example: should the method for getting the left/right node be node.left? node.getLeft()? tree.left(node)?
			* When designing a data structure, have to '''think ahead''' to concrete implementations. What will you need to override, and what will stay the same?
			* Trees have a complicated potential inheritance diagram.
			** Different concrete implementations (linked vs array)
			** Different functionality (AVL vs BTree vs Red Back)
			** Further, internal classes and utilities might need to change (e.g., AVL trees keeping count)
			** Trees are used by other data structures (priority queue, set, sort, etc)
			* Nail down the scope before you start, to keep from (a) putting in way more work and formality than is required, or (b) putting together a slapdash design that has to be completely refactored
			* Seems better to build functionality into the tree - more self-contained - although if you can get away with node.left, why wouldn't you

			Adaptability and reusability:
			* Hook methods - pseudo-virtual methods
			* Template method pattern
			* Generic types for node data
			* Generic types extend from nodes to trees

	=Flags=		=Flags=

Admin: /* Complexity and Cost */

2017-07-09T20:01:44Z

Complexity and Cost

← Older revision		Revision as of 20:01, 9 July 2017
Line 337:		Line 337:
	\|add/replace/attach		\|add/replace/attach
	\|O(1) (given a position)		\|O(1) (given a position)


	\|-		\|-

Admin: /* Complexity and Cost */

2017-07-09T20:01:18Z

Complexity and Cost

← Older revision		Revision as of 20:01, 9 July 2017
Line 311:		Line 311:
	=Complexity and Cost=		=Complexity and Cost=

	{\| class="wikitable" cellpadding="100" width="66%"		{\| class="wikitable" cellpadding="100" width="33%"
	!colspan="4"\|Big-O Complexity of Lists		!colspan="4"\|Big-O Complexity of Lists
	\|-		\|-

Admin: /* Complexity and Cost */

2017-07-09T20:01:07Z

Complexity and Cost

← Older revision		Revision as of 20:01, 9 July 2017
Line 310:		Line 310:

	=Complexity and Cost=		=Complexity and Cost=

			{\| class="wikitable" cellpadding="100" width="66%"
			!colspan="4"\|Big-O Complexity of Lists
			\|-
			\|
			\|<br /><br />
			Linked Binary Tree

			\|-
			\|depth
			\|O(d)

			\|-
			\|height
			\|O(h) (O(n) worst case)

			\|-
			\|children
			\|O(c)

			\|-
			\|tree traversal, euler tour
			\|O(n)

			\|-
			\|add/replace/attach
			\|O(1) (given a position)


			\|-
			\|root/parent/child/sibling
			\|O(1) (given a position)

			\|-
			\|is root/is leaf
			\|O(1)

			\|-
			\|length
			\|O(1)

			\|-
			\|empty
			\|O(1)

			\|}

	=OOP Principles=		=OOP Principles=

Admin: /* Complexity and Cost */

2017-07-09T19:56:21Z

Complexity and Cost

@@ Line 236: / Line 236: @@
 ** pop top
 ** seek peek right to top
 =Complexity and Cost=

Admin: /* Algorithms for Operations */

2017-07-09T19:13:03Z

Algorithms for Operations

@@ Line 192: / Line 192: @@
 ** perform visit action on node
 ** add children to queue
 =Complexity and Cost=

Admin: /* Algorithms for Operations */

2017-07-09T19:07:58Z

Algorithms for Operations

← Older revision		Revision as of 19:07, 9 July 2017
Line 110:		Line 110:

	=Algorithms for Operations=		=Algorithms for Operations=

			Algorithms for tree operations:

			height(p) method:
			* if p is root:
			** return 0
			* else:
			** return 1+height(parent)

			depth(p) method:
			* if p is leaf:
			** return 0
			* else:
			** return 1+max( depth(child1), depth(child2), ... )

			clone method (public):
			* new tree
			* root = clone this root
			* return tree

			clone method (private recursive):
			* if node null:
			** return null
			* else:
			** create new Node
			** set left to clone node left
			** set right to clone node element right
			** return new node

			addRoot method:
			* deal with non empty case
			* root = new node
			* update

			addLeft or addRight method:
			* deal with non-empty case
			* left = new node or right = new node

			replace method:
			* node element =new element

			attach(p,tree1,tree2) method:
			* deal with internal node case
			* set parent of tree 1 root node to p
			* set left child of p to tree 1 root
			* set parent of tree 2 root node to p
			* set right child of p to tree 2 root
			* tree1 root = null, size = 0
			* tree2 root = null, size = 0

			delete method:
			* deal with 2 child case
			* get correct child
			* deal with root case
			* get cursed node's parent
			* update parent's left/right child to point to replacement
			* convention: node parent = node

			preorder subtree traversal:
			* perform visit action for p
			* for each child of p:
			** preorder(c)

			postorder subtree traversal:
			* for each child of p:
			** postorder(p)
			* perform visit action for p

			inorder subtree traversal:
			* if p has left:
			** inorder(left)
			* perform visit action for p
			* if p has right:
			** inorder (right)

			breadth-first traversal:
			* deal with empty case
			* create queue
			* while queue not empty:
			** pop node from queue
			** perform visit action on node
			** add children to queue

	=Complexity and Cost=		=Complexity and Cost=