이진트리 레이아웃 #2

이진트리를 그리기 위해 각 노드의 위치 (x,y)를 계산하는 문제다. 트리의 노드 위치를 결정하기 위한 레이아웃 알고리즘은 아래와 같다.

출처: https://sites.google.com/site/prologsite/prolog-problems/4

레이아웃 알고리즘

두 자식의 x축 상 간격이 2의 배수로 증가한다. y좌표는 트리 상의 깊이로 결정된다.

입출력

트리를 생성하기 위한 입력 포맷이나, 레이아웃이 적용된 각 노드의 위치를 출력하는 형식은 자유롭게 결정한다.

입력 예 #1

"n(k(c(a,e(d,g)),m),u(p(,q),))"와 같이 입력받을 수 있다. parent(left,right)의 모양을 재귀적으로 표현한 것이다. (자식이 둘다 없으면 괄호부분이 생략된다.)

입력 예 #2

"nkcmaedgupq"와 같이 입력 받아 각 글자를 노드의 라벨로 하여 이진탐색트리를 만들 수 있다.

입력 예 #3

입력을 따로 신경쓰고 싶지 않다면 코드로 직접 트리를 만들어도 된다. 만약 Java라면 다음과 같을 것이다.

class Tree<A> {
  A value;
  Tree<A> left;
  Tree<A> right;
  ...
}

Tree<String> t = new Tree("root", new Tree("left", null, null), new Tree("right", null, null));

출력 예 #1

inorder 출력으로 각 노드의 내용과 위치 (x,y)를 출력한다.

a 1 4
c 3 3
d 4 5
e 5 4
g 6 5
...

출력 예 #2

HTML/SVG/GraphViz 등으로 직접 그려도 좋을 것이다.

출력 예 #3

출력할 필요없이 테스트 코드로 확인해도 좋다.

public void test() {
  Tree<Integer> t = ...;
  Tree<Point>   expected = ...;
  assertEquals(expected, layout(t));
}
이진트리
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

4개의 풀이가 있습니다.

예의 그림에서 c를 기준으로 보면.. c의 높이는 3(맨 밑을 1로 보면) c의 자식들의 x는 c를 기준으로 -2, +2 에 있다. 이는 2^(height-2)다.

  123456
1   c
2 a   e
3    d g

즉, 미리 루트의 높이를 계산하면 루트에서의 양팔의 길이를 알 수 있고, 자식들로 내려가면서 양팔의 길이는 반씩 줄여가면 된다.

이때, x는 왼쪽 오른쪽의 자식들 상황에 따라 달라지므로, 임의의 값으로 진행한 다음 후보정하는 방법을 취하거나 루트에서 맨왼쪽 자식까지의 높이 차를 기준으로 선보정할 수 있다.

다른 utility 함수들은 레이아웃#1 풀이를 참고하고.. 후보정하는 방식으로 구현한다면..

// 노드의 양팔 길이는 2^height
void tree_layout2(tree* t) {
    int height = tree_height(t);           // 높이
    layout2_(t, 0, 1, powi(2, height - 2));// 팔길이계산하여 0, 1기준으로 layout시작
    int minx = tree_leftmost(t)->x;              // 맨왼쪽 자식의 x가
    layout2_translate_x(t, 1-minx);        // 1이 되도록 translate
}

void layout2_(tree* t, int x, int y, int arm) {
    t->x = x;
    t->y = y;

    if (t->left) layout2_(t->left, x-arm, y+1, arm/2);
    if (t->right) layout2_(t->right, x+arm, y+1, arm/2);
}

void layout2_translate_x(tree* t, int dx) {
    t->x += dx;

    if (t->left) layout2_translate_x(t->left, dx);
    if (t->right) layout2_translate_x(t->right, dx);
}

tree* tree_leftmost(tree* t) {
    while (t->left) {
        t = t->left;
    }
    return t;
}

int tree_height(tree* t) {
    if (!t) return 0;
    return 1 + max(tree_height(t->left), tree_height(t->right));
}

2016/11/16 11:05

Han Jooyung

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

좌측순회를 마친 뒤 L(node.x), U(node.x), R(node.r.x) 순서로 x 계산.

add = ->par,node do 
  par ? node.y = par.y + 1 : (return node)
  chd = node.val < par.val ? par.l : par.r
  chd ? add[chd, node] : (node.val < par.val ? par.l = node : par.r = node)
  par
end

