= Subtree-size balance
{title2=$\bigl||T.left|-|T.right|\bigr|\leq1$}
= Nearly balanced binary tree
{synonym}
The condition that each binary-tree vertex has child <subtrees> whose node counts differ by at most one. Recursively choosing the middle entry of an index interval establishes this condition at every vertex, with exactly one allocated node per entry. No ordering assumption on the stored values is needed for the balance property or for reproducing the input's inorder <sequence>.
Back to article page
