트리 (Tree)

트리문제는 풀어도 풀어도 헷갈리고 어렵다...

상성이 잘 안맞는 것 같고.. 어떻게 풀고 보면 다른 사람들보다 코드 길이가 좀 많이 길고...

더 많이 풀면 해결 되겠지...

---

트리는 일종의 그래프이다. 근데 이제 사이클이 존재하지 않는. 예를 들어,

이것은 트리이다. 사이클이 없기 때문이다. 그러나 선을 하나 더 추가해서

이렇게 순환하게 만들어 버리면 트리가 아니다.

 

트리는 '루트, 부모, 자식' 이렇게 3가지의 개념만 알면 사실 기본은 끝이다.

추가로 단말노드(Terminal node or Leaf node)와 비-단말노드(Non-terminal node)라는 개념도 있는데,

이 개념들에 대해 이해하려면 간단하게 족보를 생각해보자.

가문의 족보라는것은 조상부터 대대로 내려온다. 뭐 1대손.. 2대손.. 이렇게 내려오는데,

여기서 1대손. 더이상 위로 올라갈곳이 없는 곳에 도착하면 이 사람이 Root Node이다.

그 아래로 2대손은 1대손의 자식노드이면서 3대손의 부모노드이고, 3대손은 2대손의 자식노드면서 4대손의 부모노드고...

이렇게 반복되다가 내가 있는 곳 까지 내려오면, 나는 내 부모님의 자식노드 이지만 나는 자식노드가 없다.

이렇게 자식노드가 없는 노드는 단말노드라고 하고 보통 Leaf node로 부르는데,

트리가 퍼져나가는게 나뭇가지 같고, 그 끝에 있어서 나뭇잎이라고 부르는 것 같다.

 

추가적으로, 부모노드는 여러 자식을 가질 수 있지만, 자식노드는 단 한개의 부모만 가져야한다.

 

일반적으로 부모 노드가 자식노드를 최대로 2개까지 가지고, 이를 이진 트리라고 한다.

이런 트리를 주로 사용하는 이유는 지난 게시글에서 본 Heap Tree등을 보면 예상이 갈 수도 있는데,

값을 정렬해서 보관하면서 시간복잡도가 가장 빠른 구조이기 때문이다.

이거에 대한 내용은 내 블로그 2학년때 썼던 알고리즘 수업 복습하던 쪽가면 아마 있을테니 대충 생략..

 

PS에서 트리는 진짜 다양하게 나오는데, 트리에서 주로 사용되는 알고리즘 중에 어려웠고 아직도 헷갈리는 두 개를 골라봤다.

 

1. Union-Find

Union-Find는 간선데이터들을 입력받았을 때, 그 간선 데이터들로 트리를 만들면서 순환도 탐색이 가능한 방식이다.

각 노드에 매칭되는 일차원 배열의 값들이 자신이 가리키는 부모 노드의 정보를 담고, 이를 타고타고 올라가 루트노드까지 찾을 수 있고, 이를 통해 트리 구조를 표현한다.

또한 트리를 구성하는 중 새로 연결하는 노드 2개의 최고 부모가 같다면 순환일 것이다.

 

일반적으로 배열을 초기화하면 값이 0으로 저장되기 때문에, 처음에는 모든 노드가 0번을 가리키고 있다.

이러한 성질을 이용하기 위해, 보통 배열의 크기는 노드의 개수+1로 할당한후, key 1부터 사용한다.

 

여기서 (1, 2)와 (3, 4)라는 간선 데이터를 넣으면

이렇게 1,3 노드는 부모가 없는 루트노드이고, 2,4 노드는 각각 1,3을 부모노드로 삼는 자식노드가 된다.

이 경우 이 4개의 노드는 총 2개의 트리를 형성한다고 볼 수 있다.

이때, Union-find 배열은 [0, 0, 1, 0, 3]이 될 것이다.

 

그럼 여기에 추가로 (1, 3), (3, 2)의 순서로 간선 데이터를 추가해보겠다.

먼저, (1, 3) 간선을 추가할 때는 괜찮았다.

부모를 찾아 올라가면 Union[1] = 0, Union[3] = 0이였으므로, 서로 다른 트리였고, 간선 연결에 문제가 발생하지 않았다.

그러나 (3, 2)를 추가할 때, Union[3] = 0이였지만, Union[2] = 1, Union[1] = 3 이여서 순환이 생겨버렸고, 더이상 트리가 아니다.

