C Academy · Урок

Поиск и освобождение

Находите узлы и освобождайте память.

Урок 4 из 413 шагов

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

Поиск в BST

Поиск использует правило упорядоченности. На каждом узле мы сравниваем искомое значение со значением узла и переходим только в одно поддерево.

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

Рекурсивный поиск

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

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

Node *search(Node *root, int target) {
    if (root == NULL || root->value == target)
        return root;
    if (target < root->value)
        return search(root->left, target);
    return search(root->right, target);
}

Итеративный поиск

Поиск также можно реализовать простым циклом, избежав накладных расходов рекурсии.

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

Node *search_iter(Node *root, int target) {
    while (root != NULL) {
        if (target == root->value) return root;
        root = (target < root->value)
             ? root->left : root->right;
    }
    return NULL;  /* not found */
}

Поиск в действии

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

Возврат не-NULL означает, что значение найдено; NULL означает, что его нет в дереве.

#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;
}
Node *search(Node *r,int t){
    if(!r||r->value==t) return r;
    return t<r->value ? search(r->left,t) : search(r->right,t);
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("7:%s 99:%s\n",
        search(root,7)?"found":"no",
        search(root,99)?"found":"no");
    return 0;
}

Поиск минимума

В BST наименьшее значение находится в самом левом узле: продолжайте переходить по left, пока не встретите NULL.

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

Node *find_min(Node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

Почему важно освобождать память

Каждый узел был получен с помощью malloc, поэтому каждый узел необходимо вернуть системе с помощью free. Если забыть вызвать free, произойдёт утечка памяти.

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

Освобождение в порядке post-order

Безопасный способ освободить дерево — использовать порядок post-order: сначала освободить обоих потомков, а затем сам узел.

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

void free_tree(Node *root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

Опасный неправильный порядок

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

Это классическая ошибка использования памяти после освобождения. Всегда сначала освобождайте потомков.

/* WRONG: use-after-free */
void bad_free(Node *root) {
    if (!root) return;
    free(root);                 /* freed here */
    bad_free(root->left);       /* reads freed memory! */
    bad_free(root->right);
}

Избегайте висячих указателей

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

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

free_tree(root);
root = NULL;   /* avoid a dangling pointer */

Подсчёт освобождённых узлов

Проверить работу освобождения можно, подсчитывая узлы во время обхода post-order, а затем освобождая каждый из них.

Эта программа строит дерево, освобождает его и сообщает, сколько узлов было освобождено.

#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 free_count(Node *r){
    if(!r) return 0;
    int c = free_count(r->left) + free_count(r->right);
    free(r);
    return c + 1;
}

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

Поиск и освобождение вместе

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

Инструменты вроде Valgrind могут подтвердить, что каждому вызову malloc соответствует вызов free.

/* lifecycle
 * 1. insert values     (allocate)
 * 2. search as needed   (read-only)
 * 3. free_tree(root)    (deallocate)
 * 4. root = NULL        (avoid dangling)
 */

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

Проанализируйте безопасное освобождение памяти.

Ответь в интерактивном уроке

Итоги

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

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

Можно начать бесплатно

Изучай C с ИИ-репетитором — бесплатно

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

Курсы: 39
Уроки: 144

Начать учиться бесплатно Посмотреть полный курс

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

Урок «Поиск и освобождение» бесплатный?

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

Чему я научусь в уроке «Поиск и освобождение»?

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

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

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

Сколько времени занимает урок «Поиск и освобождение»?

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

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

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

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

← Назад к C Academy