An Algebraic Perspective on Tree Imbalance Metrics

This paper provides an algebraic perspective on existing tree imbalance metrics, aiming to bridge the gap between algebraic theory and practical applications in computer science. We demonstrate that many popular tree imbalance metrics can be interpreted through the lens of group theory, particularly through the action of symmetric groups on tree structures. We explore two algebraic methods for quantifying tree imbalance: one based on subtree attributes and their permutations, and the other utilizing the orbit-stabilizer theorem to measure structural asymmetry. By comparing these methods with traditional metrics, we highlight their advantages and demonstrate their efficacy through examples and empirical evaluations. Our results show that these algebraic methods not only align well with established metrics for binary trees but also offer a more comprehensive measure of imbalance for non-binary trees. This work contributes to the theoretical foundation of tree imbalance metrics and offers new tools for analyzing and optimizing tree-based algorithms and data structures.