트리 순회
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
트리 순회는 트리 자료 구조의 모든 노드를 체계적으로 방문하는 방법으로, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)으로 분류된다. DFS는 한 노드의 자식 노드를 모두 방문한 후 다음 형제 노드로 이동하며, BFS는 모든 노드를 낮은 레벨부터 차례대로 순회한다. DFS는 전위, 중위, 후위 순회로 나뉘며, 각 순회 방법은 노드의 방문 순서를 결정한다. 이러한 순회 방법들은 재귀 또는 반복적 구현, 스택, 큐, 모리스 순회 등을 통해 구현될 수 있다. 트리 순회는 유한 트리뿐만 아니라 무한 트리에도 적용될 수 있으며, 함수형 프로그래밍, 게임 트리 분석 등 다양한 분야에서 활용된다. 특히 전위, 중위, 후위 순회는 수식 트리에서 접두사, 중위, 후위 표기법을 생성하고, 이진 탐색 트리에서 값을 정렬하는 데 사용된다.
더 읽어볼만한 페이지
- 재귀 - 무한 루프
무한 루프는 컴퓨터 프로그램에서 루프가 종료되지 않고 무한히 반복되는 현상으로, 프로그램 오류나 의도적인 경우에 발생하며 시스템 응답 불능을 초래하거나 특정 상황에서 사용되기도 한다. - 재귀 - 점화식
점화식은 수열의 각 항을 이전 항들의 함수로 표현하는 방정식으로, 피보나치 수열, 로지스틱 맵, 이항 계수 등의 예시가 있으며, 선형대수학이나 Z변환 등을 이용하여 풀고 다양한 분야에 응용된다. - 트리 구조 - 덴드로그램
덴드로그램은 데이터 분석에서 데이터 포인트 간 계층적 관계를 시각적으로 표현하는 나무 형태의 다이어그램으로, 군집 분석에서 클러스터 간 유사성을 나타내기 위해 활용되며 다양한 분야에 응용된다. - 트리 구조 - 프림 알고리즘
프림 알고리즘은 그래프의 최소 비용 신장 트리를 찾는 탐욕 알고리즘으로, 최소 가중치를 가진 간선을 선택하여 트리를 확장하며, 시간 복잡도는 사용되는 자료 구조에 따라 달라진다. - 그래프 알고리즘 - 페이지랭크
페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다. - 그래프 알고리즘 - 너비 우선 탐색
너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
| 트리 순회 | |
|---|---|
| 정의 | |
| 트리 순회 | 트리 자료 구조의 모든 노드를 방문하는 과정 |
| 종류 | |
| 전위 순회 (preorder traversal) | 루트 노드 방문 -> 왼쪽 서브트리 순회 -> 오른쪽 서브트리 순회 |
| 중위 순회 (inorder traversal) | 왼쪽 서브트리 순회 -> 루트 노드 방문 -> 오른쪽 서브트리 순회 |
| 후위 순회 (postorder traversal) | 왼쪽 서브트리 순회 -> 오른쪽 서브트리 순회 -> 루트 노드 방문 |
| 레벨 순회 (level order traversal) | 각 레벨별로 노드를 방문 (너비 우선 탐색) |
2. 순회
연결 리스트나 1차원 배열과 같은 선형 자료 구조와 달리, 트리 구조는 여러 가지 순회 방법이 존재한다. 트리 순회는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)으로 나눌 수 있으며, 이진 트리의 경우 루트 노드에서 시작하여 현재 노드 방문, 왼쪽 자식 노드 순회, 오른쪽 자식 노드 순회라는 세 가지 주요 단계를 거치며 순회를 진행한다. 이러한 과정은 재귀를 통해 쉽게 설명할 수 있다.[1]
2. 1. 깊이 우선 탐색 (DFS)
'''깊이 우선 탐색'''(DFS)은 다음 형제 노드로 이동하기 전에 한 노드의 자식 노드를 최대한 깊게 탐색하는 방식이다.이진 트리에서 깊이 우선 탐색을 하려면 각 노드에서 다음 작업을 수행한다.[3][4]
# 현재 노드가 비어 있으면 반환한다.
# 다음 세 가지 작업을 특정 순서로 실행한다.[5]
## 현재 노드를 방문한다. (N)
## 현재 노드의 왼쪽 하위 트리를 재귀적으로 순회한다. (L)
## 현재 노드의 오른쪽 하위 트리를 재귀적으로 순회한다. (R)
순회 추적은 방문된 각 노드의 목록으로, 트리의 순차화라고 한다. 전위, 중위, 후위 순서에 따른 단일 순차화는 기본 트리를 고유하게 설명하지 못한다. 하지만 고유한 요소를 가진 트리가 주어지면 중위 순서와 전위 또는 후위 순서를 함께 사용하면 트리를 고유하게 식별할 수 있다.[6]
그림에서 빨간색, 녹색, 파란색은 노드 방문 시점을 나타낸다. 한 가지 색상을 선택하면 해당 순회 방식대로 노드를 한 번 방문한다. 세 가지 색상을 모두 방문하면 동일 노드를 세 번 방문하는 "모든 순서" 순차화가 된다.
임의의 트리(이진 트리뿐만 아니라)를 깊이 우선 탐색으로 순회하려면 다음 단계를 따른다.
# 현재 노드가 비어 있으면 반환한다.
# 전위 순회를 위해 현재 노드를 방문한다.
# 현재 노드의 하위 트리 개수 - 1까지 각 ''i''에 대해 (또는 역순회를 위해 마지막부터 첫 번째까지) 다음을 수행한다.
## 현재 노드의 ''i''번째 하위 트리를 재귀적으로 순회한다.
## 중위 순회를 위해 현재 노드를 방문한다.
# 현재 노드의 마지막 하위 트리를 재귀적으로 순회한다.
# 후위 순회를 위해 현재 노드를 방문한다.
문제에 따라 전위, 후위, 또는 특정 중위 연산(하위 트리 개수 - 1 중 하나)은 선택 사항일 수 있다. 또한, 전위, 후위, 중위 연산 중 둘 이상이 필요할 수도 있다. 예를 들어, 삼진 트리에 삽입할 때는 항목 비교를 위해 전위 연산을 수행하고, 균형 유지를 위해 후위 연산이 필요할 수 있다.
2. 1. 1. 전위 순회 (Pre-order)
전위 순회는 다음 순서로 진행된다.1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.
전위 순회는 깊이 우선 순회라고도 한다. 전위 순회는 이진 탐색 트리를 완전히 복사해서 만들 때 새로운 트리에 값을 집어넣는 동안에 흔히 사용한다. 또한 전위 표기법을 구하는데 사용할 수 있다. 식의 값을 계산할 때, 오른쪽에서 왼쪽으로 살펴보면서 원소를 스택에 넣는다. 연산자를 찾을 때마다, 스택 위에 있는 2개의 기호를 빼내고 그 연산자를 이용해 계산한 뒤 그 결과를 다시 스택에 넣는다. 예를 들면, 전위 표기법 식 * + 2 3 4 (중위 표기법으로는 (2 + 3) * 4)를 계산하는 방법은 다음과 같다.
| 남아있는 식 | 스택 |
|---|---|
| ∗ + 2 3 4 | <비었음> |
| ∗ + 2 3 | 4 |
| ∗ + 2 | 3 4 |
| ∗ + | 2 3 4 |
| ∗ | 5 4 |
| 답 | 20 |
전위 순회는 위상 정렬된 순서이며, 이는 부모 노드가 자식 노드보다 먼저 처리되기 때문이다.
2. 1. 2. 중위 순회 (In-order)
중위 순회는 다음 순서로 진행된다.[7]1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.
중위 순회는 대칭 순회(symmetric)라고도 한다. 중위 순회는 특히 이진 탐색 트리에서 사용되는데, 이진 탐색 트리의 설정에 따른 기본적인 순서에서 값을 반환해야 하기 때문이다. 이진 탐색 트리의 노드 n에서, n의 모든 왼쪽 서브 트리는 n보다 작고, n의 모든 오른쪽 서브 트리는 n보다 크거나 같다. 따라서, 왼쪽 서브 트리를 순서대로 방문하고, 재귀 호출을 사용하여 n을 방문하고, 오른쪽 서브 트리를 순서대로 방문하면, n을 루트로 하는 모든 서브트리를 순서대로 방문하게 된다. 재귀 호출이 정확히 서브 트리를 순서대로 방문하는지는 구조적 귀납법의 수학적 원리를 사용하여 추측할 수 있다. 역순 중위 순회는 값을 내림차순으로 정렬하는 것과 비슷하다.
각 노드에서 키가 왼쪽 서브트리의 모든 키보다 크고 오른쪽 서브트리의 모든 키보다 작은 이진 탐색 트리에서 중위 순회는 키를 ''오름차순''으로 정렬된 순서로 검색한다.[7]
| 절차 | 반복적 중위 순회 절차 |
|---|---|
2. 1. 3. 후위 순회 (Post-order)
후위 순회는 다음 순서로 진행된다.# 왼쪽 서브 트리를 후위 순회한다.
# 오른쪽 서브 트리를 후위 순회한다.
# 노드를 방문한다.
후위 순회는 후위 표기법을 이진 표현 트리에서 얻는 데 유용할 수 있다.
| 절차 |
|---|
2. 1. 4. 역 전위 순회 (Reverse Pre-order)
현재 노드를 방문한 후, 오른쪽, 왼쪽 서브트리 순으로 재귀적으로 순회한다.2. 1. 5. 역 후위 순회 (Reverse Post-order)
먼저 현재 노드의 오른쪽 하위 트리를 재귀적으로 순회하고, 그 다음 현재 노드의 왼쪽 하위 트리를 재귀적으로 순회한 후, 마지막으로 현재 노드를 방문한다.2. 1. 6. 역 중위 순회 (Reverse In-order)
이진 탐색 트리에서 각 노드의 키가 왼쪽 서브트리의 모든 키보다 크고 오른쪽 서브트리의 모든 키보다 작은 방식으로 정렬되어 있을 때, 역 중위 순회는 키를 ''내림차순''으로 정렬된 순서로 검색한다.[1] 역 중위 순회는 다음 순서로 진행된다.[1]# 현재 노드의 오른쪽 서브트리를 재귀적으로 순회한다.
# 현재 노드를 방문한다.
# 현재 노드의 왼쪽 서브트리를 재귀적으로 순회한다.
2. 2. 너비 우선 탐색 (BFS)
너비 우선 탐색은 모든 노드를 낮은 레벨부터 차례대로 순회하는 방식이다. 레벨 순서 순회(Level-order Traversal)라고도 한다.[1] 너비 우선 순회라고도 한다.[2]
너비 우선 탐색은 큐를 사용하여 구현할 수 있다. 다음은 간단한 큐 기반의 레벨 순회에 대한 의사 코드이다.[3]
'''절차''' 레벨오더(노드)
: 큐 ← '''빈 큐'''
: queue.enqueue(노드)
: '''while''' '''not''' queue.isEmpty()
:: 노드 ← queue.dequeue()
:: visit(노드)
:: '''if''' 노드.left ≠ '''null'''
::: queue.enqueue(노드.left)
:: '''if''' 노드.right ≠ '''null'''
::: queue.enqueue(노드.right)
이 구현에는 마지막 노드의 깊이에 비례한 공간이 필요하다. 이는 모든 노드 번호의 합계 / 2가 된다. 공간을 더욱 효율적으로 사용하고 싶으면 반복 심화 깊이 우선 탐색을 사용한다.[4]
트리가 배열로 표현되는 경우(첫 번째 인덱스는 0), 모든 요소를 반복하는 것으로 충분하다.[5]
'''절차''' 레벨오더(배열)
: '''for''' i '''from''' 0 '''to''' array.size
:: visit(array[i])
2. 3. 순회 방법 구현
연결 리스트나 1차원 배열과 같은 선형 자료 구조에서는 순회 방법이 하나뿐이지만, 트리 구조에서는 여러 순회 방법이 존재한다. 이진 트리의 루트 노드에서 시작하여 현재 노드 방문, 왼쪽 자식 노드 순회, 오른쪽 자식 노드 순회라는 세 단계를 거치며 순회를 진행한다. 이러한 과정은 재귀를 통해 쉽게 구현할 수 있다.[7]트리 순회는 재귀 또는 스택을 이용하여 구현할 수 있다. 모든 재귀 알고리즘은 트리의 깊이에 비례한 스택 공간이 필요하다. 재귀적 순회는 여러 가지 잘 알려진 방법을 이용하여 반복적인 방법으로 변환할 수 있다.[1] 각각의 노드가 부모 포인터를 가지고 있거나 스레드 이진 트리인 경우 스택을 쓸 필요가 없다.[7] 스레드 이진 트리를 사용하면 스택 없이 중위 순회를 구현할 수 있다.
반복 심화 깊이 우선 탐색(Iterative Deepening Depth-First Search)을 사용하면 공간 효율성을 높일 수 있다.[1]
2. 3. 1. 재귀적 구현
'''전위 순회'''(preorder)는 다음과 같은 방법으로 진행한다.[7]# 노드를 방문한다.
# 왼쪽 서브 트리를 전위 순회한다.
# 오른쪽 서브 트리를 전위 순회한다.
전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.
'''중위 순회'''(Inorder)는 다음의 순서로 진행된다.[7]
# 왼쪽 서브 트리를 중위 순회한다.
# 노드를 방문한다.
# 오른쪽 서브 트리를 중위 순회한다.
중위 순회는 대칭 순회(symmetric)라고도 한다.
'''후위 순회'''(postorder)는 다음과 같은 방법으로 진행한다.[7]
# 왼쪽 서브 트리를 후위 순회한다.
# 오른쪽 서브 트리를 후위 순회한다.
# 노드를 방문한다.
모든 구현은 트리의 높이에 비례한 호출 스택 공간이 필요하다. 약하게 균형 잡힌 트리에서 이는 더욱 중요하다.[7]
각각의 노드가 부모 포인터를 가지고 있거나 스레드 이진 트리인 경우 스택을 쓸 필요가 없다. 스레드를 쓰는 경우, 중위 순회를 더 크게 개량할 수 있고, 전위 순회와 후위 순회에 필요한 부모 노드의 필요성을 되찾더라도 이것이 알고리즘에 기반한 간단한 스택보다 더 느려지게 된다.[7]
| 전위 순회 | 후위 순회 | 중위 순회 |
|---|---|---|
2. 3. 2. 반복적 구현
스택을 사용하여 재귀 호출 없이 깊이 우선 탐색을 구현할 수 있다. 큐를 사용하여 너비 우선 탐색을 구현할 수 있다.[1]모든 재귀 알고리즘은 트리의 깊이에 비례한 스택 공간이 필요하다. 재귀적 순회는 여러 가지 잘 알려진 방법을 이용하여 반복적인 방법으로 변환할 수 있다. 다음은 재귀를 사용하지 않는 후위 순회 의사 코드이다.[1]
```text
'''nonRecursivePostorder'''(rootNode)
nodeStack.'''push'''(rootNode)
'''while''' (! nodeStack.'''empty'''())
currNode = nodeStack.'''peek'''()
'''if''' ((currNode.left != null) '''and''' (currNode.left.visited == false))
nodeStack.'''push'''(currNode.left)
'''else'''
'''if''' ((currNode.right != null) '''and''' (currNode.right.visited == false))
nodeStack.'''push'''(currNode.right)
'''else'''
print currNode.value
currNode.visited := true
nodeStack.'''pop'''()
```
위의 의사 코드에서 각 노드는 추가적인 visited 플래그가 필요하다. 다음은 visited 플래그를 사용하지 않는 전위 순회 자바 코드이다.[1]
```java
public void traverseTree(Node root) {
Stack nodes = new Stack();
nodes.push(root);
Node currentNode;
while (! nodes.isEmpty()){
currentNode = nodes.pop();
Node right = currentNode.right();
if (right != null)
nodes.push(right);
Node left = currentNode.left();
if (left != null)
nodes.push(left);
System.out.println("Node data: "+currentNode.data);
}
}
```
각 노드가 부모 노드의 정보를 가지고 있다면, 스택이나 visited 플래그 없이 반복 순회를 구현할 수 있다.[1]
다음은 간단한 큐 기반의 레벨 순회(너비 우선 탐색) 의사 코드이다. 이 구현은 주어진 깊이에서 노드의 최대 개수에 비례하는 공간이 필요하며, 최대 전체 노드의 절반까지 필요할 수 있다. 더 공간 효율적인 방법은 반복적 심층 탐색을 사용하는 것이다.[1]
```text
'''절차''' 레벨오더(노드)
큐 ← '''빈 큐'''
queue.enqueue(노드)
'''while''' '''not''' queue.isEmpty()
노드 ← queue.dequeue()
visit(노드)
'''if''' 노드.left ≠ '''null'''
queue.enqueue(노드.left)
'''if''' 노드.right ≠ '''null'''
queue.enqueue(노드.right)
```
트리가 배열로 표현되는 경우(첫 번째 인덱스는 0), 모든 요소를 순회하면 된다.[1]
```text
'''절차''' 레벨오더(배열)
'''for''' i '''from''' 0 '''to''' array.size
visit(array[i])
2. 3. 3. 모리스 순회 (Morris Traversal)
모리스 순회는 스레드 이진 트리를 활용하여 호출 스택과 같은 추가적인 메모리 사용 없이 중위 순회를 수행하는 방법이다.[9]모리스 순회의 장점과 단점은 다음과 같다.
| 장점 | 단점 |
|---|---|
트리 순회는 유한한 노드를 가진 트리뿐만 아니라 무한 트리에도 적용할 수 있다. 이는 함수형 프로그래밍, 특히 레이지 평가에서 중요한데, 무한 데이터 구조를 쉽게 정의하고 다룰 수 있기 때문이다. 체스나 바둑의 게임 트리처럼 너무 커서 명시적으로 표현하기 어려운 유한 트리도 무한 트리처럼 분석하는 것이 유용하다.
전위 순회는 위상 정렬된 순서이며, 부모 노드가 자식 노드보다 먼저 처리되기 때문이다. 전위 순회는 수식 트리에서 접두사 표현법(폴란드 표기법)을 만드는 데 사용될 수 있다. 예를 들어,
[1]
웹사이트
Lecture 8, Tree Traversal
http://webdocs.cs.ua[...]
2015-05-02
모리스 순회의 구현 방법은 다음과 같다.[9]
# 현재 노드의 중위 후속자(Inorder Successor)로 연결되는 임시 링크를 생성한다.
# 생성된 링크를 따라가면서 데이터를 출력한다.
# 순회가 끝나면 임시 링크를 제거하여 원래 트리를 복원한다.
3. 무한 트리
무한 트리에서 모든 노드를 방문하는 것은 단순한 알고리즘으로는 어려울 수 있다. 예를 들어 무한 깊이의 이진 트리에서 깊이 우선 탐색은 한쪽으로만 내려가 다른 부분을 방문하지 못하고, 중위/후위 순회는 어떤 노드에도 도달하지 못할 수 있다. 반면 너비 우선 탐색은 무한 깊이의 이진 트리를 문제없이 탐색할 수 있다.
깊이가 2이고 루트가 무한히 많은 자식을 가지며 각 자식이 두 개의 자식을 갖는 트리에서는, 깊이 우선 탐색이 모든 노드를 방문할 수 있는 반면 너비 우선 탐색은 손자 노드에 도달하지 못한다.
실행 시간의 정교한 분석은 무한 서수를 통해 가능하다. 예를 들어 깊이가 2인 무한 트리에서 너비 우선 탐색은 ω·2 단계를 거친다.
단순한 깊이 우선/너비 우선 탐색은 모든 무한 트리를 탐색하지 못하고 효율적이지 않을 수 있지만, 하이브리드 방법은 대각선 논법을 통해 무한 트리를 탐색할 수 있다.
무한 깊이와 분기를 가진 트리의 노드에 양의 정수 수열로 레이블을 붙이고, 항목 합과 사전식 순서로 정렬하면 순회가 가능하다. 이는 무한 깊이 이진 트리를 이 트리에 매핑하고 너비 우선 탐색을 적용하는 것으로 해석할 수 있다.
4. 응용
후위 순회는 이진 트리의 후위 표기법(역 폴란드 표기법)을 생성할 수 있다. 묘사된 산술식을 후위 순회하면 "''A'' ''B'' ''C'' − * ''D'' ''E'' + +"가 생성된다. 후자는 스택 머신에 의해 수식을 계산하기 위해 기계어로 쉽게 변환될 수 있다. 후위 순회는 트리를 삭제하는 데에도 사용된다. 각 노드는 자식 노드를 해제한 후에 해제된다.[1]
중위 순회는 이진 탐색 트리에서 매우 일반적으로 사용되는데, 이진 탐색 트리를 설정한 비교자에 따라 기본 집합의 값을 순서대로 반환하기 때문이다.[1]
다른 트리 순회 알고리즘으로는 깊이 우선 탐색도 너비 우선 탐색도 아닌 방식이 있다. 이러한 알고리즘 중 하나는 몬테 카를로 트리 탐색으로, 가장 유망한 수를 분석하는 데 집중하며 탐색 트리의 확장을 몬테 카를로 방법을 이용한 탐색 공간의 무작위 샘플링에 기반한다.[1]
참조
[2]
서적
An Introduction to Binary Search Trees and Balanced Trees
Free Software Foundation, Inc.
2004
[3]
문서
Binary Tree Traversal Methods
http://www.cise.ufl.[...]
[4]
웹사이트
Preorder Traversal Algorithm
http://www.programme[...]
2015-05-02
[5]
문서
[6]
웹사이트
Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange
https://cs.stackexch[...]
2015-05-02
[7]
웹사이트
Tree Traversal
https://www.math.ucl[...]
2016-01-02
[8]
웹사이트
constexpr tree structures
https://fekir.info/p[...]
2021-08-15
[9]
논문
Traversing binary trees simply and cheaply
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com