Skip to content

Instantly share code, notes, and snippets.

@snipsnipsnip

snipsnipsnip/aa_tree.rb

Last active Aug 29, 2015
Embed
What would you like to do?
class Node
attr_accessor :value, :left, :right
def initialize(val)
@value = val # ノードが保持する値
@left = nil # 左側のノード
@right = nil # 右側のノード
end
end
# 描画に必要な情報を計算
def render_info(canvas, margin, node, x, y)
# 左のノードがあれば、そのノード以下の木の横幅を計算
x = render_info(canvas, margin, node.left, x, y + 1) + margin if node.left
# このノードの分の描画に必要な情報(X座標, Y座標, そのもの)を追加
canvas << [x, y, node]
# このノードの桁数を計算
x += node.value.to_s.size
# 右のノードがあれば、そのノード以下の木の横幅を計算
x = render_info(canvas, margin, node.right, x + margin, y + 1) if node.right
# 呼び出した親のために横幅を返す
x
end
# render_infoで描画情報を集めて返す
def render(root, margin=0)
canvas = []
render_info(canvas, margin, root, 0, 0)
canvas
end
# 9
# 4 15
# 2 6 12 17
# このメソッドはクラス外でOK
def print_canvas(canvas)
# X座標よりY座標を優先してソート
canvas = canvas.sort_by {|x, y, *| [y, x] }
last_x = 0
last_y = 0
# 各ノードをループで描画
canvas.each do |x, y, node|
text = node.value.to_s
# y座標が増えたら改行
if y != last_y
last_x = 0
puts
end
# 必要な分だけスペースを入れてプリント
print " " * (x - last_x)
print text
# カーソルを進める
last_x = x + text.to_s.size
last_y = y
end
puts
end
# _9__
# 4 15
# 2 6 12 17
def print_canvas2(canvas)
canvas = canvas.sort_by {|x, y, *| [y, x] }
last_x = 0
last_y = 0
# 各ノードをループで描画
canvas.each do |x, y, node|
text = node.value.to_s
if y != last_y
last_x = 0
puts
end
if node.left
# 「次の行の数字で、この数字のすぐ左にあるもの」を探してX座標をとる
ileft = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx } - 1
left_x, * = canvas[ileft]
left_x_end = left_x + node.left.value.to_s.size
print " " * (left_x_end - last_x)
print "_" * (x - left_x_end)
else
print " " * (x - last_x)
end
print text
x += text.to_s.size
# 数字右側の下線
if node.right
# 「次の行の数字で、この数字のすぐ右にあるもの」を探してX座標をとる
iright = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx }
right_x, * = canvas[iright]
print "_" * (right_x - x)
x = right_x
end
last_x = x
last_y = y
end
puts
end
# 9_
# / \
# 4 15
# 2 6 12 17
def print_canvas3(canvas)
# Y座標ごとにグループ分け
canvas_lines = canvas.group_by {|x, y, *| y }.sort.map {|_, line| line.sort }
canvas_lines.each do |line|
# 斜線の描画を記憶しておく配列
slashes = []
# この行に属す数字を描画していく
last_x = 0
line.each do |x, y, node|
text = node.value.to_s
# 数字左側の下線
if node.left
next_line = canvas_lines[y + 1]
ileft = next_line.index {|nx, *| x <= nx } - 1
left_x, * = next_line[ileft]
left_x_end = left_x + node.left.value.to_s.size
print " " * (left_x_end - last_x)
if left_x_end < x
# 下線の左端を欠けさせる (スペースにする)
print " "
print "_" * (x - left_x_end - 1)
# 斜線の描画を予約 (左手ノードなのでスラッシュ)
slashes << [left_x_end, '/']
end
else
print " " * (x - last_x)
end
print text
x += text.to_s.size
# 数字右側の下線
if node.right
next_line = canvas_lines[y + 1]
iright = next_line.index {|nx, *| x <= nx }
right_x, * = next_line[iright]
if x < right_x
# 下線の右端を欠けさせる (スペースにする)
print "_" * (right_x - x - 1)
print " "
# 斜線の描画を予約 (右手ノードなのでバックスラッシュ)
slashes << [right_x - 1, '\\']
end
x = right_x
end
last_x = x
end
puts
# 改行して斜線を描画
last_x = 0
slashes.each do |x, char|
print " " * (x - last_x)
print char
last_x = x + 1
end
puts unless slashes.empty?
end
end
# ツリーの宣言を短く書くために定義
def Node(val, left=nil, right=nil)
node = Node.new(val)
node.left = left
node.right = right
node
end
tree = Node(9, Node(4, Node(2), Node(6)), Node(15, Node(12), Node(17)))
print_canvas render(tree)
print_canvas2 render(tree)
print_canvas3 render(tree)
print_canvas3 render(Node(4, tree, tree))
print_canvas3 render(Node(4, tree, tree), 2)
print_canvas3 render(Node(4, Node(4), tree), 1)
# バグ: 右手にノードがないと落ちる
# print_canvas3 render(Node(4, tree, nil), 1)
# print_canvas3のバグを修正して整理しました
class Node
attr_accessor :value, :left, :right
def initialize(val)
@value = val # ノードが保持する値
@left = nil # 左側のノード
@right = nil # 右側のノード
end
end
# 描画位置の決まったノード
RenderedNode = Struct.new(:x, :y, :node) do
# ノードの描画に必要な幅
def width
node.value.to_s.size
end
end
# 各ノードの位置を計算する
class Renderer
def initialize(margin=0)
@margin = margin
end
# render_infoで描画情報を集めて返す (外部用)
def render(root)
@nodes = []
render_info(root, 0, 0)
@nodes
end
private
# 描画に必要な情報を計算 (内部用)
def render_info(node, x, y)
# 左のノードがあれば、そのノード以下の木の横幅が返ってくる
x = render_info(node.left, x, y + 1) + @margin if node.left
# このノードの分の描画に必要な情報を追加
@nodes << RenderedNode.new(x, y, node)
# このノードの分の描画に必要な情報を追加
x += node.value.to_s.size
x = render_info(node.right, x + @margin, y + 1) if node.right
# 呼び出した親のために横幅を返す
x
end
end
# Rendererの返した座標データから二分木のAAを表示する
class Printer
# コンストラクタで座標データをうけとる
def initialize(nodes)
@lines = group_by_line(nodes)
@slashes = nil
end
# 旧print_canvas
def run
@slashes = []
@lines.each do |line|
print_numbers(line)
print_slashes
@slashes.clear
end
end
private
# 座標データを行ごとにグループ分け
def group_by_line(nodes)
nodes.group_by {|n| n.y }.sort.map {|_, line| line.sort_by {|n| n.x } }
end
# 数字と下線からなる行の表示
def print_numbers(line)
last_x = 0
line.each do |n|
x = print_left_space(n, last_x)
x = print_node(n, x)
x = print_right_space(n, x)
last_x = x
end
puts
end
# 数字左の空白と下線の表示
# 右端の座標(現在のカーソル位置)を返す
def print_left_space(n, last_x)
x = n.x
if left_child = find_left_child(n)
left_x_end = left_child.x + left_child.width
print " " * (left_x_end - last_x)
if left_x_end < x
print " ", "_" * (x - left_x_end - 1)
# 斜線の描画を予約 (左手ノードなのでスラッシュ)
@slashes << [left_x_end, '/']
end
else
print " " * (x - last_x)
end
x
end
# 数字本体の表示
# 右端の座標(現在のカーソル位置)を返す
def print_node(n, x)
print n.node.value
x + n.width
end
# 数字右の空白と下線の表示
# 右端の座標(現在のカーソル位置)を返す
def print_right_space(n, x)
if right_child = find_right_child(n)
right_x = right_child.x
if x < right_x
print "_" * (right_x - x - 1), " "
# 斜線の描画を予約 (右手ノードなのでバックスラッシュ)
@slashes << [right_x - 1, '\\']
end
x = right_x
end
x
end
# 斜線からなる行の表示
def print_slashes
last_x = 0
@slashes.each do |x, char|
print " " * (x - last_x)
print char
last_x = x + 1
end
puts unless @slashes.empty?
end
# 右手の子ノードを探す
def find_right_child(n)
@lines[n.y + 1][index_right_child(n)] if n.node.right
end
# 左手の子ノードを探す
def find_left_child(n)
if n.node.left
next_line = @lines[n.y + 1]
# * バグ修正部分 *
# 右手のノードを探してからそのすぐ左を取る方法なので
# 右手にノードがない場合に失敗する
i = index_right_child(n)
if i
next_line[i - 1]
else
next_line.last
end
end
end
# 右手の子ノードの添字を見つける
def index_right_child(n)
next_line = @lines[n.y + 1]
next_line.index {|m| n.x <= m.x }
end
end
# ツリーの宣言を短く書くために定義
def Node(val, left=nil, right=nil)
node = Node.new(val)
node.left = left
node.right = right
node
end
# AAを描画
def draw_tree(root_node, margin)
nodes = Renderer.new(margin).render(root_node)
Printer.new(nodes).run
end
tree = Node(9, Node(4, Node(2), Node(6)), Node(15, Node(12), Node(17)))
draw_tree Node(4, tree, Node(3, tree, nil)), 1
__END__
_________4_________________
/ \
__9___ _________3
/ \ /
4 15 __9___
/ \ / \ / \
2 6 12 17 4 15
/ \ / \
2 6 12 17
9
4 15
2 6 12 17
_9__
4 15
2 6 12 17
9_
/ \
4 15
2 6 12 17
_____4__
/ \
9_ 9_
/ \ / \
4 15 4 15
2 6 12 17 2 6 12 17
_________4______
/ \
__9___ __9___
/ \ / \
4 15 4 15
/ \ / \ / \ / \
2 6 12 17 2 6 12 17
_4__________
/ \
_____________9 ____9_____
/ / \
____9_____ _4_ _15_
/ \ / \ / \
_4_ _15_ 2 6 12 17
/ \ / \
2 6 12 17
_________________4______________
/ \
______9_______ ______9_______
/ \ / \
__4__ __15__ __4__ __15__
/ \ / \ / \ / \
2 6 12 17 2 6 12 17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment