이진 트리 순회와 BST 연산을 설계하는 기준

순회 순서가 트리 처리 방식을 결정한다

이진 트리는 각 노드가 최대 두 개의 자식 노드를 갖는 계층형 자료구조다. 루트, 내부 노드, 리프 노드로 구성되며, 높이 h는 루트에서 리프까지 이어지는 최장 경로 길이다. 순회와 탐색, 삽입·삭제가 핵심 연산이다. 배열과 비교하면 메모리 지역성은 불리하지만, 연결 관계를 바꾸는 비용에서는 장점이 있다.

트리 전체를 방문하는 기본 규약은 다음과 같다.

Inorder(LNR)는 왼쪽 자식, 루트, 오른쪽 자식 순서로 처리한다. BST에서는 정렬된 순서의 출력에 적합하며, 정렬 검증·범위 질의·중복 제거 파이프라인에 활용할 수 있다.
Preorder(NLR)는 루트를 먼저 처리한다. 구조를 보존한 직렬화와 복원, 카탈로그화, 루트 우선 평가에 맞는다.
Postorder(LRN)는 자식 처리가 루트보다 앞선다. 식 트리처럼 서브트리 결과에 의존하는 평가, 하향식 리소스 해제, 안전한 삭제에 쓴다.

세 순회 모두 시간복잡도는 O(n)이며, 재귀 스택 또는 명시적 스택에 O(h)의 보조 공간이 필요하다. 편향 트리에서는 h = O(n)이 될 수 있다.

BST는 순서 불변식으로 탐색 경로를 좁힌다

이진 탐색 트리(Binary Search Tree, BST)는 모든 노드에서 left < root < right 관계를 지키는 이진 트리다. 이 불변식 덕분에 탐색·삽입·삭제는 평균 O(log n)에 수행할 수 있다. 반대로 균형이 무너지면 성능은 최악 O(n)까지 떨어진다.

검색과 삽입은 현재 키와 대상 키를 비교해 왼쪽 또는 오른쪽 서브트리로 내려가는 방식이다. 삭제는 대상 노드의 자식 상태에 따라 분기한다. 리프 노드는 바로 제거하고, 자식이 하나면 해당 자식으로 대체한다. 두 자식이 있으면 보통 우서브트리의 최소값, 즉 중위 후속자를 찾아 대상 노드 값에 대입한 뒤 후속자 노드를 삭제한다.

단순 BST는 구현이 쉽고 상수 계수가 유리하지만 입력 분포가 한쪽으로 치우치는 상황에 취약하다. AVL이나 Red-Black Tree 같은 균형 BST는 최악 O(log n)을 보장하는 대신 삽입·삭제 때 회전과 리밸런싱 오버헤드가 따른다.

재귀 구현은 코드가 단순하지만 깊은 트리에서 스택 오버플로 위험이 있다. 반복 구현은 명시적 스택이나 부모 포인터를 사용하며, 병목 구간의 성능을 예측하기 쉽고 tail-call 최적화를 지원하지 않는 언어에서도 안전하다.

순회 방식별로 확인할 특성

항목	Inorder	Preorder	Postorder
성능(시간)	O(n)	O(n)	O(n)
확장성(스택)	O(h)	O(h)	O(h)
일관성(순서 보장)	BST에서 정렬 순서 보장	구조 복원에 유리	의존성(자식 선처리) 보장
안정성(깊이 민감도)	편향 트리에서 위험	편향 트리에서 위험	편향 트리에서 위험
운영 편의(주요 용도)	정렬 출력/범위 질의	직렬화/복원	삭제/리소스 해제/식 평가

h는 트리 높이이며, 편향 트리에서는 h≈n이 될 수 있다.

삭제 경로에서 불변식을 유지하는 방법

키가 존재하지 않으면 트리 구조는 바뀌지 않아야 한다. 삭제가 일어난 뒤에도 left < root < right 조건을 유지해야 하며, 두 자식이 있는 노드에서는 후속자 처리와 후속자 재귀 삭제가 함께 필요하다.

⤢✕

계층 데이터 처리에 적용하는 순회 규약

검색 인덱스나 키-값 컨테이너에서는 정렬된 순회 결과를 범위 질의에 사용할 수 있다. 평균 O(log n) 탐색을 기반으로 Ordered Set이나 Map의 대체재를 설계할 수도 있다. 실서비스에서는 균형 BST 또는 B-Tree 파생 구조를 고려하는 편이 낫다. 단순 BST는 캐시 지역성과 최악 복잡도에 한계가 있다.