노드의 개수가 적어서 정확하게 보여지지는 않는데, 노드 N의 루트노드를 찾는 것을 getParent(N)라고 하고,

간선 (A, B)를 연결할 때, getParent(A) == getParent(B) 혹은, getParent(A) == B || A == getParent(B)이면 해당 간선이 순환을 만드는 간선이라는 뜻이 될 것이다.

 

Union-Find는 기본적으로 트리구조를 형성하는 방법인데, 주는 데이터 순서가 정렬되어있지 않다면,

부모 노드를 두 개 지정하게 될 수도 있다. 이를 위한 예외가 필요한데, 예를 들어 이런 상황이다.

다음과 같이 (1,3), (1,4), (2,5), (2,6)의 간선을 가지는 6개의 노드가 있다고 해보자.

현재의 Union-Find 배열은 [0, 0, 0, 1, 1, 2, 2] 일 것이다.

여기서 (5,4)로 간선을 만들면 어떻게 될까? 일반적인 규칙에 따르면 Union[4] = 5를 해야할 것이다.

그러나 이미 Union[4] = 1이기 때문에, 이렇게 값을 변경해버리면, 1번 노드를 루트로 갖는 트리가 단절되어버릴 것이다.

그럼 어떻게 해야할까?

트리를 병합해야한다. 그 방법은 한 쪽의 부모-자식 관계를 뒤집어버리면 된다.

(4,5)를 연결하면서, 1의 부모를 4로 바꾸면 2를 루트로 하는 하나의 트리로 바뀔 것이다.

 

이 방법은 재귀적으로, 새로운 자식노드의 부모로 탐색해나가면 된다.

대충 재귀적으로 이런 함수가 될 것이다.

int reverse(T[] tree, int key) {
    return tree[key] > 0
        ? tree[reverse(tree, tree[key])] = key
        : key;
}

만약, 내 부모노드가 0이 아니라면 (내가 Root가 아니라면), 내 부모노드는 나를 부모로 한다.

라는 내용을 재귀적으로 반복하는 것이다.

위의 트리 그림에서 이 함수를 사용하면

reverse(tree, 4);
-> tree[reverse(tree, 1)] = 4; // 루트이므로 1 반환 ( 부모가 자신을 가리키게 함 )

역시나 노드 개수가 적어서 명확하게 보이지는 않지만, 이런 방식으로 부모-자식 관계를 뒤집을 수 있다.

그리고 이 reverse함수는 병합 되기 전의 트리에서만 작동되므로, 작동이 완료된 뒤, tree[4] = 5까지 해주면 된다.

 

맨날 트리 문제를 풀면서 이 부모가 0이 아닌 수로 다를 경우 뒤집어서 병합해야 한다는 것을 잊고 문제를 틀린다.

그리고, PS에서 트리는 노드 개수자체가 너무 많아져서 머리속에 그림도 잘 안그려져서 더 그런것 같다..

 

---

두 번째로 세그먼트트리인데...

세그먼트 트리는 부분합 등을 더 편하게 구하기 위해 사용하는 자료구조이다.

예를 들어, [1 ... 8]이라는 배열이 있다고 해보자, 이 배열의 모든 구간의 합을 구하는 방법은 뭐가 있을까?

가장 쉽게 생각나는 방법은 그냥 순차적으로 1부터 8을 모두 탐색해서 더하는 방법이다. 이 방법의 시간 복잡도는 O(N)이다.

N의 크기가 작고, 계산 횟수가 적으면 이렇게 계산하더라도 아무 문제가 없겠지만..

그렇지 않은 상황을 위해 세그먼트 트리가 존재한다.

 

세그먼트트리는 자신의 모든 자식노드의 값을 합한 값을 가지는 부모노드로 이루어진 트리이다.

위의 [1 ... 8]배열을 통해 예로 들면, 이 트리에서는 1~8 값이 모두 Leaf 노드로 가고,

이 노드들을 가지는 부모노드들이 자식들의 합을 값으로 가지도록 새롭게 생성된다는 말이다.

설명하는 머리가 없어서 그림으로 보도록하자.

 

아래의 1~8 빨간 숫자가 입력값이고, 위의 파란 숫자들이 그 부모노드로 생성된 것이다.

대충 이런 구조를 가지는 트리인데, 먼저 만드는 방법을 보자.

 

트리의 크기는 위에서부터 내려오는 깊이(depth, height)에 따라 크기가 2^(depth-1)의 크기를 가진다.

