트리 (Tree)
나무를 닮은 자료구조.
트리 구조는 계층적인 관계를 가진 자료의 표현에 매우 유용하게 사용된다.
우선순위 큐를 효율적으로 구현하기 위해 트리가 사용되고,
의사결정 구조를 표현하기 위한 중요한 방법으로 결정 트리(decision tree)가 사용된다.
트리 관련 용어
노드(node)
트리에서 각각의 요소들이며, 트리는 하나 이상의 노드들로 이루어진다.
간선 또는 에지(edge)
노드와 노드의 연결 관계
루트(root) 노드
‘사장’과 같이 계층적인 구조에서 가장 높은 곳에 있는 노드.
| 부모(parent) 노드 | 간선으로 직접 연결된 노드 중에 상위 노드 |
| 자식(child) 노드 | 간선으로 직접 연결된 노드 중에 하위 노드 |
| 형제(sibling) 노드 | 같은 부모 노드를 가진 노드 |
| 조상(ancestor) 노드 | 어떤 노드에서 루트 노드까지의 경로상에 있는 모든 노드 |
| 자손(descendant) 노드 | 어떤 노드 하위에 연결된 모든 노드 |
| 단말(terminal, leaf) 노드 | 자식 노드가 없는 노드, 자식이 있으면 비단말 노드 |
| 노드의 차수(degree) | 노드가 가지고 있는 자식의 수, 단말 노드는 항상 0 |
| 트리의 차수 | 트리에 포함된 모든 노드의 차수 중에서 가장 큰 수 |
| 레벨(level) | 트리의 각층에 번호를 매기는 것. 루트 노드의 레벨은 1이고 한 층씩 내려갈수록 레벨은 1씩 증가 |
| 트리의 높이(height) | 트리가 가지고 있는 최대 레벨 |
트리의 모든 노드는 자신을 루트로 하는 하나의 서브 트리를 대표한다.
트리의 표현 방법
중첩된 집합
트리가 서브 트리들의 집합이라는 것을 잘 나타낼 수 있다.
트리의 루트와 서브 트리를 중첩된 괄호로 묶어 표현하는 방법
이를 테면, A가 루트이고 3개의 자식 B, C, D를 갖는 트리를 (A (B…)(C…)(D…))와 같이 나타내는 것.
이떄 서브 트리에도 같은 표현 방법이 적용되어야 한다.
이를 테면, 트리를 하나의 문자열처럼 표현하는 것.
그러나 이것만으로 트리의 구조를 직관적으로 이해하기에는 다소 어려움이 있다.
들여쓰기
자료가 계층적인 구조를 갖는 것을 잘 나타내는데, 윈도 탐색기에서 폴더와 파일을 나타내기 위해 흔히 사용.
일반 트리의 표현
자식의 개수에 제한이 없는 트리를 일반 트리(general tree)라고 부른다.
이러한 표현 방법에는 2가지가 존재한다.
N-링크 표현
차수가 N인 노드가 N개의 링크를 갖도록 허용하는 것.
이 경우, 각 노드는 하나의 데이터 필드와 자식 노드 개수만큼의 링크를 갖는다.
그러나 노드마다 링크의 개수가 다르다는 문제가 있다.
왼쪽 자식 – 오른쪽 형제 표현
노드가 N개가 아니라 2개의 링크만을 갖도록 하는 방법.
하나의 링크는 왼쪽 자식(첫 번째 자식, child)을 가리키고, 다른 하나는 오른쪽 형제(다음 형제, sibling)을 가리키기 위해 사용한다.
그러나 표현이 복잡하고 특히 루트인 A에서 G까지 찾아가는 과정에서 필요 없이 많은 노드를 거쳐야하는 문제가 있다.
이진 트리
모든 노드가 최대 2개의 자식막은 가질 수 있는 트리로써, 즉, 모든 노드의 차수가 2 이하로 제한된 트리이다.
이때 자식 사이에도 순서가 존재하는데, 왼쪽 자식과 오른쪽 자식은 반드시 구별되어야 한다.
이러한 구조를 이용한 이진 탐색 트리(binary search tree), 우선순위 큐를 효과적으로 구현하는 힙 트리(heap tree), 수식을 트리 형태로 표현하여 계산하는 수식 트리(expression tree) 등이 모두 이진 트리의 대표적인 예이다.
이진 트리의 종류
이진 트리는 레벨과 노드 수의 관계에 따라 포화 이진 트리와 완전 이진 트리를 정의할 수 있다.
또한, 서브 트리의 높이에 ‘균형’의 개념을 적용하면 균형 이진 트리를 정의할 수 있다.
포화 이진 트리(full binary tree)
트리의 각 레벨에 노드가 꽉 차있는 이진 트리를 말한다.
노드가 꽉 차있기에 트리의 높이를 알면 전체 노드의 수를 쉽게 계산할 수 있다.
전체 노드 개수: 2의 k승 – 1
또한, 포화 이진 트리는 각 노드에 순서대로 번호를 붙일 수도 있다.
위에서 아래로 내려오면서 왼쪽에서 오른쪽으로 순서대로 번호를 붙이는데, 이 번호는 항상 일정하다.
완전 이진 트리(complete binary tree)
높이가 k인 트리에서 레벨 1부터 k-1까지는 노드가 모두 채워져있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져있는 이진 트리를 의미한다.
마지막 레벨에서는 노드가 꽉 차있지 않아도 되지만 중간에 빈곳이 있으면 안된다.
따라서 포화 이진 트리는 완전 이진 트리이지만, 그 역은 항상 성립하지 않는다.
대표적으로 힙(heap)이 완전 이진 트리의 예이다.
균형 이진 트리(balanced binary tree)
높이균형 이진 트리(height-balaned binary tree)라고도 하며,
모든 노드에서 좌우 서브 트리의 높이 차이가 1이하인 트리를 의미한다.
이를 테면, 모든 노드에서 좌우 서브 트리의 높이가 1이하인 트리가 되겠다.
경사 트리/경사 인진 트리
다른 노드는 모두 균형 잡혀 있지만, 노드 하나가 좌우 서브 트리의 높이가 2인 경우의 트리
이진 트리의 표현 방법
배열 구조 표현
포화 이진 트리에서 노드에 번호를 붙이는 것을 그대로 배열의 인덱스로 사용하는 것.
과정:
1. 트리의 높이를 구해 배열을 할당한다. 이를 테면, 높이가 k이면 길이가 2의 k승 -1인 배열이 필요하다.
2. 포화 이진 트리의 번호를 인덱스로 사용하여 배열에 노드들을 저장한다.
이 배열 구조를 통한 표현 방법은 포화 이진 트리나 완전 이진 트리에 가장 적합하지만, 일반 이진 트리도 표현할 수 있다.
그러나, 심한 경사 트리의 경우에는 배열 항목 사이에 사용하지 않는 빈칸이 많이 발생하여 메모리 낭비가 심해질 수 있다.
또, 이 표현법에서는 어떤 노드의 인덱스를 안다면 부모 노드나 자식 노드의 인덱스를 다음과 같이 쉽게 게산할 수 있다.
노드 i의 부모 노드 인덱스 = i/2
노드 i의 왼쪽 자식 노드 인덱스 = 2i
노드 i의 오른쪽 자식 노드 인덱스 = 2i+1
이처럼 배열 표현법은 간단하나, 경사 트리에서 기억공간을 낭비할 수 있으며,
배열의 크기에 따라 표현 가능한 트리의 높이가 제한된다는 단점이 있다.
연결된 구조 표현: 링크 표현법
이진 트리를 위하 노드는 2개의 링크가 필요한데, 이들은 각각 왼쪽과 오른쪽 자식 노드를 가리킨다.
이 때, 좌우링크는 반드시 구별되어야 한다.
부모와 자식의 관계를 나타내기 위해서는 간선을 화살표로 나타내는 것이 더 정확하지만,
화살표가 없이 연결된 경우에는 위쪽이 부모 노드, 아래쪽이 자식 노드이다.
이진 트리의 연산
순회
트리의 모든 노드를 한번씩 방문하는 것.
이진 트리의 표준 순회
기본적인 순회 방법은 전위, 중위, 후위로 나눌 수 있는데, 이를 이진 트리의 표준 순회라고 한다.
이들은 루트와 왼쪽 서브 트리, 오른쪽 서브 트리를 각각 어떤 순서로 방문하느냐에 따라 구분된다.
루트를 방문하는 작업을 V, 왼쪽과 어른쪽 서브 트리를 방문하는 작업을 각각 L과 R이라고 가정하자.
- 전위순회(preorder traversal): VLR
루트를 먼저 방문(V)하고, 다음에 왼쪽 서브 트리를 방문(L)하고, 방문이 끝나면 마지막으로 오른쪽 서브 트리를 방문(R)하는 방식 - 중위순회(inorder traversal): LVR
왼쪽 서브 트리부터 시작해서 루트를 거쳐 오른쪽 서브 트리 순으로 방문하는 방식 - 후위순회(postorder traversal): LRV
왼쪽 서브 트리, 오른쪽 서브 트리, 루트 순으로 방문하는 방식.
트리에서는 전체 트리나 서브 트리나 기본 구조가 완전히 같으므로 전체 트리에 사용된 알고리즘은 똑같이 서브 트리에서도 적용이 가능하다.
따라서 순회 기법(재귀 호출)이 흔히 사용된다.
순회 방법의 선택
자식을 먼저 처리해야 부모를 처리할 수 있다면 후위순회를 사용해야 한다.
이를 테면, 컴퓨터에서 어떤 폴더의 용량은 하위 폴더들의 용량을 알아야만 계산할 수 있다.
부모가 처리되어야 자식을 처리할 수 있다면, 전위 순회를 사용해야 한다.
이를 테면, 모든 노드에서 자신의 레벨을 계산하는 경우에 전위순회를 사용해야 한다.
루트의 레벨이 1이고, 나머지 모든 노드는 부모의 레벨보다 1이 크기 때문에,
부모의 레벨이 결정되어야 자식의 레벨을 정할 수 있다.
레벨 순회
레벨 순으로 노드를 방문하는 것.
루트의 레벨이 1이고 아래로 내려갈수록 레벨이 증가하므로 위에서 아래로 방문하고, 같은 레벨에서는 왼쪽에서 오른쪽으로 방문한다.
이진 트리의 연산들
전체 노드의 수 구하기
이진 트리의 노드 개수는 완쪽 서브 트리의 노드 수와 오른쪽 서브 트리의 노드 수의 합에 1(루트 노트)을 더하면 된다.
트리의 높이 구하기
이진 트리의 높이는 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 중에서 큰 값에 1을 더한 값이다.
결정 트리
여러 단계의 복잡한 조건을 갖는 문제에 대해 조건과 그에 따른 해결방법을 트리 형태로 나타낸 것.
수식 트리
산술식을 트리 형태로 표현한 이진 트리.
수식 트리는 하나의 연산자가 2개의 피연산자를 갖는다고 가정하는데, 피연산자는 단말노드에 저장되고, 연산자는 루트나 가지 노드에 배치한다.
수식 트리의 계산
어떤 연산자를 계산하려면 자식 노드의 계산이 반드시 끝나있어야하며, 수식 트리의 계산에는 후위순회가 사용된다.
수식의 표현방법
전위 표기법
연산자를 먼저 적고 좌우 피연산자를 이어서 적는 방법이다.
중위와 후위 표기법
연산자를 중간 또는 마지막에 적는 방법이다.
이를 테면, A+B는 중위표기법인데, 같은 식을 전위표기로 나타내면 +AB, 후위표기로 나타내면 AB+가 된다.
중위표가 (A+B)*C와 동일한 후위표기 AB+C*는 다음과 같은 장점이 있다.
- 괄호를 사용하지 않아도 계산 순서를 알 수 있다.
- 연산자의 우선 순위를 생각할 필요가 없다. 식 자체에 우선 순위가 이미 포함되어있기 때문이다.
- 수식을 읽으면서 바로 계산할 수 있다. 중위표기는 괄호와 연산자의 우선 순위 때문에 식을 끝까지 읽은 다음에야 계산할 수 있다.
| 전위(prefix) | 중위(infix) | 후위(postfix) |
| 연산자 피연산자1 피연산자2 | 피연산자1 연산자 피연산자2 | 피연산자1 피연산자2 연산자 |
| +AB | A+B | AB+ |
| +5*AB | 5+A*B | 5AB*+ |
