Ответ
Бинарное дерево — это иерархическая структура данных, состоящая из узлов, где каждый узел имеет не более двух потомков: левого и правого.
Основные термины:
- Корень (Root): Самый верхний узел дерева, не имеющий предков.
- Потомок (Child): Узел, непосредственно связанный с другим узлом (предком) на более низком уровне.
- Предок (Parent): Узел, имеющий потомков.
- Лист (Leaf): Узел, не имеющий потомков.
- Высота (Height): Длина самого длинного пути от корня до листа.
Ключевые свойства и типы:
- Каждый узел содержит значение (ключ) и ссылки на левого и/или правого потомка.
- Бинарное дерево поиска (BST): Особый тип бинарного дерева, где для каждого узла все значения в его левом поддереве меньше значения узла, а все значения в правом поддереве — больше. Это свойство позволяет эффективно искать, вставлять и удалять элементы.
Почему используется: Бинарные деревья обеспечивают эффективные операции поиска, вставки и удаления данных, особенно в случае сбалансированных деревьев, где время выполнения этих операций составляет O(log n).
Пример структуры узла на Python:
class Node:
def __init__(self, key):
self.left = None # Ссылка на левого потомка
self.right = None # Ссылка на правого потомка
self.val = key # Значение узла
# Создание простого бинарного дерева
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7) # Добавим еще один узел для наглядностиПрименение:
- Сортировка и поиск данных: В бинарных деревьях поиска (BST) элементы хранятся в отсортированном порядке.
- Синтаксические деревья: Используются в компиляторах для представления структуры кода.
- Системы баз данных: Для индексации данных.
- Приоритетные очереди: С помощью бинарных куч (heap), которые являются частным случаем бинарного дерева.