Java icon indicating copy to clipboard operation
Java copied to clipboard

Feature/centroid decomposition

Open lens161 opened this issue 2 weeks ago • 2 comments

  • [ x] I have read CONTRIBUTING.md.
  • [ x] This pull request is all my own work -- I have not plagiarized it.
  • [ x] All filenames are in PascalCase.
  • [x ] All functions and variable names follow Java naming conventions.
  • [ x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
  • [ x] All new code is formatted with clang-format -i --style=file path/to/your/file.java

Summary: This PR adds an implementation of centroid decomposition for trees. The algorithm recursively finds centroids of subtrees and builds a centroid tree with height O(log n). This structure is useful for answering distance, nearest node, and other divide and conquer tree queries.

Details:

Supports adding edges to an undirected tree

Builds the centroid decomposition via build()

Provides access to centroid parents and children

Includes a helper to iterate over centroid ancestors

Tests cover subtree sizes, parent relationships, children, reset behaviour, and consistency

lens161 avatar Nov 21 '25 11:11 lens161