Traversal

Traversal

트리 순회(Tree Traversal)에 대한 깊이 있는 이해

트리 순회(Tree Traversal)는 트리 자료구조에서 각 노드를 체계적으로 방문하는 과정을 의미한다.
트리의 모든 노드를 빠짐없이 정해진 순서에 따라 방문하는 것이 핵심이다.
이러한 순회 방법은 트리 내의 데이터를 처리하고, 검색하며, 조작하는 기본적인 방법으로, 컴퓨터 과학에서 매우 중요한 알고리즘이다.

트리 순회는 트리 자료구조를 다루는 핵심 연산으로, 다양한 알고리즘과 응용 프로그램에서 필수적이다.
각 순회 방법은 고유한 특성과 장단점을 가지고 있으며, 해결하려는 문제의 성격에 따라 적절한 방법을 선택하는 것이 중요하다.
재귀적 방법은 간결하고 이해하기 쉽지만, 대규모 트리에서는 반복적 방법이나 최적화된 알고리즘을 고려해야 할 수 있다. 트리 순회에 대한 깊은 이해는 효율적인 알고리즘 설계와 문제 해결 능력 향상에 큰 도움이 된다.

트리 순회의 기본 개념

트리 순회는 기본적으로 트리의 모든 노드를 한 번씩 방문하는 과정이다.
트리는 계층적 구조를 가지고 있어 배열이나 연결 리스트와 같은 선형 자료구조와 달리 여러 가지 다른 방법으로 순회할 수 있다.
트리 순회 알고리즘은 일반적으로 재귀적으로 구현되며, 그 과정에서 노드의 데이터를 처리하거나 출력한다.

이진 트리 순회 방법

이진 트리는 가장 일반적인 트리 유형으로, 각 노드가 최대 두 개의 자식을 가진다.
이진 트리의 기본적인 순회 방법은 다음과 같이 네 가지가 있다.

전위 순회(Preorder Traversal)

전위 순회는 루트 노드를 먼저 방문한 다음, 왼쪽 서브트리를 전위 순회하고, 마지막으로 오른쪽 서브트리를 전위 순회한다.

순서: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리

알고리즘(의사 코드):

1
2
3
4
5
6

preorder(node):
    if node is null:
        return
    방문(node)
    preorder(node.left)
    preorder(node.right)

특징:

• 깊이 우선 탐색(DFS) 방식
• 트리 구조의 복사본을 만들 때 유용
• 디렉토리 구조를 표시할 때 사용 (루트 디렉토리부터 시작)
• 표현식 트리에서 전위 표기법(prefix notation)을 생성할 때 사용

예시 활용:

• 트리 복제
• XML/HTML 파싱 (루트 태그부터 처리)
• 트리 직렬화

중위 순회(Inorder Traversal)

중위 순회는 왼쪽 서브트리를 중위 순회한 다음, 루트 노드를 방문하고, 마지막으로 오른쪽 서브트리를 중위 순회한다. 다.

순서: 왼쪽 서브트리 → 루트 → 오른쪽 서브트리

알고리즘(의사 코드):

1
2
3
4
5
6

inorder(node):
    if node is null:
        return
    inorder(node.left)
    방문(node)
    inorder(node.right)

특징:

• 이진 검색 트리(BST)에서 중위 순회를 하면 노드를 오름차순으로 방문
• 중위 표기법의 수식을 생성할 때 사용
• 대칭적인 순회 방식

예시 활용:

• BST에서 정렬된 데이터 검색
• 표현식 트리에서 중위 표기식 생성
• 트리의 균형 검사

후위 순회(Postorder Traversal)

후위 순회는 왼쪽 서브트리를 후위 순회한 다음, 오른쪽 서브트리를 후위 순회하고, 마지막으로 루트 노드를 방문한다.

순서: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트

알고리즘(의사 코드):

1
2
3
4
5
6

postorder(node):
    if node is null:
        return
    postorder(node.left)
    postorder(node.right)
    방문(node)

특징:

• 자식 노드를 먼저 처리한 후 부모 노드를 처리
• 트리를 삭제할 때 유용 (리프 노드부터 삭제하므로 메모리 관리에 효율적)
• 후위 표기법(postfix notation)을 생성할 때 사용
• 디렉토리 크기 계산과 같은 상향식 계산에 적합

예시 활용:

• 파일 시스템에서 디렉토리 크기 계산
• 표현식 트리 평가 (후위 표기법)
• 트리 삭제 연산

레벨 순회(Level Order Traversal) 또는 너비 우선 순회(Breadth-First Traversal)

