트리 구조와 순회 알고리즘

트리 모델과 관계 어휘

트리는 노드와 노드를 잇는 간선으로 계층을 표현하는 자료구조입니다. 이 글에서는 간선의 방향을 부모에서 자식으로 고정하고, 하나의 루트에서 모든 노드로 가는 경로가 하나뿐인 유한 구조를 트리라고 하겠습니다. 따라서 일반 그래프처럼 임의의 순환이나 여러 부모를 허용하지 않습니다.

구조의 시작 노드를 root(루트), 바로 위 노드를 parent(부모), 바로 아래 노드를 child(자식)라고 부릅니다. 부모가 없는 노드는 루트 하나뿐이고, 자식이 없는 노드는 leaf(잎)입니다. 자식이 하나라도 있는 노드는 internal node(내부 노드)이며, 같은 부모를 직접 공유하는 노드들은 sibling(형제)입니다.

어떤 노드와 그 아래 모든 자손을 묶은 것을 subtree(부분 트리)라고 합니다. 루트의 depth(깊이)는 0으로 두고, 부모에서 자식으로 한 간선을 내려갈 때마다 1을 더합니다. 한 노드에서 그 아래 가장 먼 잎까지의 간선 수를 height(높이)로 두면, 빈 트리의 높이는 -1, 단일 노드의 높이는 0입니다.

노드가 직접 가진 자식 수는 degree(차수)이고, 구조 전체에서 허용하는 최대 자식 수는 branching factor(분기 수)입니다. 차수는 한 위치의 폭이고 높이는 아래로 남은 길이이므로 서로 대체할 수 없습니다. 넓고 얕은 트리와 좁고 긴 트리는 같은 노드 수에서도 전혀 다른 순회 비용을 만듭니다.

이진 트리의 형태

이진 트리는 각 노드가 왼쪽·오른쪽 자식을 최대 하나씩 갖는 트리입니다. 이진이라는 말만으로 키가 정렬되거나 높이가 작다는 뜻은 아닙니다. 이진 탐색 트리(BST)는 여기에 비교자 기준의 왼쪽·오른쪽 순서 조건을 추가합니다.

형태	구조 조건	예시
정 이진 트리(full/proper)	각 노드의 자식 수가 0 또는 2	루트의 왼쪽은 잎, 오른쪽은 자식 둘을 가진 내부 노드
포화 이진 트리(perfect)	내부 노드의 자식이 둘이고 모든 잎의 깊이가 같음	높이 2에 노드 7개
완전 이진 트리(complete)	마지막 층을 제외한 모든 층이 차고 마지막 층은 왼쪽부터 채워짐	배열 힙의 모양

영문 full과 한국어 번역은 교재마다 혼용되므로 이름보다 위 조건을 함께 표기합니다. 루트 깊이를 0으로 두면 높이 h인 포화 이진 트리의 노드 수는 2^(h+1)-1, 잎 수는 2^h입니다. 완전 이진 트리는 마지막 부모에게 왼쪽 자식만 있을 수 있어 항상 full은 아닙니다. 반대로 full 트리의 두 가지 높이가 크게 다르면 complete나 균형 트리일 필요가 없습니다.

완전 이진 트리를 0부터 시작하는 배열에 넣으면 i의 자식 위치는 2i+1, 2i+2이고 i>0의 부모는 floor((i-1)/2)입니다. 일반 희소 트리에 같은 배치를 강제하면 빈 인덱스가 많아질 수 있습니다. 힙은 이 구조와 부모·자식 우선순위 조건을 사용하며, BST의 중위 정렬 조건과는 다릅니다.

구조 불변식과 경계 조건

다음은 이 글에서 사용할 일곱 키의 이진 탐색 트리입니다. 순회 알고리즘은 일반 트리에도 적용되지만, 숫자 순서가 특별한 의미를 갖는 부분에서는 BST 조건을 별도로 표시합니다.

그림을 글로 읽기

• 8 · depth 0: root · height 3
• 3 · depth 1: left child
• 10 · depth 1: right child
• 1 · depth 2: leaf
• 6 · depth 2: internal
• 14 · depth 2: leaf
• 4 · depth 3: leaf

