java - 实现数据结构——弹性字典

Question

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

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

Answer 1

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

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

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