[자료구조] 트리(Tree)의 개념, 종류 그리고 순회

Published in

Quantum Ant

11 min readSep 17, 2019

이번 학기 알고리즘 수업 때 배운 내용을 정리하기 위해 포스팅을 준비했다. 기존에 C언어로 쉽게 풀어쓴 자료구조로 공부하여 정리된 포스팅이 있으나, 필자는 해당 책(개정2판)과 알고리즘(로버트 세지윅, 케빈 웨인 저) 책 또한 참고할 예정이다. 책 알고리즘은 자바로 표현하고 있어 필자의 학습에 여러모로 도움이 될 것으로 보인다.

1. 개념 및 용어 정리

트리(tree)란 계층적인 자료를 표현하는 데 이용되는 자료구조이다. 실제 나무를 거꾸로 한 것과 같은 모양을 하고 있기 때문에 트리라고 부른다.

노드(node) : 트리의 구성요소로 트리는 한 개 이상의 노드로 이루어진 유한 집합

가장 상위 노드를 루트(root) 노드, 나머지 노드를 서브 트리(subtree)라고 부른다. 위의 그림에서 루트 노드는 A, 나머지 노드는 서브 트리이다.
서브 트리에서도 다시 루트와 서브 트리로 나눌 수 있다. 예를 들면 서브 트리 { D, H, I, J }에서 루트 노드는 D, 나머지 노드는 서브 트리가 된다.
노드 간의 관계는 인간 관계와 동일하게 나타난다. 예를 들면 A는 D의 부모 노드이자, H, I, J 의 조상 노드이다. D는 A의 자식 노드이고, H, I, J는 형제 관계이다.
또한, 자식 노드가 없는 노드를 단말 노드(leaf node), 자식 노드가 있다면 비단말 노드(nonterminal node)라고 부른다.

간선(edge) : 루트와 서브트리를 연결하는 선
차수(edge) : 노드가 가지고 있는 자식 노드의 개수

예를 들어, C의 차수는 1, B의 차수는 2, D의 차수는 3임을 알 수 있다. 이로 미루어 볼 때 단말 노드는 차수가 0인 노드이다.
트리의 차수는 트리가 가지고 있는 노드의 차수 중 가장 큰 차수로, 위 트리에서는 3이다.

레벨(level) : 각 층에 번호를 매기는 것으로, 루트의 레벨은 1이며 내려갈 때마다 레벨이 증가한다.
트리의 높이(height) : 트리가 가지고 있는 최대 레벨

위 트리의 높이는 3이다.

포리스트(forest) : 트리들의 집합

트리를 컴퓨터 메모리 상에서 표현하는 방법은 여러 가지가 있을 수 있지만, 각 노드가 데이터 필드와 링크 필드를 가지게 하는 방식은 노드의 크기가 일정하지 않아 프로그램이 복잡하게 될 수 있다. 따라서, 이어질 내용은 이진 트리만 다루게 된다.

2. 이진 트리

2.1 정의

이진 트리(binary tree)는 모든 노드가 2개의 서브 트리를 가지고 있는 트리로, 트리 중에서 가장 많이 쓰이며, 서브 트리 또한 모두 이진 트리여야 하기 때문에 순환적으로 정의되고 있음을 알 수 있다. 이진 트리의 서브 트리는 공집합일 수 있다. 즉, 0~2개의 자식 노드가 존재할 수 있고, 모든 노드의 차수는 2 이하이다. 이진 트리에는 서브 트리간의 순서가 존재해 왼쪽 서브 트리와 오른쪽 서브 트리는 구별된다.

이진 트리와 일반 트리의 차이점

2.2 성질

n개의 노드를 가진 이진 트리는 n-1개의 간선을 가진다.

부모-자식 간 간선은 1개씩 존재하는데, 루트 노드는 부모 노드가 없으므로 노드 개수보다 간선이 1개 적다.

높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가진다.

한 레벨에 최소 하나의 노드는 존재해야 하므로, 최소 노드를 가지는 경우 높이만큼의 노드를 가진다.
하나의 노드는 최대 2개의 자식을 가지기 때문에, 레벨 i에서의 노드는 최대 이다. 따라서 전체 노드의 개수는 ∑\sum_{i=1}^h 2^{i-1} = 2^h-1이 된다.

n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 ┌log₂(n+1)┐이 된다.

앞서 설명한 것처럼 한 레벨에 최소 하나의 노드가 존재하므로 최대 높이는 n이다. 마찬가지로, 높이 h의 이진 트리가 가지는 최대 노드 개수는 2^h-1이다. 따라서 n≤2^h-1의 부등식이 성립하고, 양변에 log를 취하면 h≥log₂(n+1)이 된다. 여기서 h는 정수이기 때문에 소수점을 올린 h≥┌log₂(n+1)┐이 성립한다.

2.3 분류

