From charlesreid1

(Tree class operations)
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com)
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.

Revision as of 03:58, 9 October 2019

Measuring tree class operations

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

Linked binary tree

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

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

TreeTiming Add.png

Removing nodes

TreeTiming Remove.png

Traversing nodes

TreeTiming Traverse.png

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