[자료구조] 7-1. 트리의 개념

지금까지 배운 자료구조는 배열, 연결 리스트, 스택, 큐 등이 있었다. 공통점은 다들 리스트형, 선형 자료 구조였다는 것이다. 따라서 모든 원소는 인덱스에 대응되어 순서대로 찾아나갈 수 있다.

선형 자료구조는 항상 그 순서를 유지한다. i-1과 i의 관계가 i와 i+1의 관계와도 동일하다. 가나다 순이거나 123 순이거나.

이것이 바로 선형 자료 구조의 한계이다. 2개 이상의 관계를 표현하기가 어렵다.

만약 위의 데이터를 아래처럼 한 줄로 정렬한다면 어떤 관계는 부자고 어떤 관계는 형제인 것처럼 관계가 일정하지 않은 것을 볼 수 있다.

이렇게 일정하지 않은 관계를 족보식으로 표현하면 부모-자식 관계라는 일정한 관계로 만들 수 있다. 일차원적으로 늘어놓지 않고 이차원적으로 구성을 가져오면 단일한 관계로 모든 원소를 표현할 수 있게 된다.

다른 예를 들어보자. 내가 노래를 들기 위해선 어떻게 찾아야 할까?

내 폴더 안에는 그림, 문서, 음악 폴더가 있다. 그럼 나는 음악 폴더에서 찾을 수 있을 것이다.

그리고 재즈 폴더에서 찾을 수 있을 것이다. 

이 폴더들은 모두 포함 관계라는 단일한 관계로 표현되어 있다.

만약 점심을 정해야한다고 생각해보자. 이 문제를 구조적으로 접근해보자. 일단 시간이 많은지 부터 점검을 해보자.

시간이 많다면 식대가 충분한지, 없다면 교내 패스트푸드 점으로 가면 된다.

돈이 많으면 비싼 곳, 아니면 학교 앞으로 간다.

그럼 이 3개의 예의 공통점을 생각해보자.

이 사례들은 모두 계층구조를 가지고 있다.

공통점을 정리해보자면,

1. 하나의 근원에서 시작한다.

2. 한 노드에서 여러 개의 노드로 전파된다.

3. 한 번 내려갔으면 다시 올라오는 길은 없다. 즉, 사이클 경로가 없다.

이 구조의 이름은 트리 구조라고 한다.

트리의 정의를 엄밀하게 이야기하자면,

1. 루트라는 특별한 노드가 존재한다.

2. 모든 노드는 부모 자식 관계라는 1:! 관계에 재귀적으로 연결되어 있다.

3. 순환 경로(cycle path)가 없다.

이 세가지 속성을 만족할 때의 노드와 엣지의 집합을 트리라고 한다.

그림상의 동그라미는 노드 또는 버텍스라고 한다. 하나의 정보 단위, 저장 단위가 된다. 클래스든, 숫자든 하나의 단위를 노드라고 부른다. 그림은 알파벳 하나를 저장하며 A부터 M까지 존재하는 노드다.

엣지는 연결된 노드의 쌍을 말한다. 그래서 엣지를 부를 때 A, B(에이 콤마 비)라고 부른다. 하지만 A, G라고 부르지는 않는다. 하나의 엣지로 연결되어 있지 않기 때문이다.

최상위 노드에 있는 것을 루트 노드라고 부른다. 부모 노드가 없는 노드이다. 그림에서는 A를 의미한다.

리프 노드는 자식 노드가 없는 것이다. K, L, F, G, M, I, J를 의미한다.

인터널 노드는 리프 노드가 아닌 모든 노드다.

부모 노드는 반드시 'x는 y의 parent node다' 라고 부른다. 'x는 parent node다'라고 하지 않는다. 서로 연결된 한 쌍의 노드 중에 루트에 더 가까운 노드를 어떤 노드의 페어런트라고 하기 때문이다. 그림을 보면 B와 E가 연결되어있으므로 B가 루트에 더 가까우므로 'B는 E의 페어런트 노드다' 라고 부른다.

child node는 루트에서 더 먼 로드이다. E는 B의 child node다.

sibling node는 같은 페어런트 노드를 공유하는 노드이다. 위의 트리의 경우 B, C, D는 sibling node다. E, F와 H, I, J도 그렇다.

