0

我被要求设计一个代表字典的数据结构。字典包含具有不同键号的项目。数据结构应在 O(1) 时间内支持以下操作:insert(x)、delete(x)、findMin()、findMax()、successor(x)、previous(x)。search(x) 操作也应该在 O(log n) 时间内进行。

作业是针对以下主题进行的:跳过列表、哈希表和堆。我想最好的结构将是一个跳过列表,但我找不到在 O(1) 中实现插入和删除的方法。有什么建议么?

4

1 回答 1

0

您应该同时使用哈希表和跳过列表数据结构。您可以在每次插入元素时更新min和值。max因此findMin()findMax()也是O(1)
insert()并且delete()也处于恒定的时间。

顺便说一句,您不能在搜索之前删除项目。如果您在 中进行搜索O(logn)delete()O(logn)自动进行。

哈希表提供(如果实施正确)、搜索、删除和插入O(1)。其余操作 ( successor(), predecessor()) 在跳过列表中可用。

于 2014-05-27T18:28:20.587 回答