Trees/Operations Performance

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:

• 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 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.

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

Adding nodes

Removing nodes

Traversing nodes

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.