세그먼트 트리는 입력값들을 모두 Leaf노드로 받을 수 있을 만큼 커야하므로, 제일 아래쪽의 길이가 입력값들보다 큰 2의 지수승 중 가장 작은 수 일 것이다.

이 수를 구하는 방법은 log(size) / log(2) 이다. 밑을 2로하는 log입력값의 수 인데, 위의 경우 log2(8)이므로 3이다.

그러면 부모노드를 담는 크기가 3이므로, 입력값까지 모두 담기 위해서는 2^(3+1)=16개의 노드를 갖는 트리가 필요할 것이다.

 

충분한 크기의 트리를 만들었다면 이제 값들을 입력해야한다.

이때 트리는 1차원 배열에 구현하는데, Union-find에서 했던 것 처럼 배열의 key는 1부터 시작한다.

그렇게 하면, 각 노드가 자신의 key에 /2를 하면 부모노드로 가고, *2, *2+1을 하면 자식노드로 가기 때문이다.

이 성질을 이용해, 값을 입력할 때도, 부모노드에 모두 더하면서 입력한다.

void push(int[] tree, int key, int data) {
    tree[key] = data;
    for(int parent = key/2 ; parent >= 1 ; parent /= 2) tree[parent] += data;
}

이렇게 하면, key에 데이터를 입력하면서, 모든 부모노드에 자신의 값을 더할 수 있을 것이다.

이제 세그먼트 트리를 만들었으니, 세그먼트 트리를 이용해 부분 합을 구해보자.

 

먼저 우리가 필요한 값은 내가 합을 구하고자 하는 범위와 부모 노드의 크기이다.

예시로 합의 범위는 2~7로 하고, 부모 노드의 크기는 위에서 구한 8이다. (2^(log2(8)))

먼저 루트부터 탐색한다. 루트의 범위는 '0 <= x < 8'이다.

seq #1
'root' 탐색: 범위 [0 <= x < 8]
(자식 : '0 <= x < 4', '4 <= x < 8')
부분 합 범위 : 1 < x < 7
부분 합 범위가 '0 <= x < 4'와 겹치는 곳이 있다.

seq #1-1
'root-L' 탐색 : 범위 [0 <= x < 4]
(자식 : '0 <= x < 2', '2 <= x < 4')
부분 합 범위 : 1 < x < 7
'0 <= x < 2'와는 겹치는 곳이 없다.
'2 <= x < 4'는 부분 합 범위에 포함된다.
return root-LR;

seq #1
부분 합 범위가 '4 <= x < 8'과 겹치는 곳이 있다.

seq #2-1
'root-R' 탐색: 범위 [4 <= x < 8]
(자식 : '4 <= x < 6', '6 <= x < 8')
부분 합 범위 : 1 < x < 7
'4 <= x < 6'은 부분 합 범위에 포함된다.
'6 <= x < 7'은 겹치는 곳이 있다.

seq #2-1-1
'root-R-R' 탐색: 범위 [6 <= x < 8]
(자식 : '6 <= x < 7', '7 <= x < 8')
부분 합 범위 : 1 < x < 7
'6 <= x < 7'은 부분 합 범위에 포함된다.
'7 <= x < 8'은 겹치는 곳이 없다.
return root-RRL;

seq #2-1
return root-RL + root-RRL;

seq #1
return root-LR + root-RL + root-RRL;

뭔가 글로 쓰다보니까 오류가 있을 수도 있는데, 찾으면 댓글 부탁드립니다.

아무튼 이런 구조로 위에서부터 범위를 탐색하면서 재귀적으로 합을 구하는 방식이다.

 

이를 코드로 나타내면

long sum(long[] tree, int start, int end, int offset, int range) {
    int leapStart = tree.length / 2, halfRange = range / 2;

    if(halfRange == 0) return tree[leapStart+offset];
    else if(end < offset || offset + range < start) return 0;
    else if (start <= offset && offset + range <= end)  return tree[(leapStart + offset) / range]; 

    long sum = 0;
    if (offset + halfRange <= end) sum += sum(tree, start, end, offset + halfRange, halfRange); 
    if (start < offset + halfRange) sum += sum(tree, start, end, offset, halfRange);
    return sum;
}

대충 이런 느낌이 된다.

위의 작동을 이 함수에 넣으면 sum(tree, 2-1, 7, 0, 8); 이다.

 

하도 학기말이라 과제+기말준비로 머리아파서 후반부로 갈수록 좀 이상해졌다는 느낌이 있긴 한데,

일단은 마무리..