我被要求设计一个代表字典的数据结构。字典包含具有不同键号的项目。数据结构应在 O(1) 时间内支持以下操作:insert(x)、delete(x)、findMin()、findMax()、successor(x)、previous(x)。search(x) 操作也应该在 O(log n) 时间内进行。
作业是针对以下主题进行的:跳过列表、哈希表和堆。我想最好的结构将是一个跳过列表,但我找不到在 O(1) 中实现插入和删除的方法。有什么建议么?
我被要求设计一个代表字典的数据结构。字典包含具有不同键号的项目。数据结构应在 O(1) 时间内支持以下操作:insert(x)、delete(x)、findMin()、findMax()、successor(x)、previous(x)。search(x) 操作也应该在 O(log n) 时间内进行。
作业是针对以下主题进行的:跳过列表、哈希表和堆。我想最好的结构将是一个跳过列表,但我找不到在 O(1) 中实现插入和删除的方法。有什么建议么?