Дерево как структура данных: термины, виды и обход

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

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

Дерево и граф: в чем разница

Граф — это набор вершин и связей (ребер) между ними; связи могут образовывать циклы, а у вершины может быть сколько угодно соседей. Дерево — более узкий случай: это связный граф без циклов, в котором из корня к любому узлу ведет ровно один путь.

Отсюда ключевое свойство: в дереве из N узлов ровно N минус 1 ребро, и удаление любого ребра разбивает его на две части.

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

Разберем словарь, которым дальше описывают любые деревья.

• Узел (вершина) — элемент дерева, хранит значение (ключ) и ссылки на потомков.
• Корень — единственный узел без родителя, с него начинается дерево.
• Ребро (ветвь) — связь между родителем и потомком.
• Лист — узел без потомков (конец ветви).
• Родитель и потомок — узлы на соседних уровнях, соединенные ребром: родитель выше, потомок ниже.
• Предки и потомки — все узлы вверх по пути к корню и вниз по поддереву соответственно.
• Поддерево — любой узел вместе со всеми его потомками; само по себе тоже полноценное дерево (поэтому деревья удобно описывать рекурсивно).
• Степень узла — число его прямых потомков; степень дерева — максимальная степень среди его узлов.

Высота и глубина: не путать

Эти два термина часто смешивают, хотя они измеряют разное.

Глубина узла — это длина пути от корня до этого узла. У корня глубина 0, у его прямых потомков — 1, и так далее вниз.

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

Важна оговорка о единицах: длину пути считают в ребрах или в узлах, встречаются оба соглашения. Дальше функция height считает число узлов на самом длинном пути (число уровней) и для нашего примера вернет 4; при подсчете в ребрах та же высота равна 3.

Виды деревьев

Деревья различают по степени узлов и по тому, как заполнены уровни. Ниже — ориентир по задачам, а не полный каталог.

Отдельно стоит развести два близких слова.

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

Сбалансированное дерево — у любого узла высоты левого и правого поддеревьев различаются не больше чем на заданную константу (например, на 1 в AVL). Баланс — про разницу высот, а не про порядок заполнения, поэтому сбалансированное дерево не обязано быть полным, и наоборот.

Бинарное дерево поиска

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

Соберем дерево, вставляя ключи по одному в порядке 8, 3, 10, 1, 6, 14, 4, 7, 13. Проследим первые вставки руками:

• 8 — дерево пустое, 8 становится корнем.
• 3 — меньше 8, уходит влево от корня.
• 10 — больше 8, уходит вправо.
• 1 — меньше 8 (влево), меньше 3 (влево от 3).
• 6 — меньше 8 (влево), больше 3 (вправо от 3).

Продолжив так же для 14, 4, 7 и 13, получим дерево:

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \     /
       4   7   13

Теперь тот же алгоритм в коде — полная программа, которую можно скопировать и запустить:

class Node:
    def __init__(self, key):
        self.key = key      # ключ узла
        self.left = None    # левое поддерево
        self.right = None   # правое поддерево

def insert(root, key):
    if root is None:            # дошли до пустого места - создаем узел
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)   # меньше - идем влево
    elif key > root.key:
        root.right = insert(root.right, key) # больше - идем вправо
    return root                 # равные ключи не вставляем повторно

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

root = None
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, k)

print("высота (число уровней):", height(root))
print("есть ли 7:", search(root, 7) is not None)
print("есть ли 5:", search(root, 5) is not None)

Вывод программы:

высота (число уровней): 4
есть ли 7: True
есть ли 5: False

Функция search спускается от корня и на каждом узле выбирает одну ветвь: ключ меньше — влево, больше — вправо. Поэтому число сравнений равно высоте дерева, а не числу узлов.

Важна граница применимости: выигрыш есть, только пока дерево не выродилось. Если вставлять уже отсортированные ключи (1, 2, 3, 4…), каждый новый узел уйдет вправо, дерево превратится в список, а поиск станет линейным. Чтобы держать высоту малой при любом порядке вставок, используют самобалансирующиеся деревья (AVL, красно-черные).

Обходы дерева

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

• Прямой (префиксный, pre-order): узел -> левое поддерево -> правое.
• Симметричный (инфиксный, in-order): левое поддерево -> узел -> правое.
• Обратный (постфиксный, post-order): левое поддерево -> правое -> узел.

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

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def preorder(node, acc):    # корень -> левое -> правое
    if node is None:
        return
    acc.append(node.key)
    preorder(node.left, acc)
    preorder(node.right, acc)

def inorder(node, acc):     # левое -> корень -> правое
    if node is None:
        return
    inorder(node.left, acc)
    acc.append(node.key)
    inorder(node.right, acc)

def postorder(node, acc):   # левое -> правое -> корень
    if node is None:
        return
    postorder(node.left, acc)
    postorder(node.right, acc)
    acc.append(node.key)

root = None
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, k)

pre, ino, post = [], [], []
preorder(root, pre)
inorder(root, ino)
postorder(root, post)
print("pre-order (прямой): ", pre)
print("in-order (симметричный):", ino)
print("post-order (обратный):  ", post)

Вывод программы:

pre-order (прямой):  [8, 3, 1, 6, 4, 7, 10, 14, 13]
in-order (симметричный): [1, 3, 4, 6, 7, 8, 10, 13, 14]
post-order (обратный):   [1, 4, 7, 6, 3, 13, 14, 10, 8]

Как выбрать обход под задачу: симметричный — когда нужен порядок по ключу; прямой — когда узел обрабатывают до потомков (копирование, сериализация дерева); обратный — когда после потомков (подсчет размеров поддеревьев, вычисление выражения). Есть и обход в ширину, по уровням, но он реализуется через очередь, а не рекурсией.

Выводы

• Дерево — иерархическая структура данных и частный случай графа: связный граф без циклов, где к каждому узлу ведет один путь.
• Базовый словарь: узел, корень, лист, ребро, родитель и потомок, поддерево, степень; отдельно — глубина (расстояние от корня) и высота (путь до самого дальнего листа), которые легко перепутать.
• Бинарное дерево поиска ускоряет поиск до высоты дерева, но выигрыш пропадает, если дерево выродилось в список; спасают самобалансирующиеся деревья.
• Три обхода в глубину различаются моментом обработки узла; симметричный обход BST выдает ключи по возрастанию.

Где применяется и что учить дальше

Деревья лежат в основе многих инструментов: индексы баз данных и файловых систем строятся на B-деревьях, приоритетные очереди — на куче, кодирование по методу Хаффмана — на бинарном дереве, а автодополнение — на префиксных деревьях. Понимание обходов и балансировки нужно почти в любой задаче с иерархическими данными.

Смежные темы: Массивы в программировании, Виды и характеристики алгоритмов, Иерархические базы данных.

FAQ

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

Обязательно ли у бинарного дерева ровно два потомка у каждого узла? Нет. Бинарное — значит не больше двух: у узла может быть ноль, один или два потомка. Ноль потомков — это лист.

Почему обход и поиск в деревьях часто пишут рекурсией? Потому что дерево рекурсивно по определению: каждое поддерево — тоже дерево. Рекурсивная функция обрабатывает узел и вызывает себя для левого и правого поддеревьев, что дословно повторяет структуру данных.