21. 트리의 구현과 순회

21.1 도입

선형으로 표현하기 어려운 형태의 자료 중 흔한 것이 계층 구조 이다.
- 자료 간에 상하위, 포함 관계
- 조직도, 상품 분류 기준 등 등
트리는 계층 관계를 갖는 객체들을 표현하기 위한 자료구조
그러나 실제 계층 관계가 없는 자료들도 트리를 표현해서 같은 연산을 더 빠르게 할 수 있다.
하나의 상위 개념에서 가지를 쳐서 뻗어가는 모습이 실제 나무(상하가 뒤집혔지만)와 닮았다 해서 트리라고 부른다,
트리는 처음에 현실 세계의 개념을 추상화해 표현하는 자료 구조로 고안되었지만, 탐색형 자료 구조로도 유용하게 쓰인다.
- 특정한 조건을 지키도록 구성된 트리를 이용하면, 배열, 리스트를 사용하는 것보다 빠르게 작업을 할 수 있다.

21.1.1 트리의 기초적인 정의와 용어

21.1.2 트리의 구성 요소

트리는 자료가 저장된 node(노드)와 edge(간선)으로 서로 연결되어 있다.
노드 간에는 상/하위 관계가 있다. 두 노드가 연결되었을 때 한 노드는 좀더 상위, 다른 노드는 좀 더 하위에 있어야 한다.
상위 노드: 부모(parent) 노드
하위 노드: 자식(child) 노드
부모가 같은 노드: 형제(sibling) 노드
부모 노드와 그의 부모들을 통들어: 선조(ancestor)
자식 노드와 그의 자식들을 통들어: 자손(descendant)
부모-자식 비유 처럼, 트리에서 한 노드는 여러 개의 자식을 가질 수 있어도, 부모는 하나만 가질 수 있다.
모든 노드들을 자손으로 갖는 단 하나의 노드: 뿌리, 루트(root) 노드
자식이 하나도 없느 노드: 트리의 잎 노드, 리프(leaf) 노드

21.1.3 트리의 노드의 속성

깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
높이(height): 트리에서 가장 깊숙히 있는 노드의 깊이
트리의 레벨(Level): 깊이가 같은 노드들의 집합

21.1.4 트리의 재귀적 속성

트리는 재귀적인 성질을 가지고 있다.
- 트리를 다루는 코드들은 대개 재귀 호출을 이용해 구현
트리에서 한 노드와 그의 자손들을 모두 모으면 그들도 하나의 트리가 된다.
어떤 노드 t와 그 자손들로 구성된 트리를 t를 루트로 하는 서브트리(subtree) 라고 한다.
- 따라서, 모든 트리는 루트와 루트 밑에 있는 서브트리들의 집합

21.1.5 트리의 표현

트리는 다양한 방법으로 구현할 수 있다
- 가장 일반적인 형태는 각 노드를 하나의 구조체/객체로 표현하고, 이들을 서로의 포인터로 연결하는 것이다.
- 이때, 각 노드들은 자신의 부모와 모든 자손들에 대한 포인터를 가지고 있다.

기본적인(범용적인) 트리 구현

1
2
3
4
5
6
data class TreeNode<T>(
    val value: T,
    val parent: TreeNode<T>?,
    val children: MutableList<TreeNode<T>>
)
// parent 없이, children 만 있어도 된다.

자식 노드의 포인터를 담는 배열 대신, 두 포인터 left, right를 이용해 자식들을 저장할 수 도 있다. (이진 검색 트리)

21.2 트리의 순회

트리는 트리의 재귀적 속성을 이용해서 순회를 해야 한다.
- 트리에 N개의 노드가 있을 때, 시간복잡도: 모든 노드에 대해서 한 번씩 재귀 함수가 호출 됨으로, O(N)
서브트리의 개념을 이용하면 트리의 높이 또한 재귀적으로 정의할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
N = int(input())
tree = {}  # 딕셔너리 형태로 선언

for _ in range(N):
    root, left, right = input().split()
    tree[root] = [left, right]

def preOrder(now):  # root -> left -> right, 전위
    if now == '.':
        return  # 자식 노드가 없는경우
    print(now, end='')
    preOrder(tree[now][0])
    preOrder(tree[now][1])

def inOrder(now):  # left-> root -> right ,중위
    if now == '.':
        return  # 자식 노드가 없는경우
    inOrder(tree[now][0])
    print(now, end='')
    inOrder(tree[now][1])

def postOrder(now):  # left -> right -> root, 후위
    if now == '.':
        return  # 자식 노드가 없는경우
    postOrder(tree[now][0])
    postOrder(tree[now][1])
    print(now, end='')

preOrder('A')
inOrder('A')
postOrder('A')

21.5 요새, FORTRESS, 난이도: 중