이진 트리는 형태에 따라 다음과 같이 분류할 수 있다.

포화 이진 트리(full binary tree) : 각 레벨에 노드가 꽉 차 있는 이진 트리로, 각 노드에 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙일 수 있다. 부여된 번호는 항상 일정하다.
완전 이진 트리(complete binary tree) : 높이가 k일 때, 레벨 1부터 k-1까지는 노드가 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리로, 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만, 중간에 빈 곳이 있으면 안 된다.
기타 이진 트리

포화 이진 트리와 완전 이진 트리의 노드 번호는 1:1 대응하며, 두 트리의 관계는 다음과 같다.

2.4 표현

배열 표현법

배열을 이용하는 방법은 주로 포화 이진 트리나 완전 이진 트리의 경우 많이 쓰인다. 이외 이진 트리도 저장이 불가능 한 것은 아니지만 그림에서 볼 수 있는 것처럼 중간중간 빈 곳이 있어 메모리 공간의 낭비가 발생한다.

부모와 자식의 인덱스 사이의 관계

노드 i의 부모 노드 인덱스 = └i/2┘
노드 i의 왼쪽 자식 노드 인덱스 = 2*i
노드 i의 오른쪽 노드 인덱스 = 2*i+1

2. 링크 표현법

링크 표현법에서는 노드가 구조체로 표현되고, 각 노드가 가진 포인터를 이용해 노드와 노드를 연결하는 방법이다. 이진 트리를 링크 표현법으로 표현하면, 데이터 필드 1개와 양쪽 자식 노드 각각을 가리키는 2개의 포인터 필드를 가진다.

링크 표현법으로 생성된 이진 트리

2.5 순회

이진 트리를 순회한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다. 트리를 사용하는 목적은 트리의 노드에 자료를 저장하고 필요에 따라서 이 자료를 처리하기 위함이다. 따라서 트리가 가지고 있는 자료를 순차적으로 순회하는 것은 이진 트리에서 중요한 연산이다. 스택이나 큐는 선형적으로 자료를 저장하기 때문에 순회하는 방법이 하나(LIFO/FIFO) 뿐이었지만, 트리는 여러 가지 순서로 자료에 접근할 수 있다.

순회 방법에는 루트를 방문하는 순서에 따라

V : Visited, L : Left, R : Right라고 하자.

전위 순회(preorder) : VLR
중위 순회(inorder) : LVR
후위 순회(postorder) : LRV

로 나눌 수 있다. 항상 왼쪽 서브 트리를 오른쪽 서브 트리에 앞서 방문한다고 가정하여 정리했다.

이진 트리에서 각 서브 트리 또한 이진 트리이므로 같은 방법을 적용해 순회할 수 있다. 문제의 구조는 같지만 크기가 작아지는 경우 “순환”을 적용할 수 있다는 점을 이용하자.

전위 순회

preorder(x) if x != NULL // 노드 x가 NULL이면 더 이상 순환 호출을 하지 않는다.
 then print x->data; // x의 데이터를 출력한다.
 preorder(x->left); // x의 왼쪽 서브 트리를 순환 호출하여 방문한다.
 preorder(x->right); // x의 오른쪽 서브 트리를 순환 호출하여 방문한다.

위는 전위 순회의 의사 코드이다. 실제 구현하기 전에 의사 코드로 작성하는 것은 사고를 명확히 정립함으로써 프로그램 설계 시 많은 도움이 된다.

코드 검토를 쉽게 함으로써 지속적인 프로그램 개선에 도움이 된다.
코드를 다 짜 놓은 후에 수정하는 것보다 의사코드 설계 단계에서 미리 오류를 수정함으로써 코드 수정을 용이하게 만들어준다. 즉, 유지보수가 쉽다.
학년이 올라가고 공부량이 늘어가면서 다양한 언어를 배우게 되면서 사용하는 언어의 문법이 헷갈릴 수 있다. 그럴 때 의사 코드로 먼저 논리를 정리한 다음, 문법만 구글링을 통해 찾아 작성하면 된다.

간단한 프로그램을 구현할 때는 필요성을 체감하기 어려울 수 있지만, 점차 큰 프로그램을 만들면서 필요성을 느낄 것이다. 그 전에 미리 의사코드를 사용해 정리하는 습관을 들인다면, 구현 시간을 단축하고 논리적인 사고력을 기르는데 도움이 될 것이라는 것이 필자의 생각이다. 그러니 지금부터라도 무작정 바로 코드를 작성하기 보다는, 의사 코드로 어떻게 코드를 짤지 정리한 다음에 구현하는 습관을 기르자.

방문 순서는 다음과 같다.