1. 8 · depth 0 → 3 · depth 1: left
2. 8 · depth 0 → 10 · depth 1: right
3. 3 · depth 1 → 1 · depth 2: left
4. 3 · depth 1 → 6 · depth 2: right
5. 10 · depth 1 → 14 · depth 2: right
6. 6 · depth 2 → 4 · depth 3: left

이 구조에서 8은 루트이고 3과 10은 형제입니다. 6의 부분 트리에는 6과 4가 들어갑니다. 1, 4, 14는 잎이고, 자식을 가진 3, 6, 8, 10은 내부 노드입니다.

트리의 핵심 불변식은 루트에서 내려갈 때 같은 노드를 다시 만나지 않고, 각 노드에 부모 경로가 하나만 있다는 점입니다. parent 포인터를 저장한다면 child가 parent를 가리키는 역방향 링크도 함께 맞아야 합니다. 링크를 먼저 바꾸고 역방향 링크나 높이를 나중에 고치는 동안 중간 구조를 독자에게 공개하면 순회 결과가 상태에 따라 달라집니다.

입력이 외부에서 오거나 메모리 손상 가능성이 있다면 방문 집합 또는 방문 상한을 둡니다. 동일 노드를 다시 만난 사실은 정상적인 “두 번째 방문”이 아니라 트리 계약 위반입니다. 다만 공유 노드를 허용하는 DAG를 일부러 저장한다면 그것은 다른 자료구조 계약이므로, 방문 집합을 오류로 볼지 중복 제거로 볼지를 먼저 선언해야 합니다.

빈 트리와 단일 노드는 구현의 사소한 예외가 아닙니다. 빈 트리 순회는 빈 결과 또는 callback 0회로 고정하고, 단일 노드는 네 순회에서 정확히 한 번 방문하게 합니다. 이 규칙을 고정하면 호출자가 null root를 매번 별도로 추측하지 않아도 됩니다.

순회 사건과 실행 상태

순회는 노드를 나열하는 것보다 풍부한 계약입니다. 한 노드에 들어가는 enter, 실제 작업을 호출하는 visit, 자식 작업을 예약하는 children scheduled, 자식 처리가 끝나 돌아오는 exit 사건을 구분하면 재귀와 반복 구현을 같은 상태 기계로 볼 수 있습니다.

preorder는 enter 직후 현재 노드를 처리하고 자식으로 내려갑니다. postorder는 모든 자식이 끝난 뒤 exit 시점에 부모를 처리합니다. inorder는 이진 트리에서 왼쪽 자식, 현재 노드, 오른쪽 자식의 순서를 사용합니다. level-order는 큐를 이용해 깊이가 작은 노드를 먼저 처리합니다.

재귀 DFS의 호출 프레임은 아직 처리하지 않은 자식과 복귀 시점을 보관합니다. 명시적 스택으로 바꾸면 이 정보를 프레임 또는 상태 비트로 직접 저장해야 합니다. 노드 포인터만 넣고 빼는 단순 스택은 preorder에는 충분하지만, postorder의 “자식 완료 후 부모 처리”를 표현하지 못합니다.

callback이 중단을 요청할 수 있다면 완료, 중단, 구조 오류, 예산 초과를 서로 다른 결과로 반환합니다. 중단된 방문 수를 완성된 결과로 포장하면 호출자는 전체 트리를 검사했다고 오해합니다. 깊이·방문 수·시간 예산도 같은 이유로 명시적인 실패 상태가 필요합니다.

예제 트리와 방문 순서

예제 트리의 preorder는 8, 3, 1, 6, 4, 10, 14입니다. 루트를 먼저 처리하고 왼쪽 부분 트리 전체를 끝낸 뒤 오른쪽 부분 트리로 이동하기 때문입니다.

inorder는 1, 3, 4, 6, 8, 10, 14입니다. 이 결과가 정렬된다는 성질은 모든 트리의 성질이 아닙니다. 각 노드의 왼쪽 키가 비교자보다 작고 오른쪽 키가 크다는 BST 순서 불변식이 있을 때만 inorder가 비교자 순서가 됩니다.

postorder는 1, 4, 6, 3, 14, 10, 8입니다. 하위 표현을 먼저 계산하거나 자식 자원을 먼저 해제할 때 유용합니다. level-order는 8, 3, 10, 1, 6, 14, 4이며 깊이 0, 1, 2, 3의 순서가 보존됩니다.

