Структура дерева

Дерево — этонелинейнаяструктура данных, которая имитирует ветвящуюся иерархию деревьев в природе. В отличие от линейных структур, таких как массивы и связанные списки, где элементы расположены один за другим, элементы данных в дереве (называемыеузел) между ними существует чёткая иерархическая связь «один ко многим».

Структура дереваСовсем как настоящее дерево:

  • корневой узел: корневая часть дерева, единственный узел без родительского узла
  • дочерний узел: узлы, ответвляющиеся от узла
  • листовой узел: узел без дочерних узлов, как лист
  • путь: маршрут от одного узла к другому узлу
  • глубина: длина пути от корневого узла до этого узла
  • высота: длина пути от этого узла до самого дальнего листового узла

Аналогия из жизни:

  • семейное дерево: бабушки и дедушки → родители → дети → внуки
  • организационная структура: CEO → директор → менеджер → сотрудник
  • файловая система: корневой каталог → подкаталог → файл
  • классификация книг: общая категория → подкатегория → конкретная книга
тип структуры эффективность поиска эффективность вставки эффективность удаления упорядоченность
array O(n) O(n) O(n) Отсутствует
Связный список O(n) O(1) O(1) Отсутствует
Хеш-таблица O(1) O(1) O(1) Отсутствует
двоичное дерево поиска O(log n) O(log n) O(log n) Да

Основные термины

Прежде чем углубляться, давайте сначала познакомимся с базовой терминологией деревьев:

  • Узел: каждый элемент в дереве. Он содержит хранимые данные и ссылки на свои дочерние узлы.
  • Корневой узел: узел на вершине дерева, начальная точка всего дерева. У дерева ровно один корневой узел.
  • Родительский узел и дочерний узел (Parent & Child): Если узел A соединён с узлом B под ним, то A — этородительский узелдля B, B — этодочерний узелдля A. Родительский узел может иметь несколько дочерних узлов.
  • Братские узлы (Siblings): узлы, имеющие один и тот же родительский узел, являются братскими.
  • Листовой узел (Leaf): узел без дочерних узлов, также называется терминальным узлом.
  • Ребро: линия, соединяющая два узла и представляющая связь между ними.
  • Путь: последовательность узлов, проходимых от корневого узла до конкретного узла.
  • Высота: на самом длинном пути от узла до самого дальнего листового узла — этоколичество рёбер. Высота дерева — это высота корневого узла.
  • Глубина: на пути от корневого узла до конкретного узла — этоколичество рёбер. Глубина корневого узла равна 0.
  • Уровень: все узлы с одинаковой глубиной принадлежат одному уровню. Корневой узел находится на уровне 0.

Основные свойства деревьев

  1. единственный путь: между любыми двумя узлами дерева существует ровно один путь.
  2. N узлов, N-1 рёбер: дерево с N узлами имеет всего N-1 рёбер.
  3. ацикличность: в дереве нет циклов (то есть, начав с узла и следуя по рёбрам, вы не можете вернуться в этот узел).

Зачем нужны деревья? — Преимущества и применения деревьев

Вы можете спросить: если есть массивы и связные списки, зачем нам всё ещё нужны деревья? Ответ кроется в эффективности.

  • массив: быстрый поиск (по индексу), но медленные вставка и удаление (требуется перемещение многих элементов).
  • Связный список: быстрые вставка и удаление, но медленный поиск (требуется пройти с начала).
  • Деревья (особенно двоичные деревья поиска): сохраняя данные упорядоченными, они могут обеспечить гораздо более высокую скорость поиска, чем связные списки, и более эффективные операции вставки/удаления, чем массивы.

Практические сценарии применения:

  • файловая система: папки и файлы в компьютерах организованы в виде дерева.
  • индекс базы данных: B-дерево и B+ дерево — ключевые структуры данных для эффективных запросов в базах данных.
  • организационная диаграмма: иерархическое управление компанией или отделом.
  • дерево решений: модели классификации в искусственном интеллекте и машинном обучении.
  • HTML DOM: объектная модель документа веб-страницы представляет собой дерево.

Двоичное дерево: самый важный представитель семейства деревьев