레벨 순회는 루트 노드부터 시작하여 레벨별로 각 노드를 왼쪽에서 오른쪽으로 방문한다.

순서: 레벨 1 → 레벨 2 → 레벨 3 → … → 레벨 n

알고리즘(의사 코드):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

levelOrder(root):
    if root is null:
        return
    queue Q 초기화
    Q에 root 삽입
    
    while Q is not empty:
        node = Q에서 제거
        방문(node)
        if node.left is not null:
            Q에 node.left 삽입
        if node.right is not null:
            Q에 node.right 삽입

특징:

• 너비 우선 탐색(BFS) 방식
• 큐(Queue) 자료구조를 사용하여 구현
• 최단 경로 문제 및 가장 가까운 노드 찾기에 유용
• 트리의 레벨별 특성을 분석할 때 적합

예시 활용:

• 최단 경로 알고리즘
• 레벨별 트리 시각화
• 트리의 너비 계산
• 가장 가까운 공통 조상 찾기

일반 트리 순회 방법

일반 트리는 각 노드가 임의의 수의 자식을 가질 수 있는 트리이다.
일반 트리의 순회 방법은 이진 트리의 순회 방법을 확장한 형태이다.

전위 순회(Preorder Traversal)

일반 트리에서 전위 순회는 루트를 먼저 방문한 다음, 각 자식 서브트리를 왼쪽에서 오른쪽으로 전위 순회한다.

알고리즘(의사 코드):

1
2
3
4
5
6

preorder(node):
    if node is null:
        return
    방문(node)
    for each child of node:
        preorder(child)

후위 순회(Postorder Traversal)

일반 트리에서 후위 순회는 각 자식 서브트리를 왼쪽에서 오른쪽으로 후위 순회한 다음, 루트를 방문한다.

알고리즘(의사 코드):

1
2
3
4
5
6

postorder(node):
    if node is null:
        return
    for each child of node:
        postorder(child)
    방문(node)

레벨 순회(Level Order Traversal)

일반 트리에서 레벨 순회는 이진 트리와 동일하게 레벨별로 노드를 방문한다.

특수한 트리 순회 방법

기본적인 순회 방법 외에도 특수한 목적을 위한 다양한 트리 순회 방법이 있다.

1. 지그재그 순회(Zigzag Traversal)
   지그재그 순회는 레벨 순회의 변형으로, 홀수 레벨에서는 왼쪽에서 오른쪽으로, 짝수 레벨에서는 오른쪽에서 왼쪽으로 노드를 방문한다.
2. 모리스 순회(Morris Traversal)
   모리스 순회는 추가 공간을 사용하지 않고 트리를 순회하는 방법으로, 특히 중위 순회에 많이 사용된다. 이 방법은 스택이나 재귀를 사용하지 않고 O(1)의 추가 공간만을 사용한다.
3. 경계 순회(Boundary Traversal)
   경계 순회는 트리의 경계(왼쪽 경계, 리프 노드, 오른쪽 경계)를 따라 노드를 방문하는 방법이다.
4. 대각선 순회(Diagonal Traversal)
   대각선 순회는 트리의 대각선 방향으로 노드를 그룹화하여 방문하는 방법이다.

트리 순회의 구현 방식

트리 순회는 주로 두 가지 방식으로 구현된다.

재귀적 방법(Recursive Approach)

재귀적 방법은 가장 간단하고 직관적인 구현 방식이다.
각 노드에 대해 재귀 함수를 호출하여 서브트리를 순회한다.

장점:

• 코드가 간결하고 이해하기 쉬움
• 트리의 구조를 자연스럽게 반영

단점:

• 깊은 트리에서는 스택 오버플로우 발생 가능
• 함수 호출 오버헤드로 인한 성능 저하 가능

반복적 방법(Iterative Approach)

반복적 방법은 스택 또는 큐와 같은 보조 자료구조를 사용하여 순회를 구현한다.

장점:

• 스택 오버플로우 위험 없음
• 대규모 트리에 더 효율적일 수 있음

단점:

• 코드가 복잡해질 수 있음
• 로직을 이해하기 어려울 수 있음

전위 순회의 반복적 구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

iterativePreorder(root):
    if root is null:
        return
    stack S 초기화
    S에 root 삽입
    
    while S is not empty:
        node = S에서 pop
        방문(node)
        if node.right is not null:
            S에 node.right 삽입
        if node.left is not null:
            S에 node.left 삽입

중위 순회의 반복적 구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