트리의 최장 경로 찾기 문제로 접근
트리의 경로(path): 두 노드 사이를 연결하는 간선들을 트리의 경로라고 한다.
트리의 최장 경로 => 1,2번 둘 중 큰 값이다.
- 양 끝 노드가 항상 루트 혹은 리프 노드 여야 한다.
1. 가장 긴 루트-리프 경로의 길이 (== 트리의 height, 높이)
2. 가장 긴 리프-리프의 경로의 길이
리프-리프 경로들은 항상 어떤 노드까지 쭉 위로 올라가다 쭉 아래로 내려가는 형태이다.
- 최상위 노드: 경로가 올라가다가 내려가는 지점을 이 경로의 최상위 노드라 한다.
- 각 노드 마다 취상위 노드로 갖는 가장 긴 리프-리프 노드를 계산하고, 그중 최댓값을 구하면 된다.
  - => 각 서브트리의 높이를 계산한 뒤, 가장 높은 두개의 서브 트리를 선택하면 가장 긴 리프-리프 경로를 구할 수 있다.

트리 구조를 활용할 때, 구현에 따라 `visit` 변수가 필요하지 않을 수 있다.

1
2
3
4
5
6
7
8
def traverse_tree(node, node_name):
    # 자기 자신 출력
    print(node_name)
    
    # 자식 노드들을 재귀적으로 탐색
    for child in node:
        # 자식 노드가 있는 경우, 해당 자식 노드로 재귀 호출
        traverse_tree(node[child], child)

트리의 특성:
- 트리는 **사이클이 없는 비순환 그래프(acyclic graph)**입니다. 즉, 한 노드를 여러 번 방문할 일이 없습니다.
- 따라서, 한 번 방문한 노드를 다시 방문할 가능성이 없으므로 visit 리스트나 집합을 사용해서 방문 여부를 추적할 필요가 없습니다.
재귀 호출:
- 재귀적으로 각 노드를 탐색하면서, 부모 노드에서 자식 노드로만 이동하므로 무한 루프나 반복 방문이 일어나지 않습니다.
- 탐색이 자연스럽게 **깊이 우선 탐색(DFS)**처럼 동작하며, 자식이 없으면 탐색이 종료됩니다.

반면에, `visit`이 필요한 경우:

그래프 탐색:
- 만약 트리가 아니라 일반 그래프를 탐색하는 경우, 사이클이 존재할 수 있습니다. 이때는 visit 집합이나 리스트를 사용하여 노드를 여러 번 방문하지 않도록 해야 합니다.
순환 구조 탐색:
- 만약 데이터 구조가 트리가 아닌 순환 구조를 가질 가능성이 있거나, 노드를 여러 번 방문할 수 있는 경우(예: 그래프), 방문 여부를 추적하는 visit 리스트가 필요합니다.

요약

트리 구조에서는 사이클이 없기 때문에 visit 같은 방문 여부를 추적하는 변수가 필요하지 않습니다.
노드를 반복해서 방문하지 않기 때문에 재귀적으로 탐색하면 모든 노드를 한 번씩 방문하고 탐색이 종료됩니다.
그래프 같은 순환 가능성이 있는 자료구조에서는 visit 리스트가 필요할 수 있습니다.

따라서, 현재 구현에서는 **visit**이 없어도 문제없이 동작합니다.

트리 자료구조를 구현하는 방식

트리 구조에서 노드의 자식만 저장하는지 여부는 트리의 구조와 용도에 따라 달라집니다. 일반적으로 트리의 노드들은 자식에 대한 정보만 저장하는 것이 일반적이지만, 특정 상황이나 알고리즘의 필요에 따라 부모 정보나 다른 추가 정보를 함께 저장하기도 합니다.

1. 자식 노드만 저장하는 경우

일반적인 트리 구조에서는 각 노드에 대해 자식 노드들만 저장하는 것이 흔한 방식입니다. 특히 부모 노드에서 자식 노드로만 이동하는 방향성이 명확한 트리에서는 자식 노드만 저장하는 것으로 충분합니다.

예시: 자식 노드만 저장하는 트리

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from collections import defaultdict

tree = defaultdict(list)

# 부모-자식 관계 정의
tree[1] = [2, 3]  # 1번 노드의 자식: 2번, 3번
tree[2] = [4, 5]  # 2번 노드의 자식: 4번, 5번
tree[3] = [6, 7]  # 3번 노드의 자식: 6번, 7번

print(tree)
# defaultdict(<class 'list'>, {1: [2, 3], 2: [4, 5], 3: [6, 7]})

이 경우, 부모에서 자식으로의 방향성만 있으면 충분하기 때문에, 부모 노드에 자식 노드의 정보만 저장합니다. 트리 탐색이나 순회 시에는 부모에서 자식으로 내려가는 방식으로 처리할 수 있습니다.