calc_x = ->node,par,max_y do
  left_x = par.x + 2**(max_y-node.y) * (node == par.l ? -1 : 1) if par
  node.x = (node.l ? node.l.x + 2**(max_y-node.y-1) : par&.x > 0 ? left_x : 1)
  node.r.x = node.x + 2**(max_y-node.y-1) if node.r                           
end

layout = ->tree_str=gets.chop do
  Node = Struct.new(:val, :x, :y, :l, :r)
  nodes = tree_str.chars.map {|c| Node.new(c, 0, 1) }
  btree, max_y = nodes.reduce(&add), nodes.max_by(&:y).y

  trav = ->node,par=nil do
    trav[node.l, node] if node.l
    calc_x[node, par, max_y]
    puts node.values[0..2].join(" ")
    trav[node.r, node] if node.r
  end
  trav[btree]
end

Test

in_ordered =  "a 1 4\n"  + "c 3 3\n"  + "d 4 5\n"  + "e 5 4\n"  +
              "g 6 5\n"  + "k 7 2\n"  + "m 11 3\n" + "n 15 1\n" +
              "p 19 3\n" + "q 21 4\n" + "u 23 2\n"
expect{ layout["nkcmaedgupq"] }.to output(in_ordered).to_stdout

Output

cmd > layout.call
nkcmaedgupq
a 1 4
c 3 3
d 4 5
e 5 4
g 6 5
k 7 2
m 11 3
n 15 1
p 19 3
q 21 4
u 23 2
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
class BinaryTree():
    class Node():
        def __init__(self, data):
            self.left = None
            self.right = None
            self.data = data
            self.depth = 1
            self.x = 0

        def child(self, node):
            if self.data == node.data:
                return
            key = 'left' if self.data > node.data else 'right'
            if self.__dict__[key] == None:
                node.depth = self.depth + 1
                self.__dict__[key] = node
            else:
                self.__dict__[key].child(node)

        def print_inorder_pos(self, x, depth):
            if self.left != None:
                self.left.print_inorder_pos(x, depth)
                self.x = self.left.x + (2 ** (depth - self.left.depth))
            else:
                self.x = 1 if x == -1 else x + (2 ** (depth - self.depth))
            print(self.data, self.x, self.depth)
            if self.right != None:
                self.right.print_inorder_pos(self.x, depth)

    def __init__(self, data):
        self.depth = 1
        self.root = None
        if data != None:
            self.set(data)

    def set(self, data):
        for x in data:
            self.add(BinaryTree.Node(x))

    def add(self, node):
        if self.root == None:
            self.root = node
        else:
            self.root.child(node)
        if node.depth > self.depth:
            self.depth = node.depth

    def print_inorder(self):
        self.root.print_inorder_pos(-1, self.depth)

bt = BinaryTree("nkcmaedgupq")
bt.print_inorder()

Python 3.5.2에서 작성하였습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python3:

트리는 배열에 바로 저장하고, 다음과 같이 사용합니다.

.

btree[0]: 사용 안 함

btree[1]: 루트 노드

btree[x]의 왼쪽자식 = btree[x*2]

btree[x]의 오른쪽자식 = btree[x*2+1]

btree[x]의 부모 = btree[x//2]

.

그리고 편의상 깊이 대신 높이를 사용합니다.

깊이와는 반대로 가장 깊은 노드부터 0, 1, 2, 3, ... 으로 증가하며, 문제의 예시에서는 루트 노드의 높이가 4가 됩니다.

현재 노드의 깊이를 d, 트리의 최대 깊이를 D, 현재 노드의 높이를 h, 트리의 최대 깊이를 H 라고 하면 다음과 같이 변환됩니다.

h = D - d

d = H - h + 1

높이가 h인 부모 노드와 그 자식 노드 사이의 거리는 2의 (h-1)제곱이 됩니다.

from math import log, floor

def trav(idx, x, h):
    if idx >= len(btree) or btree[idx] is '.':
        return

    trav(idx*2, x - 2**(h-1), h-1)
    print(btree[idx], x, H-h+1)
    trav(idx*2+1, x + 2**(h-1), h-1)

btree = " nkucmp.ae...q....dg"
H = floor(log(len(btree) - 1, 2))  # 최대 높이(root의 높이). 
trav(1, 2**H - 1, H)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

이진트리 x 3
연관 문제

언어별 풀이 현황
전 체 x 4
기 타 x 1
ruby x 1
python x 2