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

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 中的对象数。可以假设每个键都是唯一的，不能假设 ADT 中存在 a 或 b。

标签： algorithmdata-structuresbinary-treehashtableavl-tree

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();
    }

}

Python

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

参考：

如何实现跳过列表？