Skip lists in Ruby

Skip lists are an interesting data structure that you can use as a substitute of balanced trees. This relatively new data structure was invented by William Pugh in 1990. According to his paper on skip lists :

Skip lists are a data structure that can be used in place of balanced trees.
Skip lists use probabilistic balancing rather than strictly enforced balancing
and as a result the algorithms for insertion and deletion in skip lists are
much simpler and significantly faster than equivalent algorithms for
balanced trees.

I have tried to implement skip lists in Ruby. It is not super hard because the paper has pseudocode and the algorithm is rather intuitive.

class Node
  attr_accessor :key
  attr_accessor :value
  attr_accessor :forward

  def initialize(k, v = nil)
    @key = k 
    @value = v.nil? ? k : v 
    @forward = []
  end
end

class SkipList
  attr_accessor :level
  attr_accessor :header
  
  def initialize
   @header = Node.new(1) 
   @level = 0
   @max_level = 3 
   @p = 0.5 
   @node_nil = Node.new(1000000)
   @header.forward[0] = @node_nil
  end
  
  def search(search_key)
    x = @header
    @level.downto(0) do |i|
      while x.forward[i].key < search_key do
        x = x.forward[i]
      end
    end    
    x = x.forward[0]
    if x.key == search_key
      return x.value
    else
      return nil
    end
  end

  def random_level
    v = 0
    while rand < @p && v < @max_level
      v += 1
    end
    v
  end

  def insert(search_key, new_value = nil)
    new_value = search_key if new_value.nil? 
    update = []
    x = @header
    @level.downto(0) do |i|
      while x.forward[i].key < search_key do
        x = x.forward[i]
      end
      update[i] = x
    end    
    x = x.forward[0]
    if x.key == search_key
      x.value = new_value
    else
      v = random_level
      if v > @level 
        (@level + 1).upto(v) do |i|
          update[i] = @header
          @header.forward[i] = @node_nil
        end
        @level = v
      end
      x = Node.new(search_key, new_value) 
      0.upto(v) do |i|
        x.forward[i] = update[i].forward[i]
        update[i].forward[i] = x
      end
    end
  end
end

I have not implemented the delete method yet. It is similar to insert method and won't be so difficult to code. If you are interested, why don't you try to write it on your own?