iterativeInorder(root):
    if root is null:
        return
    stack S 초기화
    current = root
    
    while current is not null or S is not empty:
        while current is not null:
            S에 current 삽입
            current = current.left
        
        current = S에서 pop
        방문(current)
        current = current.right

후위 순회의 반복적 구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

iterativePostorder(root):
    if root is null:
        return
    stack S1, S2 초기화
    S1에 root 삽입
    
    while S1 is not empty:
        node = S1에서 pop
        S2에 node 삽입
        
        if node.left is not null:
            S1에 node.left 삽입
        if node.right is not null:
            S1에 node.right 삽입
    
    while S2 is not empty:
        node = S2에서 pop
        방문(node)

트리 순회의 시간 및 공간 복잡도

시간 복잡도

모든 기본 트리 순회 알고리즘(전위, 중위, 후위, 레벨 순회)은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)이다. 여기서 n은 트리의 노드 수이다.

공간 복잡도

• 재귀적 방법: O(h), 여기서 h는 트리의 높이이다. 최악의 경우(편향 트리) O(n)이 될 수 있다.
• 반복적 방법(스택 사용): 전위, 중위, 후위 순회에서 O(h)이다.
• 반복적 방법(큐 사용): 레벨 순회에서 O(w), 여기서 w는 트리의 최대 너비이다. 최악의 경우 O(n/2) ≈ O(n)이 될 수 있습니다.

트리 순회의 응용

1. 표현식 트리 평가
   표현식 트리는 수학 표현식을 나타내는 이진 트리이다.
   내부 노드는 연산자를, 리프 노드는 피연산자를 나타낸다.

   • 전위 순회 → 전위 표기법(prefix notation) 또는 폴란드 표기법
   • 중위 순회 → 중위 표기법(infix notation) 또는 일반적인 수학 표기법
   • 후위 순회 → 후위 표기법(postfix notation) 또는 역폴란드 표기법

2. 트리 직렬화 및 역직렬화
   트리를 문자열이나 배열과 같은 선형 자료구조로 변환하는 과정을 직렬화라고 하며, 그 반대 과정을 역직렬화라고 한다. 트리 순회는 이러한 과정에 필수적이다.

3. 이진 검색 트리(BST) 연산
   이진 검색 트리에서 중위 순회를 수행하면 정렬된 순서로 노드를 방문할 수 있다.
   이는 BST의 유효성 검사와 같은 작업에 유용하다.

4. 파일 시스템 탐색
   디렉토리 구조는 트리로 모델링할 수 있으며, 파일 시스템 탐색은 트리 순회로 구현할 수 있다.

5. 구문 분석 트리(Parse Tree) 처리
   프로그래밍 언어의 구문 분석 과정에서 생성되는 구문 분석 트리는 다양한 트리 순회 방법을 사용하여 처리된다.

N-항 트리 순회

N-항 트리(각 노드가 임의의 수의 자식을 가질 수 있는 트리)의 순회는 이진 트리 순회의 확장이다.

1. 깊이 우선 순회(Depth-First Traversal)
   N-항 트리에서 깊이 우선 순회는 루트를 방문한 후, 각 자식 서브트리를 깊이 우선으로 순회한다.

2. 너비 우선 순회(Breadth-First Traversal)
   N-항 트리에서 너비 우선 순회는 레벨별로 노드를 방문한다.

특정 문제에 맞는 순회 방법 선택

적절한 트리 순회 방법을 선택하는 것은 해결하려는 문제의 성격에 따라 달라진다.

• 데이터 정렬이 필요한 경우: 이진 검색 트리에서 중위 순회 사용
• 트리 복제가 필요한 경우: 전위 순회 사용
• 상향식 계산이 필요한 경우: 후위 순회 사용
• 최단 경로 찾기가 필요한 경우: 레벨 순회(BFS) 사용
• 가장 깊은 노드 찾기가 필요한 경우: 깊이 우선 순회(DFS) 사용

효율적인 트리 순회 구현을 위한 최적화 기법

1. 꼬리 재귀 최적화(Tail Recursion Optimization)
   꼬리 재귀는 재귀 호출이 함수의 마지막 작업일 때 발생한다.
   이러한 경우 컴파일러는 재귀 호출을 반복문으로 최적화할 수 있다.

2. 반복자(Iterator) 패턴 사용
   반복자 패턴을 사용하면 트리 순회 로직을 캡슐화하고 순회 과정을 제어할 수 있다.

3. 모리스 순회 알고리즘 사용
   모리스 순회 알고리즘은 추가 공간을 사용하지 않고 트리를 순회할 수 있어, 메모리 제약이 있는 환경에서 유용하다.

참고 및 출처