[자료 구조/알고리즘] 트리 순회
트리 순회
트리 순회(tree traversal)란 트리 자료 구조에서 상위 노드와 두 개의 하위 노드를 정해진 순서에 따라 한 번씩만 탐색하는 것이다. 트리 순회는 노드 탐색 순서에 따라 크게 네 가지로 구분된다.
- 전위 (pre-order) 순회: 상위 노드 -> 왼쪽 하위 노드 -> 오른쪽 하위 노드
- 중위 (in-order) 순회: 왼쪽 하위 노드 -> 상위 노드 -> 오른쪽 하위 노드
- 후위 (post-order) 순회: 왼쪽 하위 노드 -> 오른쪽 하위 노드 -> 상위 노드
- 레벨 순서 (level-order) 순회: 루트 노드 -> 현재 레벨의 모든 노드 -> 다음 레벨의 모든 노드 -> …
트리 순회 중 전위 순회, 중위 순회, 후위 순회는 일반적으로 재귀적(recursive) 알고리즘을 사용하여 쉽게 구현할 수 있다. 재귀 알고리즘은 문제를 더 작고 동일한 형태의 서로 다른 하위 문제로 분할하여 해결하는 방식이다. 트리는 계층적인 구조를 가지고 있으므로 큰 문제를 작은 하위 문제로 나눌 수 있다. 따라서 재귀 알고리즘을 사용하면 트리의 모든 노드를 효율적으로 탐색할 수 있다.
세 가지 트리 순회에서 재귀 알고리즘의 하위 문제는 하위 트리를 순회하는 것이며, 기본 단계(재귀 호출의 종료 조건)는 노드가 하위 노드를 가지고 있지 않는 경우이다.
세 가지 트리 순회는 트리의 모든 노드를 한 번씩 방문하는 것이기 때문에 문제 해결 과정에서 해결하였던 하위 문제를 중복해서 다시 해결하지 않는다. 따라서 재귀 알고리즘을 사용한 트리 순회 문제 해결 과정은 분할 정복(divide-and-conquer) 알고리즘을 사용하는 것이다.
재귀 알고리즘을 사용하여 해결할 수 있는 문제는 반복문을 사용해서 해결할 수도 있다. 프로그래밍에서 재귀 알고리즘 구현은 함수 호출을 재귀적으로 수행하는 것을 의미한다. 모든 프로그래밍 언어에서 재귀 함수 호출은 스택(stack)이라는 자료 구조를 사용하여 후입선출(LIFO, last in first out) 방식으로 함수 호출 관리를 수행한다. 따라서 재귀 함수 호출 방식을 사용하는 대신 스택 자료 구조와 반복문을 직접 사용하여 트리 순회 문제를 해결할 수 있다. 트리 순회 문제에서 스택 자료 구조는 트리의 순회 경로를 추적하고, 나중에 방문해야 할 노드를 저장하기 위해 사용된다.
세 가지 트리 순회는 트리의 깊이 우선 탐색(DFS, depth first search) 알고리즘을 사용한 문제 해결의 한 예이다. 깊이 우선 탐색 알고리즘 역시 재귀 함수 호출을 통해 구현하거나, 명시적으로 스택 자료 구조를 사용하여 구현할 수 있다.
재귀적 문제 해결 방식은 코드가 간결하고 이해하기 쉽지만, 깊이가 깊은 트리에서는 스택 오버플로우(stack overflow) 오류를 발생시킬 위험이 있다. 스택 오버플로우란 시스템 상에서 한정된 스택 자료 구조의 최대 크기를 넘어설 때 발생하는 오류이다. 반복문 방식은 스택 오버플로우 위험이 없지만, 코드가 더 복잡하고 스택을 명시적으로 직접 관리해야 한다는 단점이 있다.
반면 레벨 순서 순회는 재귀적 알고리즘을 사용하여 구현하는 대신, 큐(queue) 자료 구조와 반복문을 사용하여 선입선출(FIFO, firest in first out) 방식으로 트리 순회 문제를 해결하는 것이 일반적이다. 트리가 계층적인 구조를 가지므로 인접한 노드를 탐색하는 문제는 문제를 하위 문제로 나누는 재귀적인 접근 방법으로 해결할 수 있지만 레벨 순서 순회는 특정 레벨의 모든 노드를 탐색한 후 다음 레벨의 모든 노드를 탐색하는 과정을 반복하므로 문제를 하위 문제로 나누는 과정으로는 해결하기가 어렵다. 레벨 순서 순회 문제에서 큐 자료 구조는 트리의 순회 경로를 추적하고, 나중에 방문해야 할 노드를 저장하기 위해 사용된다.
레벨 순서 순회는 트리의 너비 우선 탐색(BFS, breadth first search) 알고리즘을 사용한 문제 해결의 한 예이다. 너비 우선 탐색 알고리즘 역시 큐(queue) 자료 구조와 반복문을 사용하여 구현할 수 있다.
상위 노드 참조를 통한 문제 해결
트리 자료 구조는 계층적인 구조를 가지므로, 프로그래밍 언어를 통한 트리 순회 알고리즘을 구현할 때 일반적으로 이진 트리 노드 구현체 정의 시 노드 데이터, 두 개의 하위 노드 참조를 갖도록 정의한다. 이 때, 하위 노드를 탐색한 후 상위 노드를 탐색해야 할 경우, 이 구현에서 상위 노드에서 하위 노드만 참조하기 때문에(노드 참조가 단방향이기 때문에) 상위 노드를 탐색할 수 있는 방법이 없다. 이 문제를 해결하기 위해 탐색할 노드를 스택 자료 구조에 저장해 놓고 나중에 조회하여 탐색하는 방법을 사용하는 것이다. 즉, 부모 노드 참조를 정의하지 않은 이진 트리 구조에서는 재귀 함수 호출이나 명시적인 스택 자료 구조를 사용한 구현이 필수적이다.
반면 이진 트리 노드 구현체 정의 시 부모 노드 참조를 정의한다면 하위 노드도 상위 노드를 참조하기 때문에(노드 참조가 양방향이기 때문에) 재귀 함수 호출이나 스택 자료 구조 없이도 트리 순회가 가능해 진다. 이 방법을 사용하면 자료 구조를 사용하지 않으므로 하나의 반복문 만을 사용하여 구현할 수 있으며 스택 자료 구조를 사용하지 않아 메모리 공간을 절약할 수 있지만 추가적인 객체 참조를 위한 힙 메모리 할당이 일어나게 된다.
Comments