在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”。