Balanced Tree

trees

Definition

Balanced Tree

A tree is called balanced if it maintains certain defined constraints on a relative structure of its subtrees (e.g., based on height, based on weight, or other metrics). These constraints prevent the tree from becoming excessively skewed, thereby ensuring more predictable and efficient performance for specific operations compared to an unconstrained tree.

Types

Height-Balanced

Definition

Height-Balanced Tree

A tree is called height-balanced if for every tree node, the heights of its subtrees differ by at most a constant.

Link to original

Weight-Balanced

Definition

Weight-Balanced Tree

A tree is called weight-balanced if for any tree node, the number of nodes in its subtrees are within a constant factor of each other.

Link to original