在O（1）時間中查找BST尺寸C

我有兩個問題。這兩個函數的當前運行時間是什麼？如果它不是O（1）（對我來說看起來像O（n）），有人可以給我一個提示（而不是給我答案），說明如何使它進入O（1）？謝謝在O（1）時間中查找BST尺寸C

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); 
}

來源

2013-12-08 juice

如果您總是明確地存儲和更新大小，則只能使其成爲「O（1）」。 – 2013-12-08 20:32:42

如果你想通過枚舉所有節點來找到樹的大小，它將是Omega（n）。除非您按照H2CO3的建議將尺寸存儲在節點中。 – igon

二元搜索樹[平衡]（http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree）？考慮[紅黑樹]（http://en.wikipedia.org/wiki/Red-black_tree）... –

節點可以在BST struct，這將有將遞增，並在插入/拔出遞減計數器來countained。

來源

2013-12-08 20:34:43 Julius

這個問題是關於C，它沒有類。如果用'struct'替換'class'這個詞，它可能會起作用。 – Kninnug

是的，我遇到的唯一問題是在插入點。我遞歸地使用它，所以如果我在堆棧上增加它，它會多次增加。 – juice

我認爲會有另一種方式做到這一點大聲笑。沒關係。 – juice

在O（1）時間中查找BST尺寸C

回答

相關問題