방문 수는 네 순회 모두 7이지만, 방문 수만으로 순서가 맞다고 말할 수는 없습니다. 기준 순서와 중복 방문 집합을 함께 비교해야 하며, 구조 검증은 순회 결과와 분리해야 합니다.

스택·큐 상태 추적

아래 표의 스택과 큐는 각 단계에서 현재 노드를 꺼낸 뒤 남은 “다음 처리 순서”를 왼쪽부터 적은 것입니다. DFS는 오른쪽 자식을 먼저 넣고 왼쪽 자식을 나중에 넣어 왼쪽이 먼저 pop되게 합니다.

단계	preorder 처리	스택의 다음 순서	level-order 처리	큐의 다음 순서
0	8	3, 10	8	3, 10
1	3	1, 6, 10	3	10, 1, 6
2	1	6, 10	10	1, 6, 14
3	6	4, 10	1	6, 14
4	4	10	6	14, 4
5	10	14	14	4
6	14	비어 있음	4	비어 있음

예를 들어 8을 처리할 때 3을 먼저 넣고 10을 나중에 넣으면 10이 먼저 나옵니다. 원하는 preorder를 얻으려면 10을 넣은 뒤 3을 넣어 스택의 top을 3으로 만들어야 합니다. 논리적 방문 순서와 물리적 push 순서가 반대가 되는 지점입니다.

level-order에서는 10을 꺼내고 14를 넣으면 큐가 1, 6, 14가 됩니다. 이어 1을 꺼내면 6, 14, 6을 꺼내고 자식 4를 넣으면 14, 4가 됩니다. 이 중간 상태를 생략하면 방문 순서는 맞아 보여도 큐 구현의 head·tail 전이를 검증할 수 없습니다.

postorder는 프레임에 다음 자식과 복귀 상태를 보관합니다. 8에 들어가 3으로 내려가고, 3의 1과 6, 6의 4를 마친 뒤 6, 3, 마지막으로 8을 처리합니다. 자식 완료 표시가 없으면 부모로 돌아온 시점을 잃습니다.

중위 순서와 비교자 계약

BST에서 inorder를 정렬 검사로 사용할 때는 비교자의 전순서(total order)를 고정해야 합니다. 전순서는 임의의 두 키를 비교할 수 있고, 비교 결과가 일관되며, 동치 관계가 순서를 깨뜨리지 않는 비교 규칙입니다. 문자열 대소문자, null, 동점 키, 보조 ID를 호출부마다 다르게 처리하면 같은 구조가 서로 다른 결과를 냅니다.

중복 키를 허용한다면 같은 키를 왼쪽에 둘지 오른쪽에 둘지 정책을 정하거나 (key, uniqueId)를 비교해 전순서를 만듭니다. 키를 하나의 count로 합치면 inorder에서 키가 한 번만 보이므로, “원소 수”와 “서로 다른 키 수”의 의미가 달라집니다.

일반 트리의 inorder는 기본 순서가 아닙니다. 자식이 둘보다 많거나 자식 순서가 의미 없는 구조에서는 preorder, postorder, level-order 가운데 작업 목적에 맞는 순서를 선택하고, 필요하면 자식 정렬 기준을 별도 계약으로 둡니다.

삭제 순서와 독자 수명

scene graph 같은 계층 객체를 삭제할 때는 먼저 부모의 child 링크에서 부분 트리 루트를 분리합니다. 그러면 새 순회가 더 이상 삭제 대상에 들어가지 않고, 이미 읽기 시작한 독자에게는 해당 부분 트리를 유지할 수 있는 경계가 생깁니다. 그 뒤 자식부터 postorder로 자원을 회수합니다.

예를 들어 3 아래의 1, 6, 4를 삭제한다면 8의 왼쪽 링크를 먼저 비우고, 1, 4, 6, 3 순서로 해제합니다. 실제 메모리 free는 순회 종료와 같지 않을 수 있습니다. 다른 스레드가 snapshot을 pin하고 있으면 독자가 끝날 때까지 옛 노드를 보존해야 합니다.

이 규칙은 BST 키 삭제의 successor 교체와는 별개의 문제입니다. BST에서 두 자식 노드를 가진 키를 제거하는 순서와, 일반 계층 객체의 소유 자원을 회수하는 postorder를 한 함수의 암묵적 동작으로 합치지 않습니다.

