Бинарное дерево
Бинарное дерево это направленый граф, являющийся деревом, у каждой вершины которого исходящая степень меньше либо равна 2, а входящая степень равна 1. Исключением
является одна вершина корень дерева, входящая степень которой равна 0.
Входящая (исходящая) степень вершины есть это число входящих (исходящийх) в нее ребер.
На бинарном дереве основаны структуры данных
BinaryHeap,
BinarySearchTree.
Бинарное дерево называется сбалансированным,
если у любой вершины с исходящей степенью 1 исходящая степень ребенка равна 0.
В частности, если в структуре
BinaryHeap используется именно сбалансированное бинарное дерево.
Вообще говоря, существует несколько
неэквивалентных определений понятия сбалансированного дерево.
Суть сбалансированности в том, что на дерево накладывается такое условие, которое гарантирует,
что число вершин в граые растёт экспонециально с
высотой дерева.