赤黒木の実装できたよ！

参考

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
			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 sibling
			left? ? parent.right : parent.left
		end
		
		# 親の親（祖父）を返す
		def grandparent
			parent.parent
		end
		
		# 親の兄弟（叔父）を返す
		def uncle
			parent.sibling
		end
		
		# 根か
		def root?
			!@parent
		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 }
			yield [key, value]
			@right.each {|v| yield v }
		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
	
	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 delete( key )
		node = search( key )
		return nil if node.nilnode?
		value = node.value
		if !node.left.nilnode? && !node.right.nilnode?
			# nodeの値より小さい値のうちの最大値を探し、nodeの値を置き換える
			n = node.left
			n = n.right until n.right.nilnode?
			node.key = n.key
			node.value = n.value
			delete_node( n )
			return value
		end
		delete_node( 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 )
		key_hash = key.hash
		node = @tree
		loop do
			return node if node.nilnode?
			return node if node.key.eql?( key )
			if key_hash < node.key.hash
				node = node.left
			else
				node = node.right
			end
		end
	end
	
	# ノード挿入後の調整
	# 挿入されたノードを引数に指定する
	def insert_adjust( node )
		# case 1
		if node.root?
			node.to_black
			return
		end
		# case 2
		if node.parent.black?
			return
		end
		# case 3
		if node.uncle.red?
			node.parent.to_black
			node.uncle.to_black
			node.grandparent.to_red
			insert_adjust( node.grandparent )
			return
		end
		# case 4
		if node.inside?
			node = node.parent.rotate_outside
		end
		# case 5
		node.parent.to_black
		node.grandparent.to_red
		node.left? ? node.grandparent.rotate_right : node.grandparent.rotate_left
	end

	def delete_node( node )
		if !node.left.nilnode?
			child = node.left
		elsif !node.right.nilnode?
			child = node.right
		else
			child = Node.new_nilnode
		end
		is_red = node.red? # 置き換えられる前の色
		node.set( child )
		return if is_red
		if node.red?
			node.to_black
			return
		end
		delete_adjust( node )
	end

	def delete_adjust( node )
		# case 1
		return if node.root?
		parent = node.parent
		sibling = node.sibling
		# case 2
		if sibling.red?
			parent.to_red
			sibling.to_black
			parent = node.left? ? parent.rotate_left : parent.rotate_right
			sibling = node.sibling
		end
		# case 3
		if parent.black? && sibling.left.black? && sibling.right.black?
			sibling.to_red
			delete_adjust( parent )
			return
		end
		# case 4
		if parent.red? && sibling.left.black? && sibling.right.black?
			parent.to_black
			sibling.to_red
			return
		end
		# case 5
		if sibling.left.red? && sibling.right.black? && node.left?
			sibling.to_red
			sibling.left.to_black
			sibling.rotate_right
		elsif sibling.left.black? && sibling.right.red? && node.right?
			sibling.to_red
			sibling.right.to_black
			sibling.rotate_left
		end
		# case 6
		sibling = node.sibling
		sibling.is_red = parent.is_red
		parent.to_black
		if node.left?
			sibling.right.to_black
			parent.rotate_left
		else
			sibling.left.to_black
			parent.rotate_right
		end
	end
end