Skip List Ruby Implementation

skip_list.rb

INFINITY = 1.0 / 0
NEG_INFINITY = -1.0 / 0

class Node
  MAX_LEVEL = 7
  # node has value and levels
  attr_accessor :val, :levels
  def initialize(val)
    self.val = val
    self.levels = []
  end
end

class SkipList
  attr_accessor :head
  def initialize
    self.head = Node.new(NEG_INFINITY)
    tail = Node.new(INFINITY)
    0.upto(Node::MAX_LEVEL) do |level|
      head.levels[level] = tail
    end
  end

  def search_path(val)
    path = []
    level = Node::MAX_LEVEL
    head = self.head
    while level >= 0
      path[level] = head
      if head.levels[level].val >= val
        level -= 1
      else
        head = head.levels[level]
      end
    end
    path
  end

  def search(val)
    level = Node::MAX_LEVEL
    head = self.head
    while level >= 0
      if head.levels[level].val > val
        level -= 1
      elsif head.levels[level].val < val
        head = head.levels[level]
      else
        return true
      end
    end
    return head.val == val
  end

  def insert(val)
    path = search_path(val)
    return if path[0].levels[0].val == val
    node = Node.new(val)
    0.upto(Node::MAX_LEVEL) do |level|
      if rand(1..2**level) == 1
        node.levels[level] = path[level].levels[level]
        path[level].levels[level] = node
      else
        break
      end
    end
  end

  def delete(val)
    path = search_path(val)
    0.upto(Node::MAX_LEVEL) do |level|
      if path[level].levels[level].val == val
        path[level].levels[level] = path[level].levels[level].levels[level]
      else
        break
      end
    end
  end

  def print_list
    Node::MAX_LEVEL.downto(0) do |level|
      head = self.head
      while head do
        print head.val, '--->'
        head = head.levels[level]
      end
      puts ''
    end
  end
end

sl = SkipList.new
sl.insert(5)
p sl.search 5
p sl.search 10
sl.insert(15)
p sl.search 15
p sl.search 10
sl.insert 4
sl.print_list
p sl.search 4
sl.delete 4
p sl.search 4
sl.print_list