Trees - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:58:13Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:58, 9 October 2019
Line 187:		Line 187:
	Further notes from Goodrich et al, Data Structures in Python, Chapter 8 Trees.		Further notes from Goodrich et al, Data Structures in Python, Chapter 8 Trees.

	charlesreid1 git repo: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees		charlesreid1 git repo: https://git.charlesreid1.com/cs/java/src/master/trees

	We utilize the patterns that Goodrich utilized, to flex our OOP muscles, and create some interfaces and abstract classes for our Tree classes.		We utilize the patterns that Goodrich utilized, to flex our OOP muscles, and create some interfaces and abstract classes for our Tree classes.

Admin: /* Flags */

2017-09-05T09:22:13Z

Flags

← Older revision		Revision as of 09:22, 5 September 2017
Line 234:		Line 234:

	{{TreesFlag}}		{{TreesFlag}}

	~~{{DataStructuresFlag}}~~

	[[Category:Trees]]		[[Category:Trees]]

Admin: /* Algorithmic analysis */

2017-09-05T09:21:43Z

Algorithmic analysis

← Older revision		Revision as of 09:21, 5 September 2017
Line 69:		Line 69:
	===Algorithmic analysis===		===Algorithmic analysis===

	~~Analyze~~ the ~~following~~ two methods ~~to obtain~~ the height:		To analyze the calculation of the height of a tree, we will analyze two methods.

			The first calls the depth function on each leaf node, and determines the maximum result returned. This returns the total height of the tree. Using some Python-like pseudocode, we can express this using a list comprehension:

	<pre>		<pre>
Line 76:		Line 78:
	</pre>		</pre>

	This will call depth function on each tree, and the worst-case depth is n.		This will call the depth function on each tree, and the worst-case depth is n, the number of nodes in the tree.

	That means we're doing		That means we're doing

Admin: /* Algorithmic analysis */

2017-09-05T09:19:24Z

Algorithmic analysis

← Older revision		Revision as of 09:19, 5 September 2017
Line 84:		Line 84:
	</math>		</math>

	Height runs in O(n^2)		Height function runs in <math>O(n^2)</math> time

	An alternative method utilizes recursion:		An alternative method utilizes recursion:

Admin: /* Flags */

2017-09-05T08:38:20Z

Flags

← Older revision		Revision as of 08:38, 5 September 2017
Line 230:		Line 230:

	=Flags=		=Flags=

			{{TreesFlag}}

	{{DataStructuresFlag}}		{{DataStructuresFlag}}

	[[Category:Trees]]		[[Category:Trees]]

Admin: /* Implementation */

2017-06-11T20:37:31Z

Implementation

← Older revision		Revision as of 20:37, 11 June 2017
Line 184:		Line 184:

	Further notes from Goodrich et al, Data Structures in Python, Chapter 8 Trees.		Further notes from Goodrich et al, Data Structures in Python, Chapter 8 Trees.

			charlesreid1 git repo: https://charlesreid1.com:3000/cs/java/src/master/trees

	We utilize the patterns that Goodrich utilized, to flex our OOP muscles, and create some interfaces and abstract classes for our Tree classes.		We utilize the patterns that Goodrich utilized, to flex our OOP muscles, and create some interfaces and abstract classes for our Tree classes.

Admin: /* Implementation */

2017-06-10T22:47:09Z

Implementation

