在O（log2n）中插入數據結構，但在O中搜索（1）

Question

當前正在進行一項需要在O（log2n）中插入一個數據結構的賦值，但是可以搜索O ）。由於log2n插入，我正在考慮BST，但無法在O（1）中進行搜索。哈希表可以插入最壞的O（n），並搜索O（1），但不幸的是，這不符合O（log2n）插入要求。

有人有什麼建議嗎？謝謝！

Answer 1

您可以將元素插入到二叉樹中，並將指向該元素的指針放入散列表中。或者，您可以將元素插入到O（1）的哈希表中，並使用O（1）進行搜索，並且符合要求「插入O（lb N）」 - 只需運行LogBin（N）空循環。

關於「最壞情況/平均情況」：在最壞的情況下，散列表和二叉樹（非平衡像rb，只是基元）都有O（N）。我認爲，你的任務是關於「平均情況」，這是平常的。哈希表可以提供O（1）。要保留選定數據集的攻擊，請使用「universal hashing」。