루트인 12를 방문해 출력한 후, 왼쪽 서브트리를 순환 호출해 방문한다. 왼쪽 서브트리의 루트인 2를 방문해 출력한 후, 다시 그의 왼쪽 서브트리를 순환 호출해 방문한다. 이 과정을 반복하다가 3을 출력 후 그의 왼쪽 서브트리의 루트를 출력하려고 할 때, 그 값이 NULL임을 알 수 있다. 그러면 더 이상 순환 호출을 하지 않고 3의 오른쪽 서브트리의 루트를 출력한다. 그러나 이 역시도 NULL 값을 가지고 있다. 그러면 현재 루트인 6과 그의 왼쪽 서브트리인 3을 모두 방문했으니 이번에는 오른쪽 서브트리의 루트인 8을 방문하고 출력한다. 8의 양쪽 서브트리는 모두 NULL이므로 2의 오른쪽 서브트리를 방문한다. 이와 같은 방식을 반복하면서 순회하는 것이 전위순회이다.

2. 중위 순회

중위 순회 의사 코드는 전위 순회에서 순서만 바꾸면 되기 때문에 따로 기재하지 않겠다.

루트 노드인 12에서 왼쪽 서브 트리가 NULL일 때까지 타고 내려와서 3의 왼쪽 자식 노드인 NULL을 방문 후 루트인 3을 출력하고 오른쪽 자식 노드인 NULL을 방문한다. 그 후 루트인 6을 방문하고 그의 오른쪽 서브 트리로 향해 같은 과정을 거치며 8을 출력한다. 지금까지 거친 과정은 2의 왼쪽 서브트리를 방문한 것이므로 루트인 2를 출력하고 그의 오른쪽 서브트리를 순회한다. 이 과정을 반복하는 것이 중위 순회이다.

3. 후위 순회

후위 순회 의사 코드 또한 전위 순회에서 순서만 바꾸면 된다.

루트 노드인 12에서 왼쪽 서브 트리가 NULL일 때까지 타고 내려와서 3의 왼쪽 자식 노드인 NULL과 오른쪽 자식 노드인 NULL을 방문 후 루트인 3을 출력한다. 그 후 6의 오른쪽 자식 노드인 8을 출력하고 루트 노드인 6을 출력한다. 6은 2의 왼쪽 자식 노드에 해당하므로 이번에는 오른쪽 자식 노드인 16을 방문해 출력하고, 루트 노드인 2를 출력한다. 이 과정을 반복하며 순회하는 것이 후위순회이다.

순서에 상관 없이 모든 노드를 방문하기만 하면 될 경우에는 어떤 순회 방법을 선택하든 상관이 없지만, 자식 노드를 먼저 처리한 다음 부모 노드를 처리해야 한다면 후위 순회를, 부모 노드를 처리한 다음에 자식 노드를 처리해야 한다면 전위 순회를 사용해야 한다.

링크 표현법으로 생성된 이진 트리의 순회

4. 레벨 순회

각 노드를 레벨 순으로 검사하는 순회 방법이다. 앞선 순회들은 순환 호출을 함으로써 간접적으로 스택을 사용한 반면, 레벨 순회는 큐를 사용하는 순회법이다. 레벨 순회 코드는 큐에 하나라도 노드가 있으면 계속 반복하는 코드로 이루어져 있다.

levelOrder(root)
 
 initalize queue; // 큐를 초기화한다.
 if(root = null) then return; // 트리 root가 NULL이면 종료한다.
 enqueue(queue, root); // 트리 root의 루트 노드를 큐에 삽입한다.
 while isEmpty(equeue) != TRUE do // 큐가 공백 상태가 될 때까지 계속 반복
 x ← dequeue(queue); // 큐에서 맨 처음에 있는 노드를 x로 가져온다.
 print x->data; // x의 데이터 값을 출력하고
 if(x->left != NULL) then // x의 왼쪽 자식이 NULL이 아니면
 enqueue(queue, x->left); // 큐에 삽입
 if(x->right !=NULL) then // x의 오른쪽 자식이 NULL이 아니면
 enqueue(queue, x->right); // 큐에 삽입

레벨 순회를 구현하면 다음과 같다.

3. 마치며

이번 포스팅에서는 트리의 개념과 성질, 그리고 순회 방법을 간단하게 살펴보았다. 포스팅을 준비하면서 지난 학기에 배웠던 것을 상기시키고 이어서 이번 알고리즘 과제에 필요한 내용을 공부하는데 도움이 되었다. Typora에서 수식을 깔끔하게 작성해서 옮겼는데 Medium에서 LaTex 지원이 안된다는 점은 매우 매우 아쉬웠다. 순회 부분이 처음 접할 때 다소 헷갈렸던 부분이라 특별히 애니메이션으로 준비했는데, 이 글을 읽는 독자의 이해를 돕는데 도움이 되기를 바란다. 코드를 복사해서 디버깅을 하며 흐름을 따라가 보는 것도 좋다. 다음 포스팅에서는 이진 탐색 트리에 대해 정리할 것이다.