← Older revision		Revision as of 22:47, 10 June 2017
Line 187:		Line 187:
	We utilize the patterns that Goodrich utilized, to flex our OOP muscles, and create some interfaces and abstract classes for our Tree classes.		We utilize the patterns that Goodrich utilized, to flex our OOP muscles, and create some interfaces and abstract classes for our Tree classes.

	The ~~inheritance diagram is~~:		The interfaces defined are:
	* Tree - top level interface, defines abstract methods that all trees should implement		* Tree (abstract) - see [[Trees/ADT]] - top level interface, defines abstract methods that all trees should implement
	* BinaryTree - inherits from Tree, creates more abstract methods that the tree should implement		* BinaryTree (abstract) - see [[Binary Trees/ADT]] - inherits from Tree ADT, creates more abstract methods that the tree should implement
	* ~~LinkedBinaryTree~~ - linked memory structure for our binary tree, implements the interfaces and methods above in a concrete way
			Abstract classes are:
			* Abstract Tree ("concrete" implementations of a few methods) - see [[Trees/ADT#Concrete ]]
			* Abstract Binary Tree (more "concrete" implementations of whatever is possible) - see [[Binary Trees/ADT]]

			Concrete classes:
			* Linked Binary Tree - linked memory structure for our binary tree, implements the interfaces and methods above in a concrete way - see [[Binary Trees/LinkedBinTree]]
			* Array Binary Tree - array-based storage for binary tree - see [[Binary Trees/ArrayBinTree]]

	When we write a class that implements these methods for a particular data structure, we call it a concrete class.		When we write a class that implements these methods for a particular data structure, we call it a concrete class.

Admin: /* Trees in the wild */

2017-06-10T22:00:39Z

Trees in the wild

← Older revision		Revision as of 22:00, 10 June 2017
Line 199:		Line 199:

	Some places where you can spot trees in the wild:		Some places where you can spot trees in the wild:

			==Open source software==

	Binary Tree Map implementation in Apache Ignite: https://github.com/apache/ignite/blob/cc6257f8c53da5f6da32b0f184065c1e35a75acf/modules/core/src/main/java/org/apache/ignite/internal/binary/BinaryTreeMap.java		Binary Tree Map implementation in Apache Ignite: https://github.com/apache/ignite/blob/cc6257f8c53da5f6da32b0f184065c1e35a75acf/modules/core/src/main/java/org/apache/ignite/internal/binary/BinaryTreeMap.java
Line 210:		Line 212:
	(UIMA = Unstructured Information Management Applications, woo, https://uima.apache.org/)		(UIMA = Unstructured Information Management Applications, woo, https://uima.apache.org/)

			==Java implementations==

			tree algos: https://github.com/ignl/BinarySearchTrees/tree/master/Trees/src/main/java/org/intelligentjava/algos/trees

			very extensive abstract binary search tree: https://github.com/ignl/BinarySearchTrees/blob/master/Trees/src/main/java/org/intelligentjava/algos/trees/AbstractBinarySearchTree.java

			red black tree: https://github.com/ignl/BinarySearchTrees/blob/master/Trees/src/main/java/org/intelligentjava/algos/trees/RedBlackTree.java

	=Flags=		=Flags=

Admin: /* Flags */

2017-06-10T21:54:37Z

Flags

← Older revision		Revision as of 21:54, 10 June 2017
Line 195:		Line 195:

	Example of concrete tree implementation: [[Binary Trees/LinkedBinTree]]		Example of concrete tree implementation: [[Binary Trees/LinkedBinTree]]

			=Trees in the wild=

			Some places where you can spot trees in the wild:

			Binary Tree Map implementation in Apache Ignite: https://github.com/apache/ignite/blob/cc6257f8c53da5f6da32b0f184065c1e35a75acf/modules/core/src/main/java/org/apache/ignite/internal/binary/BinaryTreeMap.java

			Apache Ignite: open-source in-memory computing platform "for computing and transacting on large-scale data sets in real-time, orders of magnitude faster than possible with traditional disk-based or flash technologies." https://ignite.apache.org/



			Binary Tree and Red Black Tree implementations in Apache Uima: https://github.com/apache/uima-uimaj/blob/40c4aefb9c7e7cd0234e6bbc76e8f960ec8d7e7d/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/RedBlackTree.java

			(UIMA = Unstructured Information Management Applications, woo, https://uima.apache.org/)



	=Flags=		=Flags=

Admin: /* Tree implementation details */

2017-06-07T05:32:16Z

Tree implementation details

← Older revision		Revision as of 05:32, 7 June 2017
Line 49:		Line 49:

	Abstract class:		Abstract class:
	* Tree is an example of an abstract class implementation		* Tree is an example of an abstract class implementation - see also [[Abstract Data Types]]
	* In Python, each virtual function will raise a NotImplementedError("Must be implemented by subclass")		* In Python, each virtual function will raise a NotImplementedError("Must be implemented by subclass")
	* In Python, errors in arguments pointing to invalid positions should raise a ValueError		* In Python, errors in arguments pointing to invalid positions should raise a ValueError