Binary Trees/LinkedBinTree - Revision history

Admin: /* Flags */

2017-06-14T03:26:54Z

Flags

← Older revision		Revision as of 03:26, 14 June 2017
Line 474:		Line 474:

	{{TreesFlag}}		{{TreesFlag}}

	~~{{DataStructuresFlag}}~~

Admin: /* Implementation */

2017-06-12T13:11:23Z

Implementation

← Older revision		Revision as of 13:11, 12 June 2017
Line 3:		Line 3:
	This page describes a [[Binary Trees]] implemented using a linked memory structure.		This page describes a [[Binary Trees]] implemented using a linked memory structure.

	==Implementation==		==Java Implementation==

	Final implementation left a large amount of the work to the final concrete class.		Final implementation left a large amount of the work to the final concrete class.
Line 439:		Line 439:
	public Iterator<E> iterator() { return new ElementIterator(); }		public Iterator<E> iterator() { return new ElementIterator(); }
	</pre>		</pre>



	==Notes==		==Notes==

Admin: /* utility methods */

2017-06-12T12:54:56Z

utility methods

← Older revision		Revision as of 12:54, 12 June 2017
Line 127:		Line 127:
	===utility methods===		===utility methods===

	The following utility methods are all ~~theoretically~~ O(1) operations:		The following utility methods are all O(1) operations:

			(see [[Trees/Operations_Performance]] for empirical verification of big-O runtime of each)

	<pre>		<pre>

Admin: /* node= */

2017-06-11T20:31:14Z

node=

← Older revision		Revision as of 20:31, 11 June 2017
Line 11:		Line 11:
	</pre>		</pre>

	===node====		===node===

	To begin with, the implementation of positions in the tree was implemented as a concrete Node class, a protected static class defined within the LinkedBinTree class and used only by it.		To begin with, the implementation of positions in the tree was implemented as a concrete Node class, a protected static class defined within the LinkedBinTree class and used only by it.

Admin: /* Linked memory structure binary tree */

2017-06-11T20:31:03Z

Linked memory structure binary tree

Show changes

Admin: /* Algorithmic Analysis */

2017-06-11T16:30:16Z

Algorithmic Analysis

← Older revision		Revision as of 16:30, 11 June 2017
Line 42:		Line 42:
	* add_root, add_left, add_right, replace, delete, attach each run in O(1) time		* add_root, add_left, add_right, replace, delete, attach each run in O(1) time

			Traversal:
			* pre and post order traversal, in-order traversal
			* theoretically will take O(N) time if we store links and O(N log N) time if we don't (worst case: have to traverse the height of the tree log(N))

	=Flags=		=Flags=

Admin: /* Notes */

2017-06-11T16:28:37Z

Notes

← Older revision		Revision as of 16:28, 11 June 2017
Line 5:		Line 5:
	==Notes==		==Notes==

	An abstraction for implementing a linked binary tree is to think about the '''positions''' (or locations in the tree) independently of the '''nodes''' (or bundles of links that represent elements). This starts to make more sense when you see ~~the~~ array implementation, but essentially we want to think of each of the '''potential''' positions of nodes in a binary tree, and number them one level at a time (1, 2 3, 4 5 6 7, etc.). This way, we have a "shadow tree" and can think about "positions" in that frame of reference.		An abstraction for implementing a linked binary tree is to think about the '''positions''' (or locations in the tree) independently of the '''nodes''' (or bundles of links that represent elements). This starts to make more sense when you see either an array-based implementation or an object-oriented abstract interface, but essentially we want to think of each of the '''potential''' positions of nodes in a binary tree, and number them one level at a time (1, 2 3, 4 5 6 7, etc.). This way, we have a "shadow tree" and can think about "positions" in that frame of reference.

			In Java, this is performed by creating a Position interface that provides a way for abstract data structures to still define useful general functionality, but leave most of the definitions to the concrete implementation. In Python, it is performed by creating an abstract class.

	Each node has pointer to left and right children, a pointer to the parent, and a pointer to the element that the node stores.		Each node has pointer to left and right children, a pointer to the parent, and a pointer to the element that the node stores.

Admin: /* Binary Tree Abstract Data Type Interface */

2017-06-11T01:54:43Z

Binary Tree Abstract Data Type Interface

← Older revision		Revision as of 01:54, 11 June 2017
Line 21:		Line 21:
	* add_left		* add_left
	* add_right		* add_right
	* replace		* set//replace
	* delete		* remove//delete
	* attach		* attach(p,t1,t2)

	These can each be implement in O(1) worst case time with a linked representation. Delete and attach are the most complicated, but still only utilize a constant number of operations.		These can each be implement in O(1) worst case time with a linked representation. Delete and attach are the most complicated, but still only utilize a constant number of operations.

Admin: /* Flags */

2017-06-07T02:26:31Z

Flags

← Older revision		Revision as of 02:26, 7 June 2017
Line 45:		Line 45:
	[[Category:Linked Lists]]		[[Category:Linked Lists]]
	[[Category:Binary Trees]]		[[Category:Binary Trees]]
			[[Category:Trees]]


	{{TreesFlag}}		{{TreesFlag}}

	{{DataStructuresFlag}}		{{DataStructuresFlag}}

Admin: /* Flags */

2017-06-07T02:26:02Z

Flags

← Older revision		Revision as of 02:26, 7 June 2017
Line 45:		Line 45:
	[[Category:Linked Lists]]		[[Category:Linked Lists]]
	[[Category:Binary Trees]]		[[Category:Binary Trees]]
	~~[[Category:Trees]]~~
			{{TreesFlag}}

	{{DataStructuresFlag}}		{{DataStructuresFlag}}