트리(tree)와 이진트리(binary tree)
21 Oct 2017 | Data structure
이번 글에서는 다양한 분야에서 널리 쓰이고 있는 자료구조인 트리(tree)와 트리의 일종인 이진트리(binary tree)에 대해 살펴보도록 하겠습니다. 힙 정렬이 뭔지 알아보려면 여러가지 개념을 먼저 익혀두어야 하는데요. 차근차근 살펴 보겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
트리는 그 모양이 뒤집어 놓은 나무와 같다고 해서 이런 이름이 붙었습니다. 예컨대 다음 그림과 같습니다.
위 그림에서 검정색 동그라미를 노드(node)라고 합니다. 보통 데이터가 여기에 담깁니다. 노드와 노드 사이를 이어주는 선을 엣지(edge)라고 합니다. 노드와의 관계를 표시합니다.
경로(path)란 엣지로 연결된, 즉 인접한 노드들로 이뤄진 시퀀스(sequence)를 가리킵니다. 경로의 길이(length)는 경로에 속한 엣지의 수를 나타냅니다.
트리의 높이(height)는 루트노드에서 말단노드에 이르는 가장 긴 경로의 엣지 수를 가리킵니다. 트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부릅니다.
잎새노드(leaf node)란 자식노드가 없는 노드입니다. internal node란 잎새노드를 제외한 노드를 나타냅니다. 루트노드(root node)란 부모노드가 없는 노드를 가리킵니다.
트리의 속성 중 가장 중요한 것이 ‘루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다’는 것입니다. 이 속성 때문에 트리는 다음 성질을 만족합니다.
- 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
- 엣지(edge)의 수 |$E$| 는 노드의 수 |$V$|에서 1을 뺀 것과 같다.
다음 두 예시는 트리가 아닙니다. 회로가 존재하기 때문입니다.
다음 예시는 트리가 아닙니다. 회로가 존재하지는 않지만 1에서 4로 가는 경로가 유일하지 않아서입니다.
다음 예시 또한 트리가 아닙니다. 연결되지 않은 노드가 존재하기 때문입니다.
Binary tree
이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다. 이진트리에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있습니다.
정이진트리는 다음 그림과 같습니다. 모든 레벨에서 노드들이 꽉 채워진(=잎새노드를 제외한 모든 노드가 자식노드를 2개 가짐) 이진트리입니다.
위 정이진트리에서 레벨에 따른 노드의 숫자는 다음 표와 같습니다.
레벨
노드수
0
$2^0$
1
$2^1$
2
$2^2$
…
…
$k$
$2^k$
total
$2^{k+1}-1$
정이진트리의 노드수가 $n$개라면 잎새노드의 수는 $n/2$를 올림한 숫자가 됩니다. 위 그림 예시를 기준으로 하면 총 31개의 노드가 있는데 이 가운데 잎새노드는 31/2를 올림한 16개입니다.
완전이진트리는 다음 그림과 같습니다. 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리입니다.
정이진트리와 완전이진트리는 다음처럼 1차원 배열(array)로도 표현이 가능합니다.
어떤 노드의 인덱스를 index, 왼쪽 자식노드의 인덱스를 left_index, 오른쪽 자식노드의 인덱스를 right_index로 선언하면 다음과 같은 관계를 지닙니다. 이를 파이썬 코드로 구현하면 다음과 같습니다.
left_index = 2 * index + 1
right_index = 2 * index + 2
균형이진트리는 다음 그림과 같습니다. 모든 잎새노드의 깊이 차이가 많아야 1인 트리를 가리킵니다. 균형이진트리는 예측 가능한 깊이(predictable depth)를 가지며, 노드가 $n$개인 균형이진트리의 깊이는 $\log{n}$을 내림한 값이 됩니다.
깊이 말고 left subtree와 right subtree의 노드 수를 기준으로 균형이진트리를 정의하는 경우도 있다고 합니다. 힙 정렬과 이진탐색트리는 모두 이진트리를 기반으로 만들어진 기법입니다. 힙 정렬은 이곳, 이진탐색트리는 이곳을 참고하시면 좋을 것 같습니다.
tree traversal
트리순회(tree traversal)란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다. 하나도 빠뜨리지 않고, 정확히 한번만 중복없이 방문해야 하는데요. 노드를 방문하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 세 가지로 나뉩니다. 아래 트리를 예시로 각 방법 간 차이를 비교해 보겠습니다.
preorder
루트 노드에서 시작해서 노드-왼쪽 서브트리-오른쪽 서브트리 순으로 순회하는 방식입니다. 깊이우선순회(depth-first traversal)라고도 합니다. 위 예시 트리에 전위순회 방식을 적용하면 다음과 같습니다.
1, 2, 4, 5, 3
inorder
루트 노드에서 시작해서 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식입니다. 대칭순회(symmetric traversal)라고도 합니다. 위 예시 트리를 중위순회 방식을 적용하면 다음과 같습니다.
4, 2, 5, 1, 3
postorder
루트 노드에서 시작해서 왼쪽 서브트리-오른쪽 서브트리-노드 순으로 순회하는 방식입니다. 위 예시 트리를 후위순회 방식을 적용하면 다음과 같습니다.
4, 5, 2, 3, 1
예시 : 사칙연산
예컨대 다음과 같은 식을 계산해야 한다고 칩시다.
- $(A+B)×(C+D)+2$
이를 후위표기법으로 바꿔서 다시 쓰면 다음과 같습니다. 후위표기법은 이곳을 참고하시면 좋을 것 같습니다.
- $AB+CD+×2+$
컴퓨터가 사칙연산을 수행할 때 이진트리를 쓰면 편리합니다. 아래 그림을 볼까요?
위 이진트리를 후위순회 방식으로 읽어 보겠습니다. 이는 정확히 후위표기법과 일치합니다.
A, B, +, C, D, +, ×, 2, +
위 이진트리를 전위순회 방식으로 읽어 보겠습니다. 다음과 같습니다.
+, ×, +, A, B, +, C, D, 2
이는 함수명(인자) 형태의 함수호출과 동일합니다. 예컨대 + 기호를 add 함수, ×를 multiply 함수라고 생각해 보죠. 그러면 위와 같은 시퀀스는 다음과 같이 수행됩니다.
add(multiply(add(A, B), add(C, D)), 2)
이번 글에서는 다양한 분야에서 널리 쓰이고 있는 자료구조인 트리(tree)와 트리의 일종인 이진트리(binary tree)에 대해 살펴보도록 하겠습니다. 힙 정렬이 뭔지 알아보려면 여러가지 개념을 먼저 익혀두어야 하는데요. 차근차근 살펴 보겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
트리는 그 모양이 뒤집어 놓은 나무와 같다고 해서 이런 이름이 붙었습니다. 예컨대 다음 그림과 같습니다.
위 그림에서 검정색 동그라미를 노드(node)라고 합니다. 보통 데이터가 여기에 담깁니다. 노드와 노드 사이를 이어주는 선을 엣지(edge)라고 합니다. 노드와의 관계를 표시합니다.
경로(path)란 엣지로 연결된, 즉 인접한 노드들로 이뤄진 시퀀스(sequence)를 가리킵니다. 경로의 길이(length)는 경로에 속한 엣지의 수를 나타냅니다.
트리의 높이(height)는 루트노드에서 말단노드에 이르는 가장 긴 경로의 엣지 수를 가리킵니다. 트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부릅니다.
잎새노드(leaf node)란 자식노드가 없는 노드입니다. internal node란 잎새노드를 제외한 노드를 나타냅니다. 루트노드(root node)란 부모노드가 없는 노드를 가리킵니다.
트리의 속성 중 가장 중요한 것이 ‘루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다’는 것입니다. 이 속성 때문에 트리는 다음 성질을 만족합니다.
- 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
- 엣지(edge)의 수 |$E$| 는 노드의 수 |$V$|에서 1을 뺀 것과 같다.
다음 두 예시는 트리가 아닙니다. 회로가 존재하기 때문입니다.
다음 예시는 트리가 아닙니다. 회로가 존재하지는 않지만 1에서 4로 가는 경로가 유일하지 않아서입니다.
다음 예시 또한 트리가 아닙니다. 연결되지 않은 노드가 존재하기 때문입니다.
Binary tree
이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다. 이진트리에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있습니다.
정이진트리는 다음 그림과 같습니다. 모든 레벨에서 노드들이 꽉 채워진(=잎새노드를 제외한 모든 노드가 자식노드를 2개 가짐) 이진트리입니다.
위 정이진트리에서 레벨에 따른 노드의 숫자는 다음 표와 같습니다.
| 레벨 | 노드수 |
|---|---|
| 0 | $2^0$ |
| 1 | $2^1$ |
| 2 | $2^2$ |
| … | … |
| $k$ | $2^k$ |
| total | $2^{k+1}-1$ |
정이진트리의 노드수가 $n$개라면 잎새노드의 수는 $n/2$를 올림한 숫자가 됩니다. 위 그림 예시를 기준으로 하면 총 31개의 노드가 있는데 이 가운데 잎새노드는 31/2를 올림한 16개입니다.
완전이진트리는 다음 그림과 같습니다. 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리입니다.
정이진트리와 완전이진트리는 다음처럼 1차원 배열(array)로도 표현이 가능합니다.
어떤 노드의 인덱스를 index, 왼쪽 자식노드의 인덱스를 left_index, 오른쪽 자식노드의 인덱스를 right_index로 선언하면 다음과 같은 관계를 지닙니다. 이를 파이썬 코드로 구현하면 다음과 같습니다.
left_index = 2 * index + 1
right_index = 2 * index + 2
균형이진트리는 다음 그림과 같습니다. 모든 잎새노드의 깊이 차이가 많아야 1인 트리를 가리킵니다. 균형이진트리는 예측 가능한 깊이(predictable depth)를 가지며, 노드가 $n$개인 균형이진트리의 깊이는 $\log{n}$을 내림한 값이 됩니다.
깊이 말고 left subtree와 right subtree의 노드 수를 기준으로 균형이진트리를 정의하는 경우도 있다고 합니다. 힙 정렬과 이진탐색트리는 모두 이진트리를 기반으로 만들어진 기법입니다. 힙 정렬은 이곳, 이진탐색트리는 이곳을 참고하시면 좋을 것 같습니다.
tree traversal
트리순회(tree traversal)란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다. 하나도 빠뜨리지 않고, 정확히 한번만 중복없이 방문해야 하는데요. 노드를 방문하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 세 가지로 나뉩니다. 아래 트리를 예시로 각 방법 간 차이를 비교해 보겠습니다.
preorder
루트 노드에서 시작해서 노드-왼쪽 서브트리-오른쪽 서브트리 순으로 순회하는 방식입니다. 깊이우선순회(depth-first traversal)라고도 합니다. 위 예시 트리에 전위순회 방식을 적용하면 다음과 같습니다.
1, 2, 4, 5, 3
inorder
루트 노드에서 시작해서 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식입니다. 대칭순회(symmetric traversal)라고도 합니다. 위 예시 트리를 중위순회 방식을 적용하면 다음과 같습니다.
4, 2, 5, 1, 3
postorder
루트 노드에서 시작해서 왼쪽 서브트리-오른쪽 서브트리-노드 순으로 순회하는 방식입니다. 위 예시 트리를 후위순회 방식을 적용하면 다음과 같습니다.
4, 5, 2, 3, 1
예시 : 사칙연산
예컨대 다음과 같은 식을 계산해야 한다고 칩시다.
- $(A+B)×(C+D)+2$
이를 후위표기법으로 바꿔서 다시 쓰면 다음과 같습니다. 후위표기법은 이곳을 참고하시면 좋을 것 같습니다.
- $AB+CD+×2+$
컴퓨터가 사칙연산을 수행할 때 이진트리를 쓰면 편리합니다. 아래 그림을 볼까요?
위 이진트리를 후위순회 방식으로 읽어 보겠습니다. 이는 정확히 후위표기법과 일치합니다.
A, B, +, C, D, +, ×, 2, +
위 이진트리를 전위순회 방식으로 읽어 보겠습니다. 다음과 같습니다.
+, ×, +, A, B, +, C, D, 2
이는 함수명(인자) 형태의 함수호출과 동일합니다. 예컨대 + 기호를 add 함수, ×를 multiply 함수라고 생각해 보죠. 그러면 위와 같은 시퀀스는 다음과 같이 수행됩니다.
add(multiply(add(A, B), add(C, D)), 2)
Comments