This project is developed using Visual Studio 2019. Google Test including Google Mock is used as a testing framework. Thus to run the project Google Test and Google Mock need to be installed. The easiest way is to install a gmock NuGet package. The project can also be successfully ran in Visual Studio 2017. However, it might be necessary to change a platform toolset to one of VS2017 as well as to retarget solution.
In this part a simple binary search tree class is implemented that supports an LCA query.
LCA is defined as follow: For nodes u and v of tree T , query lca(u, v) returns the lowest common ancestor of u and v in T, that is, it returns the node farthest from the root that is an ancestor of both u and v, where node is also defined to be an ancestor of itself, i.e. lca(u,u) = u.
Definition is taken from Bender et al. (2005) "Lowest common ancestors in trees and directed acyclic graphs".
Quick links:
In this part, functionality of LCA query is extended to support DAGs.
LCA for DAGs is defines as follows: An LCA w of nodes u and v in a DAG is an ancestor of both u and v where w has no descendants that are also ancestors of both u and v. Note: assume lca(x,x) = x, i.e. lca is reflexive.
As for part 1, definition is taken from Bender et al. (2005) "Lowest common ancestors in trees and directed acyclic graphs".
Quick links:
Subject: Howard G. "Ward" Cunningham.
Development branch: feature--biography-essay.
Quick links:
Development branch: feature--measuring-engineering-report.
Commit identifying current most-up-date submission: 98c95664b0c29dc6bdbf69b64ca074d08e93060a
Release/Tag identifying most-up-date submission: v4.0
Quick links: