本履歴

購入した古本の履歴と時々プログラミング

プログラミングコンテストの練習

二分探索木をRubyで書いてみた。極悪データの追加とランダムデータの追加で処理時間を比べてみた。
バランスを取ることの重要性がわかるなあ。
次は乱択アルゴリズムのTreapを実装して、極悪データに対処してみる。

class Node
	attr_accessor :value,:parent,:left,:right
	def initialize(value,parent=nil)
		@value=value
		@parent=parent
		@left=nil
		@right=nil
		self
	end
	
	def child_num
		ret=0
		ret+=1 if @right
		ret+=1 if @left
		ret
	end
	
	def leaf?
		child_num==0
	end
end

class BST
	def intialize
		@root=nil
	end
	
	def root?(node)
		@root==node
	end
	
	def empty?
		@root==nil
	end
	
	def add(value)
		if empty?
			@root=Node.new(value)
		else
			node=@root
			while node do
				if value<=node.value
					if node.left
						node=node.left
					else
						node.left=Node.new(value,node)
						break
					end
				else
					if node.right
						node=node.right
					else
						node.right=Node.new(value,node)
						break
					end
				end
			end
		end
	end
	
	def _search(node,value)
		return false unless node
		return node if node.value==value
		if node.value<value
			_search(node.left,value)
		else
			_search(node.right,value)
		end
	end
	
	def search(value)
		_search(@root,value)
	end
	
	def _max(node)
		return node unless node.right
		_max(node.right)
	end
	
	def max
		nil if empty?
		_max(@root).value
	end
	
	def _delete(node)
		case node.child_num
		when 0
			if root?(node)
				@root=nil
			else
				if node.parent.right==node
					node.parent.right=nil
				else
					node.parent.left=nil
				end
			end
		when 1
			child_node=node.left
			child_node=node.right unless child_node
			if node.parent.right==node
				node.parent.right=child_node
			else
				node.parent.left=child_node
			end
		when 2
			left_max_node=_max(node.left)
			_delete(left_max_node)
			left_max_node.right=node.right
			left_max_node.left=node.left
			if node.parent.right==node
				node.parent.right=left_max_node
			else
				node.parent.left=left_max_node
			end
		end
	end
	
	def delete(value)
		node=search(value)
		return false unless node
		_delete(node)
		node
	end
	
	def to_a
		@ret=[]
		def traverse_in_order(node)
			return unless node
			traverse_in_order(node.left)
			@ret.push(node.value)
			traverse_in_order(node.right)
		end
		traverse_in_order(@root)
		@ret
	end
end

require"benchmark"
bst1=BST.new
bst2=BST.new
N=10000

Benchmark.bm do |x|
  x.report("worst case :"){
  	N.times{|i|bst1.add(i)}
  	N.times{|i|bst1.search(rand(N))}}
  x.report("random case:"){
  	[*0...N].shuffle.each{|j|bst2.add(j)}
  	N.times{|i|bst2.search(rand(N))}}
end

#       user     system      total        real
#worst case : 11.970000   0.050000  12.020000 ( 13.106473)
#random case:  0.090000   0.010000   0.100000 (  0.097615)