Menu
I was having a look at this question and then reading about Tarjan's least common ancestors algorithm. I never came across any applications of LCA algorithms before.
Where are such LCA algorithms commonly used?
578
Application of Lowest Common Ancestor(LCA):To determine the distance between pairs of nodes in a tree: the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor.
The Lowest Common Ancestor (LCA) of two nodes and in a rooted tree is the lowest (deepest) node that is an ancestor of both and . Remember that an ancestor of a node in a rooted tree is any node that lies on the path from the root to (including ).
In compilers, the LCA of two basic blocks is a place you can put a computation so it is available to both. This might be useful for eliminating common subexpressions, or inserting phi-node for SSA conversion. These algorithms are well evolved and highly optimized, though, so the LCA itself may be hard to see, e.g., SSA and PRE
62
Don't know where it is used, but I have a couple ideas where it might get used:
computer graphics: often 3D sceneries get split into cubes which form a tree structure. If you have an object which is contained in two such cubes a LCA algorithm gives you the smallest containing larger cube.
analysis of gens in order to find the relationships between species and their lowest common ancestor
merge algorithms of version control systems
5
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
