treap.rb

# Tree+Heap=Treap
class Treap
  attr_accessor :value, :left, :right, :priority

  # 空の頂点
  def self.empty()
    obj = self.new
    obj.value = -1
    obj.priority = rand(0.0...1.0)
    obj
  end
  
  @@empty = Treap.empty()

  def initialize(v, l=@@empty, r=@@empty)
    @value = v
    @left = l
    @right = r
    # 優先度。高いほど上に来る。ランダムに決める
    @priority = rand(0.0...1.0)
  end
  
  # 要素vを探す
  def search(v)
    return @@empty if self == @@empty
    return self if @value == v
    if v < @value
      # 小さければ左へ
      @left.search(v)
    else
      # 多きければ右へ
      @right.search(v)
    end
  end 

  # 左回転
  def rotate_left
    tmp = @right
    @right = tmp.left
    tmp.left = self

    return tmp
  end
  
  # 右回転
  def rotate_right
    tmp = @left
    @left = tmp.right
    tmp.right = self

    return tmp
  end
  
  # 木の高さを調べる
  def depth
    return 0 if self == @@empty
    [@left.depth, @right.depth].max + 1
  end
  
  # 頂点追加
  def self.add(root, v)
    # 最下部にまず追加する
    return self.new(v) if root == @@empty

    if v < root.value
      # 自分の左に持ってくる
      root.left = self.add(root.left, v)
      
      # 優先度が高いなら右回転で持ち上げる
      if root.priority < root.left.priority
        root = root.rotate_right()
      end
    else
      # 自分の右に持ってくる
      root.right = self.add(root.right, v)
      
      # 優先度が高いなら左回転で持ち上げる
      if root.priority < root.right.priority
        root = root.rotate_left()
      end
    end
    
    # 頂点を返す
    root
  end
end

# 1~100を追加
treap = Treap.new(1)
(2..100).each do |v|
  treap = Treap.add(treap, v)
end

# 高さを出力してみる
p treap.depth()