이진트리 레이아웃 #3

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

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

레이아웃 알고리즘

모든 노드에서 좌우 간격의 대칭을 유지하면서 최대한 컴팩트하게 만든다.

입출력

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

입력 예 #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 2 3
d 2 5
e 3 4
g 4 5
...

출력 예 #2

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

출력 예 #3

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

public void test() {
  Tree<Integer> t = ...;
  Tree<Point>   expected = ...;
  assertEquals(expected, layout(t));
}

확인하기

여기에서 눈으로 결과를 확인할 수 있다.

아래 입력들에 대해서 잘 동작하는지 확인해보자.

  1. qawrsxedcfvutgbyhnujmikolp
  2. qwertyuiopasdfghjklzxcvbnm
  3. afgzxtkjijbed
이진트리
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

2개의 풀이가 있습니다.

Ruby

중복(x,y위치)을 갖는 컴팩트 트리를 대칭이 되도록 오른쪽에서 살며시 당기는 방식. 중복지점을 찾고 중복노드 둘의 공통부모를 찾은 뒤 공통부모 포함 우측 노드가 대칭이 되도록 이동/반복. 2번 풀이에서 Node 구조 수정(부모노드 검색 요건) minimize(당기기) 추가.

add = ->par,node do
  par ? (node.y = par.y + 1; node.u = par.id) : (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 do
  left_x = par.x + (node == par.l ? -1 : 1) if par
  node.x = (node.l ? node.l.x + 1 : par&.x > 0 ? left_x : 1)
  node.r.x = node.x + 1 if node.r
end

minimize = ->nodes,vst do
  find_dups = -> { nodes.group_by {|e| [e.x, e.y]}.select {|_,v| v.size > 1}.first }
  while dups = find_dups[] do
    d1u, d2u = dups[1].map {|e| parent_id = nodes[e.u] }
    d1u, d2u = nodes[d1u.u], nodes[d2u.u] until d1u == d2u
    d1u.x += 1
    vst.map.with_index {|e,i| e.x += 2 if i > vst.index {|e| e.id == d1u.id } }
  end
end

layout = ->tree_str=gets.chop,visits=[] do
  Node = Struct.new(:id, :val, :x, :y, :l, :r, :u)
  nodes = tree_str.chars.map.with_index {|c,i| Node.new(i, c, 0, 1)}
  btree = nodes.reduce(&add)
  trav = ->node,par=nil do
    trav[node.l, node] if node.l
    calc_x[node, par]
    visits << node
    trav[node.r, node] if node.r
  end
  trav[btree]
  minimize[nodes, visits]
  puts visits.map {|e| [e.val, e.x, e.y].join(" ") }
end

Test

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

Output

cmd > layout.call
nkcmaedgupq
a 1 4 
c 2 3 
d 2 5 
e 3 4 
g 4 5 
k 3 2 
m 4 3 
n 5 1 
p 6 3 
q 7 4 
u 7 2  
+1 입력을 "qwertyuiopasdfghjklzxcvbnm"(qwerty 순서대로) 로 하니 트리 노드들이 중복되는 문제가 있네요 - Han Jooyung, 2016/11/29 12:18 M D
체크 감사합니다. 알려주신 케이스로 점검해보니 알고리즘에 문제가 있네요.(중복을 허용한 트리생성) - 권용훈, 2016/11/29 15:13 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

아이디어

노드의 양팔 길이가 대칭이다. 재귀적으로 현재 노드에 대해 양쪽 자식이 모두 layout이 적용된 다음 컴팩트하게 자신의 팔 길이를 결정하면 된다.

양쪽 자식들의 팔길이 대칭 맞추기

우선 양쪽 자식은 따로 계산되므로 팔 길이가 깊이별로 달라질 수 있는데, 이를 먼저 맞춰줘야 한다. 예를 들어 왼쪽 자식은 팔길이가 최종 1-2-1으로 결정되었는데, 오른쪽 자식은 1-1-2로 결정되었다면 최종은 깊이별로 더 큰 값으로 맞춰서 1-2-2가 되어야 한다.

자신의 팔길이 결정하기

그런다음 컴팩트한 팔길이를 계산하려면 왼쪽 자식의 오른쪽 프로파일(단계별 가장 큰 x값들)과 오른쪽 자식의 왼쪽 프로파일(단계별 가장 작은 x값들)을 계산하여 각 단계별로 x가 겹치지 않는 팔길이를 계산하면 된다.

결정된 팔길이에 맞춰 양쪽 자식 떨어뜨리기

결정된 팔 길이에 맞춰서 다시 자식들을 translate하는 것도 필요.

코드

재귀를 위한 도움함수 layout3를 호출한다. 이때 기준 x는 마지막에 최소 x 기준점이 1이 되도록 translate해준다. 최소 x를 찾으려면 모든 노드를 탐색해야 한다. (오른쪽 자식의 왼쪽 자식이 최소 x를 가질 수도 있으므로)

void tree_layout3(tree* t) {
    int height = tree_height(t) - 1;
    int* arms = (int*)calloc(height, sizeof(int));
    layout3(t, 0, 1, arms, height);  // arms 버퍼는 최종 결정된 팔길이를 저장한다.
    int minx = tree_fold(t, INT_MAX, tree_xmin);
    tree_translate_x(t, 1-minx);
    free(arms);
}

재귀 layout3 함수는 먼저 왼쪽 오른쪽 자식을 처리한 다음 자식들이 겹치지 않도록 양쪽으로 벌려놓는다. 팔길이 대칭을 맞춰주기 위해 재귀계산을 할때 그 결과로 레벨별 팔길이를 반환한다.(arms 반환인자)

void layout3(tree* t, int x, int y, int* arms, int n) {
    int* armsLeft = (int*)calloc(n-1, sizeof(int));
    int* armsRight = (int*)calloc(n-1, sizeof(int));

    t->x = x;
    t->y = y;

    // 먼저 재귀적으로 팔 길이를 모두 결정한다. 이 때 x에서 시작하므로 겹칠 것이다.
    if (t->left) layout3(t->left, x, y+1, armsLeft, n-1);
    if (t->right) layout3(t->right, x, y+1, armsRight, n-1);

    // 단계별 팔 길이 중 큰 쪽으로 맞춰주기
    for (int i=0; i<n-1; i++) {
        arms[i+1] = max(armsLeft[i], armsRight[i]);
    }

    if (t->left) layout3_setArms(t->left, x, arms+1);
    if (t->right) layout3_setArms(t->right, x, arms+1);

    // 여기부터 armsLeft와 armsRight는 그냥 버퍼로 사용
    for (int i=0; i<n-1; i++) {
        armsLeft[i] = INT_MIN;
        armsRight[i] = INT_MAX;
    }
    // left의 오른쪽 프로파일
    if (t->left) tree_right_profile(t->left, armsLeft);
    // right의 왼쪽 프로파일
    if (t->right) tree_left_profile(t->right, armsRight);

    // 두 프로파일이 겹치지 않도록 현재 노드의 arm을 결정
    int diff = INT_MAX;
    for (int i=0; i<n-1; i++) {
        if (armsRight[i] == INT_MAX || armsLeft[i] == INT_MIN) break;
        diff = min(diff, armsRight[i] - armsLeft[i]);
    }

    int arm = 1 + max(0, -diff / 2);

    if (t->left) tree_translate_x(t->left, -arm);
    if (t->right) tree_translate_x(t->right, arm);
    arms[0] = arm; // 현재 노드 팔길이 저장

    free(armsLeft);
    free(armsRight);
}

팔길이를 재설정하는 함수 setArms

void layout3_setArms(tree* t, int x, int* arms) {
    t->x = x;
    if (t->left) layout3_setArms(t->left, x-*arms, arms+1);
    if (t->right) layout3_setArms(t->right, x+*arms, arms+1);
}

왼쪽/오른쪽 프로파일 구하려면 모든 노드를 돌면서 x좌표의 min혹은 max를 저장하면 된다. profile은 레벨별로 최소값을 저장하기 위한 것이다.

void tree_left_profile(tree* t, int* profile) {
    *profile = min(t->x, *profile);
    if (t->left) tree_left_profile(t->left, profile+1);
    if (t->right) tree_left_profile(t->right, profile+1);
}

void tree_right_profile(tree* t, int* profile) {
    *profile = max(t->x, *profile);
    if (t->left) tree_right_profile(t->left, profile+1);
    if (t->right) tree_right_profile(t->right, profile+1);
}

마지막으로 트리 전체의 최소 x는 right profile의 min값으로 계산할 수도 있겠으나 여기서는 tree_fold 라는 재귀함수를 이용하였다.

int tree_xmin(tree* t, int l, int r) {
    return min(t->x, min(l, r));
}

int tree_fold(tree* t, int z, int (*f)(tree*,int,int)) {
    if (!t) return z;
    int l = tree_fold(t->left, z, f);
    int r = tree_fold(t->right, z, f);
    return f(t, l, r);
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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

이진트리 x 3
연관 문제

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