Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
# 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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment