c - 在 O(1) 时间内找到 BST 大小 C

Question

我有两个问题。这两个函数当前的运行时间是多少？如果不是 O(1) (对我来说似乎是 O(n))，有人可以给我一个提示(而不是给我答案)如何将其变成 O(1) 吗？谢谢

static int size(NODE *r)
{
    if(r==NULL) 
        return 0;

    return size(r->left) + size(r->right) + 1;
}


int bst_size(BST_PTR t)
{
    return size(t->root);
}

Answer 1

节点可以包含在 BST struct 中，该结构将具有一个在插入/删除时递增和递减的计数器。