Понятие баланса

Дерево называется сбалансированным, если разница уровней любых двух листьев не превышает единицы.

Более жёстким определением баланса является идеально-сбалансированное дерево – дерево, у которого для каждого узла количество узлов в левом и правом поддеревьях различается не более, чем на единицу.

Когда равновероятно обращение к любой из вершин, использование сбалансированного дерева минимизирует среднюю длину пути до идентификатора. По этой причине важно научиться конструировать сбалансированные деревья.

Для изменчивых баз данных была предложена ещё одна возможность организации бинарного дерева поиска с менее строгим определением баланса – AVL-дерево (дерево, сбалансированное по высоте).