Неожиданное поведение кода вставки двоичного дерева поиска

Я вставляю узел в двоичное дерево поиска и столкнулся с непредвиденным поведением.

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

Это работает, значит, он успешно вставил узел в BST.

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

struct node {
    int data;
    struct node *left;
    struct node *right;

};

typedef struct node Node;


struct node *insert(Node *root, int val)
{

    if(root == NULL){
   
        struct node *root = malloc(sizeof(struct node));
        root->data   = val;
        root->left  = root->right = NULL;
        return root;
    }
   
    if(root->data < val)
        root->right = insert(root->right,val);
   
    else if(root->data > val)
        root->left = insert(root->left,val);
    
    //return root; //WHY THIS LINE IS OPTIONAL
}

int main(){
    
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 5);
    root = insert(root, 1);
}

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

John Bollinger 17.05.2022 05:17

@JohnBollinger Это работает, значит, он успешно вставляет узел в BST. Да, я также подозревал неопределенное поведение. Спасибо за подтверждение.

user3699192 17.05.2022 05:22

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

monk 17.05.2022 05:28

Откуда вы знаете, что он успешно вставляет узел? Представленная программа не производит никакого вывода. Несмотря на это, ваша реализация C может рассматривать его как эквивалент int main(void) {}.

John Bollinger 17.05.2022 05:45
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
0
4
23
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Последняя строка в insert() не обязательна, но только в том случае, если вы готовы смириться с неопределенным поведением. В вашем конкретном случае UB работает правильно, и это, безусловно, один возможность UB.

На самом деле, это одна из его наиболее коварных функций, поскольку кажущееся правильное поведение может привести к тому, что ваш код с ошибками будет выпущен для вас, бедных ничего не подозревающих пользователей :-)

Например, когда стек перемещается вверх и вниз из-за вызовов функций, может случиться так, что предыдущее значение root будет возвращено просто потому, что вы не загружаете в него новое значение. И, если новое значение такое же, как и предыдущее, уже находящееся в стеке, вполне может показаться, что оно работает.

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


Дальнейшее расширение произвольных значений, рассмотрим этот код:

#include<stdio.h>

int get42(void) { return 42; }
int getX(void) {}

int main(){
    int x = get42();
    //printf("123456789\n");
    int y = getX();
    printf("%d\n", x);
    printf("%d\n", y);
}

Имея в виду, что это UB, поэтому он может действовать по-разному для вас, для меня это дает:

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
42
42

Таким образом, несмотря на предупреждение, кажется, что оно дает то же значение, что и предыдущий вызов функции. Вы можете проверить это, раскомментировав printf() и увидев:

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
123456789
42
10

10 есть возвращаемое значение из вызова printf (он возвращает количество напечатанных символов, девять цифр и \n).

Итак, в этом случае очень похоже, что пропуск оператора return просто позволит вызывающей стороне выбрать все, что было в стеке из предыдущего вызова (или какое-то произвольное значение, если это первый вызов на этой глубине), например с:

#include<stdio.h>

int get42(void) { return 42; }
int getX(void) {}

int main(){
    int x = 42;//get42();
    //printf("123456789\n");
    int y = getX();
    printf("%d\n", x);
    printf("%d\n", y);
}

производство для меня:

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
42
-1539029341

Но, как указывалось ранее, не полагайтесь на это. Поведение может измениться, когда вы переключитесь на новый компилятор, новую версию компилятора, новую машину или даже решите скомпилировать его в субботу вместо рабочего дня :-)

Другие вопросы по теме