Trees/Operations Performance - Revision history

Admin: /* Linked binary tree */

2019-10-09T04:23:38Z

Linked binary tree

← Older revision		Revision as of 04:23, 9 October 2019
Line 6:		Line 6:

	The process of building the linked binary tree class in Java was:		The process of building the linked binary tree class in Java was:
	* Follow the [[Binary Trees]] class implementation laid out in Goodrich book, Chapter 8, Trees, in the [[Binary Trees/LinkedBinTree]] class: https://git.charlesreid1.com/cs/java/src/master/trees/LinkedBinTree.java		* Follow the [[Binary Trees]] class implementation laid out in Goodrich book, Chapter 8, Trees, in the [[Binary Trees/LinkedBinTree]] class: https://git.charlesreid1.com/cs/java/src/branch/master/trees/oop-correct-tree/LinkedBinTree.java
	* Build tests for the linked binary tree class in TreeTesting.java: https://git.charlesreid1.com/cs/java/src/master/trees/TreeTesting.java		* Build tests for the linked binary tree class in TreeTesting.java: https://git.charlesreid1.com/cs/java/src/master/trees/TreeTesting.java
	* Build timing scripts for the linked binary tree class in TreeTiming.java: https://git.charlesreid1.com/cs/java/src/master/trees/TreeTiming.java		* Build timing scripts for the linked binary tree class in TreeTiming.java: https://git.charlesreid1.com/cs/java/src/master/trees/TreeTiming.java

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

2019-10-09T03:58:32Z

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

← Older revision		Revision as of 03:58, 9 October 2019
Line 6:		Line 6:

	The process of building the linked binary tree class in Java was:		The process of building the linked binary tree class in Java was:
	* Follow the [[Binary Trees]] class implementation laid out in Goodrich book, Chapter 8, Trees, in the [[Binary Trees/LinkedBinTree]] class: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/LinkedBinTree.java		* Follow the [[Binary Trees]] class implementation laid out in Goodrich book, Chapter 8, Trees, in the [[Binary Trees/LinkedBinTree]] class: https://git.charlesreid1.com/cs/java/src/master/trees/LinkedBinTree.java
	* Build tests for the linked binary tree class in TreeTesting.java: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/TreeTesting.java		* Build tests for the linked binary tree class in TreeTesting.java: https://git.charlesreid1.com/cs/java/src/master/trees/TreeTesting.java
	* Build timing scripts for the linked binary tree class in TreeTiming.java: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/TreeTiming.java		* Build timing scripts for the linked binary tree class in TreeTiming.java: https://git.charlesreid1.com/cs/java/src/master/trees/TreeTiming.java

	The timing script was used to perform verification that the amortized cost of the add and remove operations were as expected.		The timing script was used to perform verification that the amortized cost of the add and remove operations were as expected.

Admin: /* Tree class operations */

2017-06-12T12:44:44Z

Tree class operations

← Older revision		Revision as of 12:44, 12 June 2017
Line 1:		Line 1:
	=~~Tree~~ class operations=		=Measuring tree class operations=

	This page covers performance tests of tree class operations and verification of their big-O performance.		This page covers performance tests of tree class operations and verification of their big-O performance.

	==~~LinkedBinTree~~==		==Linked binary tree==

	The process of building the linked binary tree class in Java was:		The process of building the linked binary tree class in Java was:
Line 11:		Line 11:

	The timing script was used to perform verification that the amortized cost of the add and remove operations were as expected.		The timing script was used to perform verification that the amortized cost of the add and remove operations were as expected.

			Note that these measurements were run on full binary trees, so consider the inputs biased.

	===Adding nodes===		===Adding nodes===

Admin: /* Traversing nodes */

2017-06-12T12:38:52Z

Traversing nodes

← Older revision		Revision as of 12:38, 12 June 2017
Line 24:		Line 24:
	[[Image:TreeTiming_Traverse.png\|500px]]		[[Image:TreeTiming_Traverse.png\|500px]]

			Note that these results are not saying the breadth-first traversal takes O(1) time, they are showing the per-operation cost of traversing a single node (like adding or removing a single node). This should remain O(1) cost if the overall operation of traversing the tree is to scale like O(N). If the cost of traversal scales like O(N), there is a leaky algorithm implementation and it will scale like O(N^2) when the rubber meets the road.


	=Flags=		=Flags=

Admin: /* Traversing nodes */

2017-06-12T12:36:52Z

Traversing nodes

← Older revision		Revision as of 12:36, 12 June 2017
Line 23:		Line 23:

	[[Image:TreeTiming_Traverse.png\|500px]]		[[Image:TreeTiming_Traverse.png\|500px]]




			=Flags=

			{{TreesFlag}}


			[[Category:Trees]]
			[[Category:Timing]]
			[[Category:Performance]]
			[[Category:Java]]
			[[Category:Binary Trees]]

Admin: /* Traversing nodes */

2017-06-12T12:35:57Z

Traversing nodes

← Older revision		Revision as of 12:35, 12 June 2017
Line 22:		Line 22:
	===Traversing nodes===		===Traversing nodes===

	[[~~Images~~:TreeTiming_Traverse.png\|500px]]		[[Image:TreeTiming_Traverse.png\|500px]]

Admin: /* Removing nodes */

2017-06-12T12:35:42Z

Removing nodes

← Older revision		Revision as of 12:35, 12 June 2017
Line 18:		Line 18:
	===Removing nodes===		===Removing nodes===

	[[~~Images~~:TreeTiming_Remove.png\|500px]]		[[Image:TreeTiming_Remove.png\|500px]]

	===Traversing nodes===		===Traversing nodes===

	[[Images:TreeTiming_Traverse.png\|500px]]		[[Images:TreeTiming_Traverse.png\|500px]]

Admin: /* Adding nodes */

2017-06-12T12:35:23Z

Adding nodes

← Older revision		Revision as of 12:35, 12 June 2017
Line 14:		Line 14:
	===Adding nodes===		===Adding nodes===

	[[~~Images~~:TreeTiming_Add.png\|500px]]		[[Image:TreeTiming_Add.png\|500px]]

	===Removing nodes===		===Removing nodes===

Admin at 12:34, 12 June 2017

2017-06-12T12:34:05Z

@@ Line 1: / Line 1: @@
-=Tree Operations Performance=
+=Tree class operations=
 ==LinkedBinTree==
@@ Line 9: / Line 11: @@
 The timing script was used to perform verification that the amortized cost of the add and remove operations were as expected.

Admin: Created page with "=Tree Operations Performance= ==LinkedBinTree== The process of building the linked binary tree class in Java was: * Follow the Binary Trees class implementation laid out..."

2017-06-12T12:31:27Z

Created page with "=Tree Operations Performance= ==LinkedBinTree== The process of building the linked binary tree class in Java was: * Follow the Binary Trees class implementation laid out..."

New page

=Tree Operations Performance=

==LinkedBinTree==

The process of building the linked binary tree class in Java was:
* Follow the [[Binary Trees]] class implementation laid out in Goodrich book, Chapter 8, Trees, in the [[Binary Trees/LinkedBinTree]] class: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java
* Build tests for the linked binary tree class in TreeTesting.java: https://charlesreid1.com:3000/cs/java/src/master/trees/TreeTesting.java
* Build timing scripts for the linked binary tree class in TreeTiming.java: https://charlesreid1.com:3000/cs/java/src/master/trees/TreeTiming.java

The timing script was used to perform verification that the amortized cost of the add and remove operations were as expected.