Двоичное дерево поиска: иерархическая структура — Блог
$ cat learn/02-binary-search-tree.md

Двоичное дерево поиска: иерархическая структура

Алгоритмы Binary Search Tree Дерево Структуры данных

Двоичное дерево поиска: иерархическая структура данных

История

Концепция деревьев в computer science появилась в 1950-х годах. Двоичное дерево поиска (Binary Search Tree, BST) было предложено несколькими исследователями:

  • 1962 — Роберт Уинер и Кеннет Томсон разработали ранние версии BST для языка Lisp
  • BST стало основой для многих современных структур данных: AVL-деревья, красно-черные деревья, B-деревья

Реальные примеры из жизни

Организационная структура компании

        CEO (Генеральный директор)
        /      \
    CTO       CFO
   /   \      /  \
Dev  Dev   Acc  Acc

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

Файловая система

/
├── home/
│   ├── user/
│   │   ├── documents/
│   │   │   ├── report.pdf
│   │   │   └── notes.txt
│   │   └── pictures/
│   │       └── photo.jpg
│   └── admin/
└── etc/
    └── config

Семейное древо (генеалогия)

        Бабушка Аня
        /       \
    Дедушка    Дедушка
    Вася        Коля
      |
    Папа
      |
    Я

Бинарное дерево в играх

В шахматах каждая позиция — это узел дерева:

  • Ход белых → ветвь 1
  • Ход черных → ветвь 2
  • Дерево всех возможных партий

Как это работает

Правило BST

Для каждого узла:

  • Левое поддерево содержит значения ** меньше ** текущего узла
  • Правое поддерево содержит значения ** больше ** текущего узла
        50
       /  \
     30    70
    /  \  /  \
   20 40 60  80

Проверим: для узла 30,
- 20 < 30 (левое поддерево) ✓
- 40 > 30 (правое поддерево) ✓

Поиск в BST

Ищем число 60:

Шаг 1: 50 < 60 → идем вправо
        50
       /  \
     30    70    ← идем сюда
    /  \  /  \
   20 40 60  80

Шаг 2: 70 > 60 → идем влево
        50
       /  \
     30    70
            /  \
           60   80    ← нашли!

Сравните с массивом:

  • Массив: нужно проверить до 3 элементов (в худшем случае)
  • BST: достаточно 2 сравнения!

Поиск элемента в массиве vs BST

Массив [20, 30, 40, 50, 60, 70, 80]:
Ищем 60: 20(нет) → 30(нет) → 40(нет) → 50(нет) → 60(да!) = 5 сравнений

BST:
        50
       /  \
     30    70
    /  \  /  \
   20 40 60  80

50 < 60 → вправо → 70 > 60 → влево → нашли! = 2 сравнения

Код

Структура узла

// tree_array.h
#define TREE_TYPE int

typedef struct TreeNode {
    TREE_TYPE value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

Создание узла

TreeNode* create_node(TREE_TYPE value) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Вставка в BST

TreeNode* insert(TreeNode *root, TREE_TYPE value) {
    // Базовый случай: дошли до пустого места
    if (root == NULL) {
        return create_node(value);
    }
    
    // Рекурсивный спуск
    if (value < root->value) {
        root->left = insert(root->left, value);
    } else if (value > root->value) {
        root->right = insert(root->right, value);
    }
    // Если value == root->value, ничего не делаем (дубликаты не добавляем)
    
    return root;
}

Поиск в BST

TreeNode* find(TreeNode *root, TREE_TYPE value) {
    // Базовый случай: не нашли или дошли до конца
    if (root == NULL || root->value == value) {
        return root;
    }
    
    // Рекурсивный спуск
    if (value < root->value) {
        return find(root->left, value);
    } else {
        return find(root->right, value);
    }
}

Три способа обхода дерева

// 1. Прямой обход (root → left → right)
// Используется: копирование дерева, префиксные выражения
void pre_order_traverse(TreeNode *root) {
    if (root == NULL) return;
    print("%d ", root->value);           // Посетить корень
    pre_order_traverse(root->left);     // Левое поддерево
    pre_order_traverse(root->right);   // Правое поддерево
}

// 2. Центрированный обход (left → root → right)
// Используется: сортировка элементов
void in_order_traverse(TreeNode *root) {
    if (root == NULL) return;
    in_order_traverse(root->left);      // Левое поддерево
    print("%d ", root->value);           // Посетить корень
    in_order_traverse(root->right);     // Правое поддерево
}

// 3. Обратный обход (left → right → root)
// Используется: удаление дерева, постфиксные выражения
void post_order_traverse(TreeNode *root) {
    if (root == NULL) return;
    post_order_traverse(root->left);    // Левое поддерево
    post_order_traverse(root->right);   // Правое поддерево
    print("%d ", root->value);          // Посетить корень
}

Удаление узла

Три случая при удалении:

TreeNode* delete_node(TreeNode *root, TREE_TYPE value) {
    if (root == NULL) return NULL;
    
    // Ищем узел для удаления
    if (value < root->value) {
        root->left = delete_node(root->left, value);
    } else if (value > root->value) {
        root->right = delete_node(root->right, value);
    } else {
        // Нашли узел для удаления!
        
        // Случай 1: нет детей (листок)
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        
        // Случай 2: только один ребенок
        if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        }
        if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        
        // Случай 3: два ребенка
        // Находим минимальный узел в правом поддереве
        TreeNode *temp = find_min(root->right);
        root->value = temp->value;   // Копируем значение
        root->right = delete_node(root->right, temp->value);
    }
    
    return root;
}

TreeNode* find_min(TreeNode *node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

Примеры

Телефонная книга (контакт-ключ)

        Анна
       /    \
    Alice    Мария
    /   \      \
  Alex  Bob   Петр

Ищем “Мария”:

  1. Анна < Мария → вправо
  2. Мария == Мария → нашли!

Иерархия файлов

        / (root)
       /  \
   home    etc
  /    \    /  \
user   admin config
  |
documents/
  |
  report.txt

Вычисление выражений

Выражение 3 + 4 * 2 представляется деревом:

      +
     /  \
    3    *
       /  \
      4    2

Прямой обход (префикс): + 3 * 4 2 Центрированный обход (инфикс): 3 + 4 * 2 Обратный обход (постфикс): 3 4 2 * +

Сложность операций

ОперацияСреднееХудший
ПоискO(log n)O(n)
ВставкаO(log n)O(n)
УдалениеO(log n)O(n)
ОбходO(n)O(n)

Почему O(log n)? Каждый шаг отсекает половину элементов (как в бинарном поиске).

Худший случай — отсортированные данные (деgenerate tree):

   1
    \
     2
      \
       3
        \
         4  → превращается в связанный список!

Ключевые выводы

  1. BST — иерархическая структура с эффективным поиском O(log n) в среднем

  2. Правило: левое поддерево < корень < правое поддерево

  3. Три обхода: pre-order, in-order, post-order

  4. Главная проблема — может выродиться в список при отсортированных данных

  5. Используется в: базах данных (индексы), компиляторах (синтаксические деревья), файловых системах

Что дальше?

Следующий этап — графы! Мы изучим:

  • Представление графов (матрица и список смежности)
  • Обходы BFS и DFS
  • Топологическая сортировка
← Все статьи