0Pricing
C Academy · Урок

Вставка в BST

Создайте двоичное дерево поиска.

«Вставка в BST» — бесплатный урок C Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

Правило упорядочивания BST

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

Именно такой порядок позволяет выполнять поиск, вставку и удаление за время, пропорциональное высоте дерева.

Где должно находиться значение

Чтобы выполнить вставку, мы начинаем с корня и сравниваем значения. Если новое значение меньше, переходим влево, если больше — вправо.

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

/* insert 7 into:
 *        10
 *       /  \
 *      5    15
 * 7 < 10 -> left;  7 > 5 -> right of 5
 */

Вспомогательная функция create_node

При вставке создаются новые листья, поэтому мы повторно используем конструктор, который выделяет память и инициализирует узел.

Оба указателя на потомков изначально равны NULL, поскольку только что вставленный узел всегда является листом.

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) return NULL;
    n->value = value;
    n->left = n->right = NULL;
    return n;
}

Рекурсивная вставка

Самый простой способ вставки — рекурсивный: функция возвращает корень поддерева, возможно новый.

Если поддерево пусто, мы возвращаем новый узел. В противном случае рекурсивно переходим влево или вправо, заново присоединяем результат, а затем возвращаем неизменённый корень.

Node *insert(Node *root, int 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);
    return root;  /* equal: ignore duplicate */
}

Зачем возвращать корень

Возврат корня поддерева позволяет родительскому узлу одной строкой восстановить связь: root->left = insert(root->left, v).

Если поддерево было пустым, возвращённый новый узел становится потомком. Если оно было непустым, возвращается тот же корень, и связь не изменяется.

/* The assignment does double duty:
 * - empty case: stores the new node
 * - non-empty:  stores the same pointer back (no-op)
 */
root->left = insert(root->left, value);

Обработка дубликатов

В настоящих BST нужно решить, что делать с одинаковыми значениями. Распространённый вариант — игнорировать дубликаты, как это делает наша функция insert, не имеющая отдельной ветви для равного значения.

Другие варианты — хранить счётчик в каждом узле или всегда направлять дубликаты в одну сторону.

if (value < root->value)
    root->left = insert(root->left, value);
else if (value > root->value)
    root->right = insert(root->right, value);
/* value == root->value -> do nothing */

Создание BST

Вставка последовательности значений создаёт дерево, форма которого зависит от порядка вставки.

Здесь мы вставляем несколько чисел и выводим непосредственных потомков корня, чтобы подтвердить соблюдение правила упорядочивания.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return create_node(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}

int main(void){
    Node *root = NULL;
    int data[] = {10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,data[i]);
    printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
    return 0;
}

Итеративная вставка

Вставлять элементы можно и без рекурсии. Мы спускаемся по дереву с помощью указателя, запоминая родителя, пока не найдём пустое место.

Затем присоединяем новый узел к правильной стороне этого родителя.

void insert_iter(Node **rootp, int value) {
    Node *cur = *rootp, *parent = NULL;
    while (cur) {
        parent = cur;
        cur = (value < cur->value) ? cur->left : cur->right;
    }
    Node *n = create_node(value);
    if (!parent) *rootp = n;
    else if (value < parent->value) parent->left = n;
    else parent->right = n;
}

Порядок вставки формирует дерево

Вставка 1,2,3,4,5 в отсортированном порядке создаёт вырожденное дерево, похожее на связный список, с высотой, равной количеству узлов.

Вставка в сбалансированном порядке сохраняет высоту близкой к log(n). Баланс напрямую влияет на скорость поиска.

/* sorted insert 1..5 ->
 * 1
 *  \
 *   2
 *    \
 *     3   (height = 4, like a list)
 */

Стоимость вставки

Каждая вставка проходит по одному пути от корня к листу, поэтому выполняет работу, пропорциональную высоте дерева.

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

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

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

Дубликат 10 не увеличивает счётчик, потому что insert отбрасывает равные значения.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,10,20};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("count=%d\n", count(root));
    return 0;
}

Быстрая проверка

Проанализируйте поведение при вставке.

Итоги

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

Рекурсивная форма возвращает корень поддерева, чтобы родитель мог корректно восстановить связи. Стоимость вставки зависит от высоты дерева, поэтому порядок вставки имеет значение.

Часто задаваемые вопросы

Урок «Вставка в BST» бесплатный?

Да — полный текст урока «Вставка в BST» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Вставка в BST»?

Создайте двоичное дерево поиска. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Вставка в BST»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Узлы и структура дерева
  2. Вставка в BST
  3. Обходы
  4. Поиск и освобождение
← Назад к C Academy