AVL/Binary Search Tree

Question

У меня есть вопрос программирования C. Ниже приведена вставка в узел с ключом.

Я не понимаю, почему node->left = insert(node->left,key)

Я предполагаю, что этот код будет обновлять node->left с чем?

Не звонит ли он insert()? Это похоже на повторение одной и той же функции снова и снова - это не бесконечный цикл или вставка?

Я проверил несколько примеров, все они обновляют node->left таким образом, снова вызвав ту же функцию? Скажем, я неправильно понял, что в нем хранится? Указатель? Или они просто магически связаны?

// An AVL tree node 
struct node 
{ 
    int key; 
    struct node *left; 
    struct node *right; 
    int height; 
}; 

struct node* insert(struct node* node, int key) 
{ 
    /* 1. Perform the normal BST rotation */ 
    if (node == NULL) 
     return(newNode(key)); 

    if (key < node->key) 
     node->left = insert(node->left, key);//This just called Insert function again? 
    else 
     node->right = insert(node->right, key); 

Answer 1

Да, они называют функцию insert снова, но учтите, что аргументы изменились . Это то, что называется recursion.

Также обратите внимание, что он не всегда повторяет ту же функцию: в случае node==NULL это не называется. Так что это не бесконечно; как вы принимаете node->left, node->left->left, и поэтому один, вы однажды достигли точки, где указатель NULL.

---

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