我有两个问题。这两个函数当前的运行时间是多少?如果不是 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);
}
最佳答案
节点可以包含在 BST struct
中,该结构将具有一个在插入/删除时递增和递减的计数器。
关于c - 在 O(1) 时间内找到 BST 大小 C,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20458656/