Деревья. Представление в памяти. Примеры использования. Бинарные деревья

Алла: Как хорошо полежать в тени! Такое раскидистое дерево!

Тимофей: Да, прямо B-дерево...

Гоша: Чего?

Тимофей: B-дерево — структура данных, которую часто применяют для хранения данных во внешней памяти. Например, на её основе реализованы индексы в базах данных.

Гоша: Индексы? Я знаю, что у элементов массива есть индексы. Это они?

Тимофей: Нет, это совсем другие индексы. Про них я расскажу чуть позже. Сначала я расскажу про структуру данных –– дерево поиска.

При помощи деревьев поиска в некоторых языках программирования реализовано множество. Существует метод сортировки, который в худшем случае имеет такую же сложность, как и сортировка слиянием, — $O(n \log n)$. Эта сортировка реализована с использованием дерева. Скоро вы узнаете, как работает этот алгоритм.

Алла: А что такое дерево поиска?

Тимофей: Перед тем как ответить на этот вопрос, разберёмся, что же вообще такое дерево.

Дерево — структура данных, которая состоит из непустого набора связанных узлов.

Узел — объект, который может содержать некоторую информацию.

Узлы ещё называют вершинами дерева или нодами. Узел дерева может ссылаться на другие узлы.

Ребро — связь между двумя вершинами.

Путь в дереве — набор вершин, в котором следующие друг за другом узлы соединены ребром.

В дереве может быть выделен главный узел — корень дерева. В этом случае дерево будет деревом с корнем.

На корень дерева ни один узел не ссылается. На схеме выше узел со значением 8 — корень дерева.

Если узел ссылается на другие узлы, то их называют потомками/детьми/дочерними узлами. Например, у вершины со значением 8 есть два дочерних узла со значениями 3 и 10. Для них же узел 8 является родительским.

Если узел не ссылается на другие узлы дерева, то он называется листом или листовой вершиной.

Высота (глубина) дерева с корнем — количество вершин в самом длинном пути от корня до листа.

Обязательное условие: в дереве не может быть циклов. Между любыми двумя вершинами в дереве существует единственный путь.

Всего в дереве с $n$ вершинами $n - 1$ ребро.

Гоша: Конечно. В каждый узел, кроме корня, входит ровно одно ребро. И одно ребро не может входить более, чем в одну вершину. Получается, рёбер на одно меньше, чем вершин.

Тимофей: Да, но это утверждение можно доказать более строго. Воспользуемся методом математической индукции.

База индукции: $n = 1$. Одна вершина, ноль рёбер. Утверждение корректно.

Шаг индукции: пусть в дереве $n + 1$ вершина. Возьмём листовую вершину. Эта вершина соединена ровно с одним ребром. Дерево без этой вершины содержит $n$ вершин. То есть по предположению индукции $n - 1$ ребро. Таким образом, исходное дерево содержит $n$ ребер. Именно это и нужно было доказать.

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

Если каждый узел в дереве имеет не более 2 потомков, такое дерево называют двоичным или бинарным.

В общем случае количество дочерних узлов в дереве может быть произвольным.

Обычно узел дерева представляют в виде класса или структуры как узел связного списка. Отличие в том, что в дереве у вершины может быть больше одного потомка. Например, в бинарном дереве — от 0 до 2.

Скопировать кодPYTHON
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right 

Тимофей: Вот что такое структура данных дерево и её частный случай — двоичное дерево. Именно двоичные деревья наиболее популярны в программировании.

Гоша: А ты что-то говорил про поиск. Как эти деревья могут помочь в поиске?