哪种数据结构可以提供有效的范围操作

Question

我被要求实现一个数据结构。经过几次尝试，我遇到了麻烦，我想获得有关如何使用 AVL 和哈希表实现以下方法的想法： 建议一个包含一组动态对象的 ADT，以便每个对象都有其唯一值 (id(，并支持以下内容：

init- 初始化一个空结构 - O(1(。

add(x(- 将 x 插入结构 - O(log(n((。

remove(x(- 从结构中删除 x - O(log(n((。

range(a，b( -假设 a 小于 b，返回一个带有键在范围 [a，b] - O(log(n(+k 范围内的对象的数组，其中 k 是该范围内的对象数。

空间复杂度为 O(n(，其中 n 是给定时间内 ADT 中的对象数量。 可以假设每个键都是唯一的，不能假定 a 或 b 存在于 ADT 中。

Answer 1

我认为这是一个很好的答案。

LeetCode的1206(Design Skiplist(可能与你希望设计的设计"有点"相似。

爪哇岛

class Skiplist {
private static final double DEFAULT_PROB = 0.5;
private final Random rand = new Random();
private final List<Node> sentinels = new ArrayList<>();
{
sentinels.add(new Node(Integer.MIN_VALUE));
}

private static final class Node {
private final int val;
private Node left, right, up, down;
private Node(int val) {
this.val = val;
}
}
public boolean search(int target) {
Node smallerOrEquals = getSmallerOrEquals(target);
return smallerOrEquals.val == target;
}
public void add(int num) {
Node curr = getSmallerOrEquals(num);
final Node nodeToInsert = new Node(num);
append(curr, nodeToInsert);
populateLevelUp(nodeToInsert);
}
private void populateLevelUp(final Node nodeToInsert) {
Node curr = nodeToInsert;
Node currPrev = nodeToInsert.left;
while (flipCoin()) {
while (currPrev.left != null && currPrev.up == null)
currPrev = currPrev.left;
if (currPrev.up == null) {
final Node tempSentinel = new Node(Integer.MIN_VALUE);
currPrev.up = tempSentinel;
tempSentinel.down = currPrev;
sentinels.add(currPrev.up);
}
currPrev = currPrev.up;
final Node tempNode = new Node(nodeToInsert.val);
curr.up = tempNode;
tempNode.down = curr;
curr = curr.up;
currPrev.right = curr;
curr.left = currPrev;
}
}

private void append(Node prev, Node curr) {
final Node next = prev.right;
prev.right = curr;
curr.left = prev;
if (next != null) {
next.left = curr;
curr.right = next;
}
}

public boolean erase(int num) {
final Node nodeToRemove = getSmallerOrEquals(num);
if (nodeToRemove.val != num)
return false;
Node curr = nodeToRemove;
while (curr != null) {
final Node prev = curr.left;
final Node next = curr.right;
prev.right = next;
if (next != null)
next.left = prev;
curr = curr.up;
}
return true;
}
private Node getSmallerOrEquals(final int target) {
Node curr = getSentinel();
while (curr != null) {
if (curr.right == null || curr.right.val > target) {
if (curr.down == null)
break;
curr = curr.down;
} else
curr = curr.right;
}
return curr;
}
private boolean flipCoin() {
return rand.nextDouble() < DEFAULT_PROB;
}
private Node getSentinel() {
return sentinels.get(sentinels.size() - 1);
}
public String toString() {
Node node = sentinels.get(0);
final StringBuilder sb = new StringBuilder();
while (node != null) {
Node iter = node;
while (iter != null) {
sb.append(iter.val).append(",");
iter = iter.up;
}
sb.append("n");
node = node.right;
}
return sb.toString();
}
}

蟒

class Node:

def __init__(self, val, levels):
self.val = val
self.levels = [None] * levels

class Skiplist:
def __init__(self):
self.head = Node(-1, 16)
def __iter__(self, num):
cur = self.head
for level in range(15, -1, -1):
while True:
future = cur.levels[level]
if future and future.val < num:
cur = future
else:
break
yield cur, level
def search(self, target):
for prev, level in self.__iter__(target):
pass
cur = prev.levels[0]
return cur and cur.val == target
def add(self, num):
node_level = min(16, 1 + int(math.log2(1. / random.random())))
node = Node(num, node_level)
for cur, level in self.__iter__(num):
if level < node_level:
future = cur.levels[level]
cur.levels[level] = node
node.levels[level] = future
def erase(self, num):
res = False
for cur, level in self.__iter__(num):
future = cur.levels[level]
if future and future.val == num:
res = True
cur.levels[level] = future.levels[level]
return res

引用：

如何实现船长？

Answer 2

跳过列表可以满足所有这些要求。

• 插入和删除已经内置于跳过列表中。
• 对于 range(a，b( - 你寻找第一个更小/eqaulsa元素，一旦找到，就开始迭代最低级别的链表，直到你找到b或更高的元素。