컴파일러와 DSL의 AST에서는 Preorder를 직렬화·복원에, Postorder를 스택 머신 코드 생성과 식 평가에 적용할 수 있다. Postorder는 하향식 리소스 해제와 소멸 순서를 보장하는 데도 맞는다.

파일시스템의 디렉터리 트리 삭제도 Postorder가 유용하다. 하위 리소스를 먼저 삭제할 수 있기 때문이다. 스냅샷이나 메타데이터를 직렬화할 때는 Preorder와 Null 마커를 조합한 포맷을 사용할 수 있다.

Python으로 구현한 순회와 BST 연산

재귀를 쓸 때는 트리 높이가 sys.getrecursionlimit()보다 작아야 한다. 이 구현은 동일 키를 우측 서브트리에 삽입한다.

# Python 3.10+
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional, List

@dataclass
class Node:
    key: int
    left: Optional[Node] = None
    right: Optional[Node] = None

# Traversal (Recursive)
def inorder(node: Optional[Node], out: List[int]) -> None:
    if not node:
        return
    inorder(node.left, out)
    out.append(node.key)
    inorder(node.right, out)

def preorder(node: Optional[Node], out: List[int]) -> None:
    if not node:
        return
    out.append(node.key)
    preorder(node.left, out)
    preorder(node.right, out)

def postorder(node: Optional[Node], out: List[int]) -> None:
    if not node:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.key)

# Inorder (Iterative)
def inorder_iter(root: Optional[Node]) -> List[int]:
    stack, out, cur = [], [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.key)
        cur = cur.right
    return out

# BST operations
def bst_search(root: Optional[Node], key: int) -> Optional[Node]:
    cur = root
    while cur:
        if key == cur.key:
            return cur
        cur = cur.left if key < cur.key else cur.right
    return None

def bst_insert(root: Optional[Node], key: int) -> Node:
    if root is None:
        return Node(key)
    cur = root
    while True:
        if key < cur.key:
            if cur.left: cur = cur.left
            else:
                cur.left = Node(key)
                break
        else:  # duplicates go right
            if cur.right: cur = cur.right
            else:
                cur.right = Node(key)
                break
    return root

def _min_node(node: Node) -> Node:
    while node.left:
        node = node.left
    return node

def bst_delete(root: Optional[Node], key: int) -> Optional[Node]:
    if root is None:
        return None
    if key < root.key:
        root.left = bst_delete(root.left, key)
    elif key > root.key:
        root.right = bst_delete(root.right, key)
    else:
        # node to delete found
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        # two children: replace with inorder successor
        succ = _min_node(root.right)
        root.key = succ.key
        root.right = bst_delete(root.right, succ.key)
    return root

if __name__ == "__main__":
    # Build BST
    keys = [7, 3, 9, 1, 5, 8, 10, 5, 9]
    root = None
    for k in keys:
        root = bst_insert(root, k)

    arr = []
    inorder(root, arr)
    print("inorder(rec):", arr)
    print("inorder(iter):", inorder_iter(root))

    arr = []
    preorder(root, arr)
    print("preorder:", arr)

    arr = []
    postorder(root, arr)
    print("postorder:", arr)

    # search/delete
    print("search 5:", bst_search(root, 5) is not None)
    root = bst_delete(root, 7)
    print("delete 7 -> inorder:", inorder_iter(root))

순회 결과는 항상 O(n) 원소 출력을 보장한다. BST의 Inorder 결과는 중복을 허용하는 경우 비내림차순으로 출력된다. 삭제 후에는 BST 불변식이 유지되는지 확인해야 한다.

순회 규약을 표준화하면 디버깅과 테스트가 단순해지고 직렬화·복원 호환성도 개선된다. 삭제 절차의 케이스 분기를 명시하면 장애 재현성과 유지보수성도 나아진다. 편향을 막아 평균 탐색·삽입·삭제 O(log n)을 유지하면 레이턴시를 줄이고 p95 지연을 안정화할 수 있으며, 순회 파이프라인은 O(n) 선형 스캔으로 일괄 처리의 처리량 예측 가능성을 높인다.