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

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

Ключевые свойства:

• Каждый узел содержит значение (ключ) и ссылки на левого/правого потомка.
• Левое поддерево узла содержит значения меньше, правое — больше (для бинарного дерева поиска, BST).

Пример на 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)

Применение: сортировка, поиск, синтаксические деревья. Время поиска в сбалансированном BST — O(log n), в вырожденном (списке) — O(n).