Зачем data engineer’у деревья

После hash-таблиц деревья — следующая ключевая структура в работе data engineer’а. Их применений три:

1. Индексы в БД. B-tree и B+-tree — основная структура индекса в PostgreSQL, MySQL, Oracle. Когда вы пишете CREATE INDEX, БД строит дерево.
2. Иерархия данных. JSON, XML, HTML — деревья по природе. Catalog -> categories -> products -> variants — дерево. Аналитические OLAP-кубы хранятся как деревья.
3. Алгоритмы. Merge tree в LSM-storage (RocksDB, Cassandra), сегментное дерево, decision trees в ML, AST в парсерах.

В этом модуле начнём с базового — что такое дерево как абстрактная структура. Без этого нельзя понимать ни BST, ни B-tree, ни heap (следующий модуль), ни графы.

Дерево: формальное определение

Дерево — это связный ациклический неориентированный граф с одним выделенным узлом, называемым корнем. Если игнорировать математическое определение, проще говорить так:

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

            (1)            <- root
           /   \
         (2)   (3)
        /  \     \
      (4)  (5)   (6)
              \
              (7)          <- leaf (нет детей)

Базовая терминология

Depth vs height — самое путающее

Это две разные характеристики:

• Depth (глубина) узла — расстояние от корня до узла. У root depth = 0.
• Height (высота) узла — расстояние от узла до самого далёкого листа в его поддереве. У листа height = 0.

            (1)  depth=0, height=3
           /   \
   d=1, h=2(2)  (3) d=1, h=1
        /  \     \
 d=2,h=1(4) (5)  (6) d=2, h=0
            d=2,h=0    \
                       (7) d=3, h=0

Height всего дерева = height корня = максимальная depth среди всех узлов.

Subtree (поддерево)

Поддерево — любой узел вместе со всеми его потомками. Это рекурсивное определение, потому что любое поддерево — само по себе дерево.

поддерево от (2):
        (2)
        / \
      (4) (5)

Эта рекурсивность — главная причина, почему алгоритмы для деревьев почти всегда рекурсивные.

Tree vs Graph

Дерево — частный случай графа. Какие ограничения отличают его?

Свойство «N-1 ребро для N узлов» — простой способ проверить, что граф — дерево: если он связный и |E| == |V| - 1, то это дерево.

Представление в коде

Дерево можно представить несколькими способами. Самый простой — node-based с указателями:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []   # для общего дерева
        # или для бинарного:
        # self.left = None
        # self.right = None

# построим маленькое дерево
root = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
root.children = [n2, n3]
n2.children = [n4, n5]

Альтернатива — массив, особенно для бинарных деревьев (об этом в уроке 02 этого модуля и в модуле 11 для heap):

# полное бинарное дерево в массиве
# индекс i:
#   parent = (i - 1) // 2
#   left child = 2*i + 1
#   right child = 2*i + 2

tree = [1, 2, 3, 4, 5, 6, 7]
# это дерево:
#         1
#       /   \
#      2     3
#     / \   / \
#    4   5 6   7

Array-based представление — самое компактное по памяти, но требует, чтобы дерево было «плотно заполненным».

Размер и высота

Два главных размерных параметра:

• Число узлов N — сколько всего элементов в дереве.
• Высота h — сколько уровней.

Связь между ними зависит от формы дерева:

сбалансированное бинарное дерево с N узлами имеет h ≈ log2(N):
N=1:      h=0
N=3:      h=1
N=7:      h=2
N=15:     h=3
N=1023:   h=9
N=10^6:   h~=20

вырожденное дерево (skewed, как связный список):
        (1)
          \
          (2)
            \
            (3)
              \
              (4)
N=4, h=3, h = N - 1 — патологический случай

Это критически важно: алгоритмы дерева работают за O(h) — поэтому сбалансированное дерево даёт O(log N), а вырожденное — O(N). На разнице между этими двумя оценками строится вся теория BST и balanced trees (см. уроки 04 и 05).