Двоичное дерево — это дерево, в котором каждый узел имеет не более двух дочерних узлов. Эти два дочерних узла обычно называютлевым дочерним узломиправым дочерним узлом, это основа многих мощных древовидных структур (таких как двоичные деревья поиска, кучи и AVL-деревья).

Базовая структура выглядит следующим образом:

Основные термины для двоичных деревьев

Термин определение Аналогия из жизни
узел базовая единица, содержащая данные и указатели Человек в семье
корневой узел Верхний узел дерева Предок в семействе
родительский узел Узел с дочерними узлами родители
дочерний узел узел, на который указывает его родительский узел children
сестринский узел дочерние узлы одного родителя сестринские узлы
листовой узел узел без дочерних узлов человек в семье без детей
depth количество рёбер от корня до этого узла количество поколений
height количество рёбер от этого узла до самого дальнего листового узла количество поколений, в течение которых продолжается семья

тип двоичного дерева

Type Особенности Временная сложность сценарии применения
обычное двоичное дерево каждый узел имеет не более 2 дочерних узлов O(n) дерево выражений
полное двоичное дерево каждый узел имеет либо 0, либо 2 дочерних узла O(n) Кодирование Хаффмана
полное двоичное дерево все уровни, кроме последнего, заполнены O(n) реализация кучи
двоичное дерево поиска левый < корень < правый В среднем O(log n) Поиск, сортировка
сбалансированное двоичное дерево разница высот между левым и правым поддеревьями ≤ 1 O(log n) индекс базы данных
красно-чёрное дерево Цветное сбалансированное дерево O(log n) ядро Linux

Операции с двоичным деревом поиска

Действие Описание Временная сложность
Поиск Поиск узла по значению в среднем O(log n), в худшем случае O(n)
Вставка вставка нового узла в среднем O(log n), в худшем случае O(n)
Delete Удаление указанного узла в среднем O(log n), в худшем случае O(n)
обход Посещение всех узлов O(n)

Обход двоичного дерева

Обход означает посещение каждого узла дерева по некоторому правилу, при этом каждый узел посещается только один раз. Это основа алгоритмов, связанных с деревьями. Выделяют в основном четыре способа:

  1. Прямой обход:Корень -> Левый -> Правый

    • Сначала посещается корневой узел, затем рекурсивно выполняется прямой обход левого поддерева и, наконец, рекурсивно выполняется прямой обход правого поддерева.
    • Применение: Копирование дерева, получение префиксного выражения.
  2. Симметричный обход:Левый -> Корень -> Правый

    • Сначала рекурсивно обойдите левое поддерево в симметричном порядке, затем посетите корневой узел и, наконец, рекурсивно обойдите правое поддерево в симметричном порядке.
    • Применение: вдвоичном дереве поиска. В нём симметричный обход будетв порядке возрастаниявыводить все значения.
  3. Обратный обход:Левый -> Правый -> Корень

    • Сначала рекурсивно обойдите левое поддерево в обратном порядке, затем рекурсивно обойдите правое поддерево в обратном порядке и, наконец, посетите корневой узел.
    • Применение: удаление дерева, вычисление размера каталога.
  4. Обход по уровням:По уровням, слева направо

    • Начиная с корневого узла, посещайте узлы уровень за уровнем.
    • Применение: обработка данных по уровням (например, печать организационной диаграммы).Обычно реализуется с помощью очереди (Queue).。

Пример: для приведённого ниже двоичного дерева результаты обхода следующие:

        1
       / \
      2   3
     / \   \
    4   5   6
  • прямой обход:1, 2, 4, 5, 3, 6
  • симметричный обход:4, 2, 5, 1, 3, 6
  • обратный обход:4, 5, 2, 6, 3, 1
  • обход по уровням:1, 2, 3, 4, 5, 6

Практика: реализация бинарного дерева на Python

Хватит теории, давайте напишем код! Мы реализуем простой класс узла бинарного дерева и выполним операции вставки и обхода.

Шаг 1: Определите класс узла

Каждый узел должен хранить данные и указывать на свои левый и правый дочерние узлы.

Пример

class TreeNode:
    """Класс узла бинарного дерева"""
    def __init__(self, value):
        self.value = value  # Данные, хранящиеся в узле
        self.left = None    # Указывает на левый дочерний узел
        self.right = None   # Указывает на правый дочерний узел

    def __str__(self):
        """Удобно для вывода информации об узле"""
        return f"Node({self.value})"

