balance factor
For a tree node, the height of its left subtree minus the height of its right subtree.
In more detail
An AVL tree requires every node's balance factor to be -1, 0 or +1. A value of +2 or -2 after an insert means that node is out of balance and a rotation is needed. Nodes store their heights so balance factors can be computed in O(1).
Related terms
- AVL tree — A self-balancing binary search tree in which the heights of every node's two subtrees differ by at most one.
- rotation — A small local rearrangement of a search tree that lifts a child above its parent while keeping the keys in order.
Taught in
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers