2分探索木の連想配列で削除方法を変えたら速くなった

連想配列の再発明（線形検索、二分探索木、ハッシュテーブル）してそれぞれの時間計測 - fujidigの雑記の2分探索木バージョンの改良。
クラス名をMyHash2Mに変更し上記の記事のコードに追加してみると、

                user     system      total        real
Hash        0.032000   0.000000   0.032000 (  0.031000)
MyHash1    32.515000   0.000000  32.515000 ( 32.515000)
MyHash2     1.063000   0.016000   1.079000 (  1.094000)
MyHash2M    0.640000   0.000000   0.640000 (  0.641000)
MyHash3     0.219000   0.000000   0.219000 (  0.218000)

こんな感じで半分くらいの時間に短くなっています。今までの削除方法では木の高さが高くなってしまって効率が悪かったんでしょうね。
ところで、ノードを置き換える場合、「ノード = nil」ではなく、「親ノード.left = nil」のようにしなくてはいけなく面倒ですね。とりあえず、ProcやMethodを使ってやっていますが。

参考にしました

http://www.geocities.jp/h2fujimura/mutter/tree/binary-search-tree.html#delete

class MyHash
	include Enumerable
	
	#Node = Struct.new( :key, :hash, :value, :left, :right )
	class Node
		def initialize( key, value, left = nil, right = nil )
			@key = key
			@value = value
			@left = left
			@right = right
		end
		
		attr_accessor :key, :value, :left, :right
		
		def each
			@left.each{|v| yield v } if @left
			yield [key, value]
			@right.each{|v| yield v } if @right
		end
		
		def inspect( level = 0 )
			puts ' ' * level + key.inspect
			if @left
				puts ' ' * level + 'left:'
				@left.inspect( level + 1 )
			end
			if @right
				puts ' ' * level + 'right:'
				@right.inspect( level + 1 )
			end
		end
	end
	
	def initialize
		@tree = nil
	end
	
	attr_reader :tree
	
	def []( key )
		hash = key.hash
		node = @tree
		loop do
			return nil unless node
			return node.value if node.key.hash == hash && node.key.eql?( key )
			if hash < node.key.hash
				node = node.left
			else
				node = node.right
			end
		end
		return nil
	end
	
	def []=( key, value )
		hash = key.hash
		unless @tree
			@tree = Node.new( key, value )
			return value
		end
		node = @tree
		loop do
			if node.key.hash == hash && node.key.eql?( key )
				node.value = value
				return value
			end
			if hash < node.key.hash
				unless node.left
					node.left = Node.new( key, value )
					return value
				else
					node = node.left
				end
			else
				unless node.right
					node.right = Node.new( key, value )
					return value
				else
					node = node.right
				end
			end
		end
	end
	
	def delete( key )
		hash = key.hash
		node = @tree
		set_node = proc{|v| @tree = v }
		loop do
			return nil unless node
			if node.key.hash == hash && node.key.eql?( key )
				value = node.value
				if node.left && node.right
					# nodeの値より小さい値のうちの最大値を探し、nodeの値を置き換える
					n = node.left
					set_n = node.method( :left= )
					while n.right
						set_n = n.method( :right= )
						n = n.right
					end
					node.key = n.key
					node.value = n.value
					set_n.call( n.left )
				elsif node.left
					set_node.call( node.left )
				elsif node.right
					set_node.call( node.right )
				else
					set_node.call( nil )
				end
				return value
			end
			if hash < node.key.hash
				set_node = node.method( :left= )
				node = node.left
			else
				set_node = node.method( :right= )
				node = node.right
			end
		end
	end
	
	def each
		@tree.each{|v| yield v } if @tree
	end
	
	def inspect
		'{' + map{|key,value|
			key.inspect+'=>'+value.inspect}.join(', ') + '}'
	end
end