Шаг 2: Построение примера дерева

Давайте вручную построим дерево из диаграммы предыдущего примера.

Пример

# Создать узел
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)

# Построение связей (Links)
root.left = node2
root.left = node3
node2.left⟦⟧node4 = node4
node2.right = node5
node3.right⟦⟧node6 = node6

print(f"Корневой узел: {root}")
print(f"Левый дочерний узел корневого узла: {root.left}")
print(f"Правый дочерний узел корневого узла: {root.right}")

Шаг 3: Реализация алгоритмов обхода (рекурсивная версия)

Рекурсия — самый интуитивный способ реализации обхода дерева.

Пример

def preorder_traversal(node):
    """Прямой обход: корень -> левый -> правый"""
    if node is None:
        return
    print(node.value, end=' ')  # 1. Посетить корневой узел
    preorder_traversal(node.left)   # 2. Обойти левое поддерево
    preorder_traversal(node.right)  # 3. Обойти правое поддерево

def inorder_traversal(node):
    """Симметричный обход: левый -> корень -> правый"""
    if node is None:
        return
    inorder_traversal(node.left)    # 1. Обойти левое поддерево
    print(node.value, end=' ')  # 2. Посетить корневой узел
    inorder_traversal(node.right)   # 3. Обойти правое поддерево

def postorder_traversal(node):
    """Обратный обход: левый -> правый -> корень"""
    if node is None:
        return
    postorder_traversal(node.left)  # 1. Обойти левое поддерево
    postorder_traversal(node.right) # 2. Обойти правое поддерево
    print(node.value, end=' ')  # 3. Посетить корневой узел

print("\n--- Демонстрация обхода ---")
print("Результат прямого обхода:", end=' ')
preorder_traversal(root) # Вывод: 1 2 4 5 3 6

print("\nРезультат симметричного обхода:", end=' ')
inorder_traversal(root)  # Вывод: 4 2 5 1 3 6

print("\nРезультат обратного обхода:", end=' ')
postorder_traversal(root) # Вывод: 4 5 2 6 3 1

Шаг 4: Реализуйте обход по уровням (с использованием очереди)

Обход по уровням должен использовать свойство очереди "первым пришёл — первым вышел".

Пример

from collections import deque

def level_order_traversal(root):
    """Обход по уровням: использование очереди"""
    if root is None:
        return

    queue = deque([root]) # Инициализировать очередь и добавить корневой узел в очередь

    while queue:
        current_node = queue.popleft() # 1. Извлечь узел из левого конца очереди
        print(current_node.value, end=' ') # 2. Посетить этот узел

        # 3. Добавить дочерние узлы этого узла (если есть) в правую часть очереди по порядку
        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)

print("\nРезультат обхода по уровням:", end=' ')
level_order_traversal(root) # Вывод: 1 2 3 4 5 6

Практика и испытание

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

Упражнение 1: Вычислить высоту дерева

Написать функциюtree_height(node), принимает корневой узел дерева и возвращает высоту дерева (по соглашению высота пустого дерева равна -1 или 0; в этом примере мы определяем её как количество рёбер).

Подсказка: высота дерева = 1 + max(высота левого поддерева, высота правого поддерева). Это классическая рекурсивная задача.

Упражнение 2: Поиск значения в бинарном дереве

Написать функциюsearch_in_tree(node, target_value), в заданном бинарном дереве найдите, есть ли значение, равноеtarget_valueузлу. Если найдено, вернитеTrue, иначе returnFalse。

Подсказка: можно использовать любой метод обхода и сравнивать значение каждого узла при его посещении.

Испытание: бинарное дерево поиска (BST)

Это классический вариант бинарного дерева. В бинарном дереве поиска для любого узла:

  • еголевое поддеревозначения всех узлов в<Значение этого узла.
  • егоправое поддеревозначения всех узлов в>Значение этого узла.

Ваша задача:

  1. Реализацияinsert_into_bst(root, value)функция, вставляющая значение в правильную позицию в двоичном дереве поиска.
  2. Реализацияsearch_in_bst(root, value)функция, которая использует свойства BST для эффективного поиска (средняя временная сложность O(log N)).
Другие расширения