Сколько узлов в дереве высоты h

Для бинарного дерева (≤ 2 ребёнка на узел):

• Минимум узлов высоты h: h+1 (если дерево — линейная цепочка)
• Максимум: 2^(h+1) - 1 (если дерево полностью заполнено)

h=0: min=1, max=1     -- single node
h=1: min=2, max=3
h=2: min=3, max=7
h=3: min=4, max=15
h=10: min=11, max=2047
h=20: min=21, max=2_097_151

Этим объясняется, почему сбалансированное бинарное дерево такое эффективное: 2^20 ≈ миллион узлов — а высота всего 20. Lookup проходит максимум 20 узлов.

Применения в DE

B-tree в PostgreSQL

Когда вы пишете CREATE INDEX ON table(column), PostgreSQL строит B-tree на этой колонке. Это не бинарное, а многоарное дерево (каждый узел имеет до сотен детей), специально оптимизированное под disk access. Высота B-tree на 100M записей — обычно 3-4 уровня. Поиск по индексу — это 3-4 disk seek.

JSON как дерево

Любой JSON — это дерево:

{
  "user": {
    "id": 1,
    "name": "Anna",
    "addresses": [
      {"city": "Moscow"},
      {"city": "SPb"}
    ]
  }
}

Полное дерево:

                (root)
                  |
                user
               /  |  \
              id name addresses
              |  |    /        \
              1 "Anna" addr[0]  addr[1]
                       |         |
                      city     city
                       |         |
                    "Moscow"   "SPb"

Парсинг JSON — это рекурсивное построение этого дерева. Сериализация — обход дерева.

Catalog -> category -> product

Любой иерархический бизнес-объект — дерево:

Catalog
├── Electronics
│   ├── Phones
│   │   ├── iPhone 15
│   │   └── Samsung Galaxy
│   └── Laptops
└── Clothing
    └── Shoes

В реляционной БД это хранится через parent_id (см. модель adjacency list). В графовой — как настоящее дерево.

Попробуй сам

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

# 1. Постройте дерево с 7 узлами и посчитайте характеристики
root = TreeNode("root")
a = TreeNode("a")
b = TreeNode("b")
c = TreeNode("c")
d = TreeNode("d")
e = TreeNode("e")
f = TreeNode("f")

root.children = [a, b]
a.children = [c, d]
b.children = [e]
e.children = [f]

#       root
#       /  \
#      a    b
#     / \    \
#    c   d    e
#              \
#               f

# 2. Подсчёт высоты — рекурсия
def height(node):
    if not node.children:
        return 0
    return 1 + max(height(c) for c in node.children)

print(f"Высота дерева: {height(root)}")   # 3

# 3. Подсчёт всех узлов
def count(node):
    return 1 + sum(count(c) for c in node.children)

print(f"Число узлов: {count(root)}")      # 7

# 4. Глубина конкретного узла
def depth(root, target, current=0):
    if root is target:
        return current
    for child in root.children:
        result = depth(child, target, current + 1)
        if result is not None:
            return result
    return None

print(f"Глубина 'f': {depth(root, f)}")   # 3

# 5. Все листья
def leaves(node):
    if not node.children:
        return [node.value]
    result = []
    for c in node.children:
        result.extend(leaves(c))
    return result

print(f"Листья: {leaves(root)}")          # ['c', 'd', 'f']

# 6. Все потомки конкретного узла
def descendants(node):
    result = []
    for c in node.children:
        result.append(c.value)
        result.extend(descendants(c))
    return result

print(f"Потомки 'a': {descendants(a)}")   # ['c', 'd']

Эти упражнения — фундамент. Все дальнейшие алгоритмы (обходы, BST, balanced trees) строятся на рекурсивном спуске по дереву.

В следующем уроке разберём бинарные деревья — особый, самый частый класс деревьев. Поймём, что значит complete, full, perfect и balanced, и почему array-layout работает только для complete.