SkipList跳表

Python实现

class Skiplist:

    def __init__(self):

        self.head = Node()  # dummy head

    def search(self, target: int) -> bool:

        node = self.head

        while node:

            while node.right and node.right.val < target:

                node = node.right

            if node.right and node.right.val == target:

                return True

            node = node.down  # 这一层没有，往下一层

        return False

    def add(self, num: int) -> None:

        nodes = []

        node = self.head

        while node:

            # Move to the right in the current level

            while node.right and node.right.val < num:

                node = node.right

            nodes.append(node)

            # Move to the next level

            node = node.down

        insert = True

        down = None

        while insert and nodes:

            node = nodes.pop()

            node.right = Node(num, node.right, down)

            down = node.right

            insert = (random.getrandbits(1) == 0)

        # Create a new level with a dummy head

        # right = None

        # down = current head

        if insert:

            self.head = Node(-1, None, self.head)

    def erase(self, num: int) -> bool:

        node = self.head

        found = False

        while node:

            # Move to the right in the current level

            while node.right and node.right.val < num:

                node = node.right

            # Find the target node

            if node.right and node.right.val == num:

                # Delete by skipping

                node.right = node.right.right

                found = True

            # Move to the next level

            node = node.down

        return found

class Node:

    def __init__(self, val=-1, right=None, down=None):

        self.val = val

        self.right = right

        self.down = down

# Your Skiplist object will be instantiated and called as such:

# obj = Skiplist()

# param_1 = obj.search(target)

# obj.add(num)

# param_3 = obj.erase(num)

Java实现

class Skiplist {

    class Node {

        int val;

        Node right;

        Node down;

        Node(){

            this(-1, null, null);

        }

        Node(int val, Node right, Node down) {

            this.val = val;

            this.right = right;

            this.down = down;

        }

    }

    Node head;

    public Skiplist() {

        this.head = new Node();

    }

    public boolean search(int target) {

        Node node = head;

        while(node != null) {

            while(node.right != null && node.right.val < target)

                node = node.right;

            if(node.right != null && node.right.val == target)

                return true;

            node = node.down;

        }

        return false;

    }

    public void add(int num) {

        Node node = head;

        LinkedList nodes = new LinkedList<>();

        while(node != null) {

            while(node.right != null && node.right.val < num) {

                node = node.right;

            }

            nodes.add(node);

            node = node.down;

        }

        // 向上回溯，根据概率判断是否新增节点

        boolean isInsert = true;    // 最下面一层 100% 要新增

        double c = 1.0;

        Node down = null;           // 记录一下下面一层的down指针

        while 货币符号(!nodes.isEmpty() && isInsert) {

            Node cur = nodes.removeLast();

            cur.right = new Node(num, cur.right, down);

            down = cur.right;

            isInsert = count(c++);

        }

        if(isInsert)

            this.head = new Node(-1, null, head);

    }

    public boolean erase(int num) {

        Node node = head;

        boolean res = false;

        while(node != null) {

            while(node.right != null && node.right.val < num) {

                node = node.right;

            }

            if(node.right != null && node.right.val == num) {

                res = true;

                node.right = node.right.right;

            }

            node = node.down;

        }

        return res;

    }

// 计算概率

    static boolean count(double i) {

        double x = new Random().nextDouble();

        double y = 1 / Math.pow(2, i);

        return x <= y;

    }

}