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://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.
Note that these measurements were run on full binary trees, so consider the inputs biased.
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.
TreesPart of Computer Science Notes
Series on Data Structures
Abstract data type: Trees/ADT
Preorder traversal: Trees/Preorder
Postorder traversal: Trees/Postorder
In-Order traversal: Binary Trees/Inorder
Breadth-First Search: BFS
Breadth-First Traversal: BFT
Depth-First Search: DFS
Depth-First Traversal: DFT
Tree operations: Trees/Operations Performance · Trees/Removal
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT
Flags · Template:TreesFlagBase · e