赤黒木を実装中 削除はまだ

参考

http://www.geocities.jp/h2fujimura/mutter/tree/red-black-tree.html

class RedBlackTree
	class Node
		def initialize( key, value, is_red = false, left = nil, right = nil, is_nilnode = false )
			@key        = key
			@value      = value
			@is_red     = is_red
			if is_nilnode
				@is_nilnode = true
				@left = nil
				@right = nil
				@parent = nil
				return
			end
			@parent     = nil
			self.left   = left  || self.class.new_nilnode
			self.right  = right || self.class.new_nilnode
			@is_nilnode = false
		end
		
		def self.new_nilnode
			return new( 'NIL', nil, false, nil, nil, true )
		end
		
		attr_accessor :key, :value, :is_red, :left, :right, :parent, :is_nilnode
		
		def nilnode?; @is_nilnode; end
		
		def left=( left )
			@left = left
			left.parent = self
		end
		
		def right=( right )
			@right = right
			right.parent = self
		end
		
		# 他のノードからインスタンス変数をコピー
		# 親ノード情報はコピーしない
		# other の子の親ノード情報を更新する
		def set( other )
			[:@key, :@value, :@is_red, :@left, :@right, :@is_nilnode].each do |sym|
				instance_variable_set( sym, other.instance_variable_get( sym ) )
			end
			unless other.nilnode?
				other.left.parent = self
				other.right.parent = self
			end
		end
		
		# 左の子か
		def left?
			parent.left == self
		end
		
		# 右の子か
		def right?
			parent.right == self
		end
		
		# 部分木の内側の子か
		def inside?
			( left? && parent.right? ) || ( right? && parent.left? )
		end
		
		# 兄弟を返す
		def brother
			left? ? parent.right : parent.left
		end
		
		# 親の親（祖父）を返す
		def grandparent
			parent.parent
		end
		
		# 親の兄弟（叔父）を返す
		def uncle
			parent.brother
		end
		
		# 根か
		def root?
			!@parent
		end
		
		# 赤黒木のルールを満たした木か（デバッグ用）
		# invalidならfalse、validであれば根から葉までの黒ノードの数を返す
		def valid?( parent = nil, count = 0, is_left = false )
			return false if root? && red? # 根は黒である必要がある
			return false if parent != @parent # 親ノードの情報が正しくない
			return false if parent && parent.red? && red? # 赤いノードの子は黒である必要がある
			if !root?
				return false if is_left != left?
				return false if !is_left != right?
				return false if brother.brother != self
				if !nilnode?
					# 左の子であれば親より小さい必要がある
					return false if left? && @key >= parent.key
					# 右の子であれば親より大きい必要がある
					return false if right? && @key < parent.key
				end
			end
			if nilnode?
				return false if red? # 葉は黒である必要がある
				return count + 1
			end
			# 子ノードを再帰的にチェックする
			count += 1 if black?
			left_count = @left.valid?( self, count, true )
			return false if !left_count
			right_count = @right.valid?( self, count, false )
			return false if !right_count
			# 右のノードと左のノートで葉までの黒ノードの数が異なる
			return false if left_count != right_count
			return left_count
		end
		
		# 左回り（半時計回り）で回転
		def rotate_left
			a = self
			b = left
			c = right
			d = c.left
			e = c.right
			
			c_copy = self.class.new_nilnode.set( c )
			c.set( d )
			c_copy.left = self.class.new_nilnode.set( a )
			a.set( c_copy )
			return c_copy.left
		end
		
		# 右回り（時計回り）で回転
		def rotate_right
			a = self
			b = left
			c = right
			d = b.left
			e = b.right
			
			b_copy = self.class.new_nilnode.set( b )
			b.set( e )
			b_copy.right = self.class.new_nilnode.set( a )
			a.set( b_copy )
			return b_copy.right
		end
		
		# 外側に回転
		def rotate_outside
			left? ? rotate_left : rotate_right
		end
		
		def each
			return if nilnode?
			@left.each{|v| yield v } if @left
			yield [key, value]
			@right.each{|v| yield v } if @right
		end
		
		# デバッグ用表示
		def inspect( level = 0 )
			ret = ' ' * level
			ret += (red? ? '○' : '●') + ' '
			ret += key.inspect
			ret += "\n"
			return ret.chomp if nilnode?
			ret += @left.inspect( level + 2 ).chomp + "\n"
			ret += @right.inspect( level + 2 ).chomp + "\n"
			return ret.chomp
		end
		
		def red?; @is_red; end
		def black?; !@is_red; end
		def to_red; @is_red = true; end
		def to_black; @is_red = false; end
	end
	
	def initialize
		@tree = Node.new_nilnode
	end
	
	attr_reader :tree # デバッグ用に外部公開
	
	def []( key )
		node = search( key )
		return nil if node.nilnode?
		node.value
	end
	
	def []=( key, value )
		node = search( key )
		unless node.nilnode?
			node.value = value
			return value
		end
		node.set( Node.new( key, value, true ) )
		insert_adjust( node )
		return value
	end
	
	def each
		@tree.each{|v| yield v }
	end
	
	include Enumerable
	
	def inspect
		'{' + map{|key,value|
			key.inspect+'=>'+value.inspect}.join(', ') + '}'
	end
	
	#private
	
	# 引数のキーに一致するノードを返す
	# 見つからないときは挿入されるべき位置のNILノードを返す
	def search( key )
		node = @tree
		loop do
			return node if node.nilnode?
			return node if node.key == key
			if key < node.key
				node = node.left
			else
				node = node.right
			end
		end
	end
	
	# ノード挿入後の調整
	# 挿入されたノードを引数に指定する
	def insert_adjust( node )
		if node.root?
			node.to_black
			return
		end
		if node.parent.black?
			return
		end
		if node.uncle.red?
			node.parent.to_black
			node.uncle.to_black
			node.grandparent.to_red
			insert_adjust( node.grandparent )
			return
		end
		if node.inside?
			node = node.parent.rotate_outside
		end
		g = node.left? ? node.grandparent.rotate_right : node.grandparent.rotate_left
		g.to_red
		g.parent.to_black
	end
end

hash = RedBlackTree.new
1.upto(20) {|v| hash[v] = v }
p hash.tree
puts hash.tree.valid?