AVL/二叉搜索树

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.

的点

¹ 我并不是说递归调用必须总是改变它的参数，但这是最常见的方法。

AVL/二叉搜索树

AVL / Binary Search Tree

c

algorithm

binary-tree

avl-tree