This repo contains a partial implementation of Gabow's data structure for the dynamic lowest common ancestor (LCA) problem. Specifically, it contains code for a data structure that supports
- O(1) worse-case LCA queries
- O(log n) amortized insertion of leaves
See writeup.pdf
for more details (including performance analysis).
lcaTree.hpp/cpp
: Defines the classExpensiveTreeNode
, which supports O(1) LCA queries and O(log^2 n) amortized insertion of leaveslcaMultilevel.hpp/cpp
: Defines the classMultilevelTreeNode
, which uses indirection to support O(1) LCA queries and O(log n) amortized insertion of leavesdemo.cpp
: A minimal example demonstrating how to construct a tree and run LCA queries on ittest.cpp
: Tests correctness of the LCA implementationtimingTest.cpp
: Tests efficiency of the LCA implementationgenerateRandTree.hpp/cpp
: Defines a suite of functions used to generate random trees for testing