조상 노드는 루트 노드에서 어떤 노드에 이르는 사이의 모든 노드를 말한다. 예를 들어, 루트에서 E까지 가는 경로는 A, B, E이다. A와 B는 E의 조상 노드가 된다. A에서 M까지는 A, D, H, M이다. 그래서 M의 조상 노드는 A, D, H가 된다.

후손 노드는 반대의 개념이다. A가 B의 조상 노드이면 B는 A의 후손 노드이다.

부분 트리는 어떤 트리의 한 노드를 루트 노드로 두고, 이 트리의 정의를 만족시키는 노드와 엣지의 집합을 의미한다.

노드의 디그리는 한 노드가 갖는 자식 노드의 개수이다. A의 디그리는 B, C, D가 있으므로 3이 된다. B의 디그리는 2다.

트리의 디그리는 한 트리에 속한 노드들의 디그리 중 최댓값을 의미한다. K와 L의 경우 트리의 디그리는 0이다. C H는 1, B E는 2,  A D는 3이 된다.

바이너리 트리는 디그리가 2다. 터너리 트리는 디그리가 3, K-ary 트리는 디그리가 K인 것을 말한다. 우리는 바이너리 트리를 가장 많이 사용하게 된다.

깊이를 정의하는 방법에는 2가지가 있다. 루트 또는 리프를 기준으로 하는데 여기서는 루트부터 얘기해보겠다.

루트 노드의 뎁스를 1로 설정하면 차일드 노드는 페어런트 노드의 뎁스+1 이라고 정의한다. 그러면 C의 뎁스는 루트 노드의 뎁스가 1이니까 +1을 하면 2가 된다. G의 뎁스는 페어런트인 C가 2니까 +1을 해서 3이 된다.

리프 노드로부터의 맥시멈 디스턴스로 정의하는 교재도 있다. 트리의 깊이 또는 높이는 노드가 가진 뎁스의 최댓값으로 정의한다. 그림의 경우는 A B E K까지 내려가므로 뎁스는 4가 된다.

이러한 트리를 이용해 어떤 자료 구조에 이용할까? 자기 자신이 저장하고 있는 데이터의 공간 + 자식 노드의 개수 + 자식 노드 각각의 포인터를 저장해야한다.

그래서 이와 같은 자료구조를 갖는다. data는 내가 저장할 데이터, n_childs는 노드의 개수, *childs는 노드들에 대한 포인터의 배열이다.

참고) *이 붙으면 동적 배열을 의미한다.

만약 위와 같은 그림의, 노드 3개를 가진 트리가 있다면, 실제 메모리 상에서는 각각 A를 저장하는 노드, B를 저장하는 노드, C를 저장하는 노드...이렇게 저장이 될 것이다. 거기엔 300번지, 500번지, 900번지라는 주소가 붙는다.

B와 C는 차일드 노드가 없기 떄문에 n_childs는 0이다. 하지만 A는 B와 C라는 2개의 차일드를 가지고 있으므로 그들의 주소를 저장해야 한다.

그림처럼 B는 300번지, C는 900번지임을 저장해놓는다.

이전까지 배운 알고리즘은 자료를 효율적으로 관리한다는 점에서 추가, 제거, 검색 연산을 제일 많이 쓴다고 말했다. 그럼 트리는 어떻게 자료를 효율적으로 사용할까?

트리의 원소를 찾는 기본 탐색 알고리즘으로는 BFS와 DFS가 있다.

그 중에서 디그리가 2인 바이너리 트리에 대해서 공부할 것이다.

그 후에는 바이너리 트리 중 특이한 성질을 가진 바이너리 서치 트리를 공부한다. 바이너리 서치 트리는 리스트보다 원소를 더 잘 검색하는 구조다. 그 중에서도 특수한 경우로 균형 이진 검색 트리를 배울 것이다.

그 다음에는 힙이라는 또 다른 형태의 이진 트리를 배운다. 이 이진 트리는 TOP을 찾는 연산을 리스트보다 잘한다.

최종적으로 이진 탐색 트리와 힙이 실제 검색 성능이 좋고 추가와 제거가 효율적이라는 것을 배우게 될 것이다.