Что такое бинарное дерево?

Бинарное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух потомков: левого и правого.

Основные свойства:

• Корень (Root): Самый верхний узел дерева.
• Узел (Node): Элемент дерева, содержащий данные и ссылки на потомков.
• Потомок (Child): Узел, находящийся непосредственно под другим узлом (родительским).
• Родитель (Parent): Узел, имеющий непосредственно ниже себя одного или нескольких потомков.
• Лист (Leaf): Узел, не имеющий потомков.
• Ветвь (Branch): Путь от корня до листа.
• Поддерево (Subtree): Дерево, состоящее из узла и всех его потомков.

Различные виды бинарных деревьев:

• Полное бинарное дерево (Full Binary Tree): Каждый узел имеет либо 0, либо 2 потомка.
• Идеально сбалансированное (совершенное) бинарное дерево (Perfect Binary Tree): Все уровни, кроме последнего, полностью заполнены, и на последнем уровне все узлы расположены как можно левее.
• Сбалансированное бинарное дерево (Balanced Binary Tree): Высота левого и правого поддеревьев любого узла различается не более чем на 1. Пример: AVL-дерево, красно-черное дерево.
• Вырожденное (вытянутое) бинарное дерево (Degenerate Binary Tree): Каждый узел имеет не более одного потомка. По сути, это связанный список.

Применяется в различных алгоритмах и структурах данных, таких как бинарные деревья поиска, кучи, синтаксические деревья.