Бинарное дерево — это структура данных, состоящая из узлов, где каждый узел имеет не более двух дочерних узлов: левого и правого.
Основные понятия:
- Корень (Root): Самый верхний узел.
- Узел (Node): Базовый элемент дерева, содержит данные и ссылки на дочерние элементы.
- Родительский узел (Parent node): Узел, имеющий дочерние узлы.
- Дочерний узел (Child node): Узел под родительским узлом.
- Лист (Leaf): Узел, не имеющий дочерних узлов.
- Глубина (Depth): Расстояние от корня до узла.
- Высота (Height): Максимальная глубина от корня до самого глубокого листа.
Типы бинарных деревьев:
- Полное бинарное дерево (Full Binary Tree): Каждый узел имеет либо 0, либо 2 дочерних узла.
- Идеальное бинарное дерево (Perfect Binary Tree): Все внутренние узлы имеют ровно 2 дочерних узла, и все листовые узлы находятся на одной глубине.
- Сбалансированное бинарное дерево (Balanced Binary Tree): Разница между глубиной левого и правого поддерева для каждого узла ограничена малой константой (например, 1, как в AVL-деревьях).
Применение:
- Бинарные деревья поиска (Binary Search Trees)
- Кучи (Heaps)
- Деревья Хаффмана
- Выражения
Пример узла в Python:
python
Обход дерева (Traversal):
- Прямой обход (Pre-order): Корень -> Левое поддерево -> Правое поддерево.
- Симметричный обход (In-order): Левое поддерево -> Корень -> Правое поддерево (часто используется в BST для получения отсортированных данных).
- Обратный обход (Post-order): Левое поддерево -> Правое поддерево -> Корень.
- Обход в ширину (Level-order): По уровням, слева направо.
Сложность операций (для сбалансированных деревьев):
| Операция | Средний случай | Худший случай |
|---|
| Вставка | O(log n) | O(n) |
| Поиск | O(log n) | O(n) |
| Удаление | O(log n) | O(n) |