구현 계약과 의사코드

아래 코드는 특정 언어의 완성 API가 아니라, 유효한 엄격한 트리에서 명시적 스택으로 preorder를 수행하는 의사코드입니다. callback은 continue 또는 stop을 반환하고, 같은 객체를 두 번 만나면 구조 오류로 처리한다고 가정합니다.

preorder(root, visit):
    if root is null:
        return completed(count=0)
    stack = [root]
    seen = empty set
    while stack is not empty:
        node = stack.pop()
        if node is already in seen:
            return invalid_structure(count=seen.size)
        seen.add(node)
        if visit(node) == stop:
            return stopped(count=seen.size)
        if node.right exists:
            stack.push(node.right)
        if node.left exists:
            stack.push(node.left)
    return completed(count=seen.size)

실제 구현에서는 깊이와 방문 수 상한을 넘었을 때 budget_exceeded를 반환합니다. callback이 예외를 던지면 구조 오류와 구분해 callback_failed로 감싸거나, 호출자에게 예외를 전달할지 API에서 정합니다. 독자가 순회 중 노드를 삭제할 수 있다면 immutable snapshot, writer 잠금, pin 중 하나를 먼저 선택해야 합니다.

복잡도와 실패 진단

유효한 트리의 모든 노드를 한 번씩 방문하는 순회 시간은 노드 수를 n이라 할 때 O(n)입니다. 재귀 DFS의 추가 공간은 트리 높이 h에 비례하고, 이진 트리의 명시적 DFS 스택은 O(h)이고 편향·형태에 따라 비용이 달라집니다. 위 의사코드는 구조 오류 검출을 위해 별도의 seen 집합을 사용하므로 전체 추가 공간은 O(n)입니다. level-order 큐의 최대 공간은 한 깊이의 폭에 비례하며, 균형 트리와 편향 트리에서 서로 다른 값을 보입니다.

방문 수가 예상보다 크면 cycle, 중복 child 등록, 동일 객체 alias를 먼저 확인합니다. 방문 수는 맞지만 inorder만 틀리면 자식 방향이나 비교자를 확인합니다. 삭제 중 crash가 나면 parent 분리, snapshot pin 종료, 실제 free의 순서를 사건 로그로 재구성합니다.

운영 로그에는 traversal ID, root generation, 방문 수, 종료 상태, 최대 stack/queue 크기, 취소 시각을 기록합니다. 이 값들은 성능을 자동으로 보장하지 않지만, 무한 순회와 단순한 “빈 결과”를 구별하는 진단 근거가 됩니다.

검증 범위와 연결 지점

검증 입력에는 빈 트리, 단일 노드, 완전 이진 트리, 한쪽으로 긴 트리, 동점 키, 잘못된 parent cycle을 넣습니다. 네 순회의 기준 순서를 독립적으로 작성하고, 각 노드가 한 번만 방문됐는지와 높이·깊이 정의가 일치하는지를 함께 확인합니다.

균형 BST의 회전과 높이 제한은 검색 트리의 회전과 색 균형 복구에서 이어집니다. Trie의 접두 경로와 메모리 비용은 같은 parent-child 경로에 terminal 의미를 추가한 사례입니다. 공간 트리는 여기에 공간 bound를 붙이고 같은 순회 사건을 재사용합니다.

참고 자료와 검증 범위

• 검색 트리의 회전과 색 균형 복구 — repository note, 2026-09-17 확인. BST 순서와 높이·회전 불변식의 연결에 적용했습니다.
• Trie의 접두 경로와 메모리 비용 — repository note, 2026-09-17 확인. terminal과 공통 경로의 비교 사례에 적용했습니다.
• 공간 후보의 보수성·Grid·AABB Tree·계층 전환 — repository note, 2026-09-17 확인. 공간 인덱스가 같은 순회 원리를 어떻게 확장하는지 연결하는 데 사용했습니다.
• 외부 공식 문서나 특정 라이브러리 버전은 이 장의 근거로 사용하지 않았습니다. 일반 트리 정의와 예제 순서는 설명을 위해 직접 계산했습니다.
• 실행 범위 — repository 빌드·테스트·benchmark를 실행하지 않았습니다. 표의 상태와 순회 결과는 손으로 대조한 설명이며 실행 성공이나 측정 결과가 아닙니다.