赤黒木アニメーション

• 挿入（3.62 MB）
• 削除（3.13 MB）
• 参考：二分木画像化レシピ - 日記を書く [・w・] はやみずさん

できた。大きいのでリンクにとどめておく。
PostScriptのファイルを生成するコードは以下のような感じ。赤黒木のクラスのコードに下に追加する形で。

class MyHash
	class Node
		def print( out, height, level = 0, lx = 0.0, rx = 592.0, parent_x = nil, parent_y = nil )
			x = ( lx + rx ) / 2
			y = 800.0 - level * height
			if level > 0
				out.puts "#{red? ? 1 : 0} 0 0 setrgbcolor"
				out.puts "#{5.0/level} setlinewidth"
				out.puts "newpath #{parent_x} #{parent_y} moveto #{x} #{y} lineto stroke"
			end
			@left.print( out, height, level + 1, lx, x, x, y ) if @left
			@right.print( out, height, level + 1, x, rx, x, y ) if @right
		end
		
		def max_height
			return 1 if nilnode?
			# 片方が赤でもう片方が黒なら赤の方だけ見ればいいよね
			if @left.red? && @right.black?
				count = @left.max_height + 1
			elsif @left.black? && @right.red?
				count = @right.max_height + 1
			else
				left_count = @left.max_height
				right_count = @right.max_height
				count = [left_count, right_count].max + 1
			end
			return count
		end
	end
	
	def print( out )
		out.puts '%!PS-Adobe-2.1'
		out.puts '%%PageBoundingBox: -5 -5 597 805'
		height = @tree.max_height
		height = 800.0 / ( height - 1 ) if height != 0.0
		@tree.print( out, height )
		out.puts "showpage"
	end
end

class Array
	def shuffle
		array = self
		s = []
		s << array.delete_at(rand(array.size)) until array.empty?
		return s
	end
end

MAX = 10000
NUM = 170

hash = MyHash.new
a = Math.exp( Math.log( MAX ) / NUM )
n = 1.0
file_count = 0
array = (1..MAX).to_a.shuffle
i = 1
array.each do |v|
	hash[v] = true
	if i >= n.floor
		filename = "tree_animation_#{'%03d' % file_count}.ps"
		open( filename, 'w' ) {|f| hash.print( f ) }
		puts "#{i} #{filename} #{hash.to_a.size} #{hash.tree.valid?.inspect}"
		file_count += 1
		n *= a
	end
	i += 1
end

そして、ImageMagickで

mogrify -format gif -geometry 360x225! *.ps

とそれぞれのファイルをGIFファイルに変換。
さらに、

convert -delay 24 -loop 0 tree_animation_*.gif tree_animation.gif

としてGIFアニメに。