如何实现一个跳表

跳表是非常实用的数据结构，在Redis ZSet、Java并发容器中常有实用。直觉该结构比较复杂，实际上核心操作逻辑非常简单。 随机操作+链表分层变化，就能实现条表。Leetcode有跳表问题，值得学习。

class Node
  def initialize(down = nil, next_node = nil, val = nil)
    @down = down
    @next = next_node
    @val = val
  end

  attr_accessor :val, :next, :down
end

class Skiplist
  def initialize()
    @head = Node.new
  end

=begin
    :type target: Integer
    :rtype: Boolean
=end
  def search(target)
    p = @head
    while p
      p = p.next while p.next && p.next.val < target
      return true if p.next && p.next.val == target
      p = p.down
    end
    false
  end

=begin
    :type num: Integer
    :rtype: Void
=end
  def add(num)
    stack = []
    p = @head
    while p
      p = p.next while p.next && p.next.val < num
      stack << p
      p = p.down
    end
    down = nil
    need = true
    while stack.any? && need
      p = stack.pop
      p.next = Node.new(down, p.next, num)
      down = p.next
      need = rand > 0.5
    end
    @head = Node.new(@head) if need
  end

=begin
    :type num: Integer
    :rtype: Boolean
=end
  def erase(num)
    p = @head
    found = false
    while p
      p = p.next while p.next && p.next.val < num
      if p.next && p.next.val == num
        found = true
        p.next = p.next.next
      end
      p = p.down
    end
    found
  end
end

sl = Skiplist.new
p sl.add(3)
p sl.search(3)
p sl.erase(3)
p sl.search(3)
# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist.new()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)