2. 부모 노드 정보도 저장하는 경우

특정 알고리즘에서는 부모 노드 정보가 필요한 경우도 있습니다. 예를 들어, 어떤 트리에서 리프 노드에서 루트로 올라가는 경로를 추적해야 하는 경우, 부모 정보를 알아야 하므로 각 노드의 부모 정보도 저장할 수 있습니다. 또한, 이진 탐색 트리와 같은 자료 구조에서는 각 노드가 자신의 부모를 가리키는 포인터를 저장하는 경우가 많습니다.

부모 정보를 저장할 때는 두 가지 방법이 있습니다:

각 노드의 자식 노드 정보를 저장하면서, 별도의 자료구조로 부모 노드를 기록.
트리 노드 자체에 부모 정보를 저장하는 방식.

방법 1: 별도의 자료구조로 부모 정보 기록

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import defaultdict

tree = defaultdict(list)
parent = {}

# 트리 구성
tree[1] = [2, 3]
tree[2] = [4, 5]
tree[3] = [6, 7]

# 부모 정보 기록
parent[2] = 1
parent[3] = 1
parent[4] = 2
parent[5] = 2
parent[6] = 3
parent[7] = 3

print("트리:", tree)
print("부모 정보:", parent)
# 트리: defaultdict(<class 'list'>, {1: [2, 3], 2: [4, 5], 3: [6, 7]})
# 부모 정보: {2: 1, 3: 1, 4: 2, 5: 2, 6: 3, 7: 3}

이 방법은 부모 정보를 별도의 딕셔너리인 parent에 저장합니다. 이 방식은 노드에서 부모 노드로 가는 경로를 추적하거나 역방향 탐색이 필요할 때 유용합니다.

방법 2: 트리 노드에 부모 정보를 저장

트리의 각 노드가 부모 정보를 포함하도록 저장할 수도 있습니다. 예를 들어, 다음과 같이 트리를 표현할 수 있습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None  # 부모 정보 저장

# 트리 구성
root = TreeNode(1)
child1 = TreeNode(2)
child2 = TreeNode(3)

# 관계 설정
root.children.extend([child1, child2])
child1.parent = root
child2.parent = root

이 경우 각 노드는 parent 속성을 통해 부모 노드를 가리킵니다. 이를 통해 부모-자식 관계를 양방향으로 탐색할 수 있습니다.

3. 추가 정보 저장

트리의 각 노드에 추가 정보를 저장하는 경우도 있습니다. 예를 들어, 이진 탐색 트리(BST)에서는 노드에 저장된 값뿐만 아니라, 좌측 자식과 우측 자식에 대한 정보도 함께 저장합니다. 혹은 각 노드가 특정 상태나 가중치 등을 가지는 경우에도 트리 노드에 이런 정보들을 저장할 수 있습니다.

1
2
3
4
5
6
7
8
class TreeNode:
    def __init__(self, value, weight=0):
        self.value = value
        self.weight = weight  # 추가 정보 (예: 가중치)
        self.children = []

# 노드 생성
node = TreeNode(1, weight=10)  # 가중치가 10인 노드

4. 결론

자식 정보만 저장하는 것이 트리에서 일반적인 방식입니다. 이때는 부모에서 자식으로 내려가는 방향의 탐색만 가능하며, 부모 정보가 필요하지 않은 경우에 적합합니다.
부모 정보가 필요한 경우에는 별도의 자료구조를 통해 부모 정보를 저장하거나, 노드 자체에 부모 정보 필드를 포함할 수 있습니다.
트리에서 노드 간의 관계뿐만 아니라 추가적인 정보가 필요한 경우(예: 가중치, 상태 등), 이를 각 노드에 저장하는 방식으로 확장할 수 있습니다.

Reference

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만, 인사이트)
https://www.algospot.com/

21. 트리의 구현과 순회#

21.1 도입#

21.1.1 트리의 기초적인 정의와 용어#

21.1.2 트리의 구성 요소#

21.1.3 트리의 노드의 속성#

21.1.4 트리의 재귀적 속성#

21.1.5 트리의 표현#

21.2 트리의 순회#

21.5 요새, FORTRESS, 난이도: 중#

트리 구조를 활용할 때, 구현에 따라 visit 변수가 필요하지 않을 수 있다.#

반면에, visit이 필요한 경우:#

요약#

트리 자료구조를 구현하는 방식#

1. 자식 노드만 저장하는 경우#

예시: 자식 노드만 저장하는 트리#

2. 부모 노드 정보도 저장하는 경우#

방법 1: 별도의 자료구조로 부모 정보 기록#

방법 2: 트리 노드에 부모 정보를 저장#

3. 추가 정보 저장#

4. 결론#

Reference#