이진트리로 정렬·탐색·계층 데이터를 다루는 방법

정렬과 계층 표현을 함께 맡는 트리 구조

이진트리는 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드를 갖는 트리 구조다. 루트에서 시작해 내부 노드와 리프를 따라 내려가며 데이터를 표현하고 탐색한다. 트리의 높이(height)와 깊이(depth), 서브트리는 이 구조의 동작 특성을 설명하는 기본 단위다.

같은 이진트리라도 용도는 다르다. 키의 대소 관계를 유지하는 이진탐색트리(BST), 높이를 제어하는 AVL과 Red-Black 트리, 완전 이진트리를 활용하는 힙이 대표적이다. 완전·포화·정이진트리도 노드 배치 규칙에 따라 구분된다.

노드 배치가 메모리 접근 방식을 결정한다

연결 구조에서는 노드가 키 또는 값과 left/right 포인터를 가지며, 필요하면 parent 포인터도 둔다. 이는 연결 리스트처럼 동적 메모리 할당으로 구성할 수 있다.

완전 이진트리라면 배열 표현도 가능하다. 배열 인덱스 i의 자식은 2i+1과 2i+2로 계산할 수 있어 캐시 친화적으로 접근할 수 있다. 네트워크 전송이나 영속화가 필요할 때는 레벨 순서(BFS) 기반 직렬화를 사용할 수 있다.

높이가 탐색 비용을 좌우한다

트리 높이가 h이면 탐색·삽입·삭제의 평균 시간 복잡도는 O(h)다. 균형을 유지하면 h ≈ O(log n)가 되지만, 한쪽으로 편향된 스큐 트리는 최악 O(n)까지 성능이 떨어진다.

AVL과 Red-Black 트리는 회전 연산으로 균형을 유지해 높이 상한을 보장한다. 단순한 BST는 구현이 쉬운 대신 입력 순서에 따라 성능 편차가 커질 수 있다.

균형 트리 기준으로 탐색·삽입·삭제는 평균 O(log n)이다. n=1,000,000이면 log2 n ≈ 20 수준의 비교 횟수를 기대할 수 있다. 노드당 2~3개 포인터 오버헤드는 고려해야 하며, 완전 이진트리를 배열로 표현하면 캐시 적중률을 높일 수 있다. 균형이 유지되면 p95/99 지연을 안정화하고, 정렬 순서는 범위 질의(range query)의 효율도 높인다.

순회 방식은 트리를 읽는 순서를 정한다

전위·중위·후위·레벨 순회는 같은 트리에서 서로 다른 읽기 순서를 제공한다. BST에서 중위 순회를 수행하면 키가 정렬 순서로 출력된다.

순회는 재귀로 구현할 수 있고, 스택이나 큐를 사용하는 반복 방식으로도 구현할 수 있다. 표현식 트리 평가, 직렬화와 역직렬화, 구조적 비교에 이 방식들이 쓰인다.

BST의 불변식과 중복 키 정책

BST는 왼쪽 서브트리의 키가 루트보다 작고, 오른쪽 서브트리의 키가 루트보다 크다는 규칙을 유지한다. 삽입·삭제 과정에서 균형이 무너지면 AVL 또는 Red-Black 트리의 회전 기반 재균형을 적용한다.

중복 키를 만났을 때의 동작도 정해야 한다. 거부할지, 개수를 저장할지, 한쪽에 안정적으로 배치할지를 명시하지 않으면 삽입 정책과 검색 결과가 모호해진다.

⤢✕

키를 입력받으면 현재 노드와 비교해 좌우로 이동하거나 삽입한다. 중복 키 정책은 거부·카운트·좌측 배치 중 하나로 명시하고, 불균형이 발생하면 회전을 적용한다. 연산 뒤에는 BST 불변식과 AVL|RB 균형 조건을 검증한다.

라이브러리와 시스템에서의 활용

Java TreeMap/TreeSet과 C++ std::map은 레드-블랙 트리를 기반으로 정렬 컬렉션을 구현한다. 컴파일러와 파서는 AST나 표현식 트리로 구문 구조를 표현하고 평가한다.

이진 힙은 우선순위 큐와 작업 스케줄링에 쓰이며 Dijkstra, Prim 같은 그래프 알고리즘을 가속한다. 세그먼트 트리와 펜윅 트리(이진 인덱스 트리)는 실시간 로그·메트릭 집계에서 구간 질의와 업데이트를 처리한다. 게임·그래픽스에서는 BSP/KD-트리 계열로 충돌 감지와 가시성 판단을 최적화한다.

반복 순회로 구현한 BST

Python 3.10+ 환경에서 동작하는 예시다. 중복 키는 무시하며, 중위 순회는 재귀 대신 스택으로 수행한다.

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional, Generator

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

def insert(root: Optional[Node], key: int) -> Node:
    if root is None:
        return Node(key)
    cur = root
    while True:
        if key == cur.key:
            # 중복 정책: 무시(또는 카운트/리스트로 변경 가능)
            return root
        elif key < cur.key:
            if cur.left:
                cur = cur.left
            else:
                cur.left = Node(key)
                return root
        else:
            if cur.right:
                cur = cur.right
            else:
                cur.right = Node(key)
                return root

def 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 inorder(root: Optional[Node]) -> Generator[int, None, None]:
    stack: list[Node] = []
    cur = root
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            yield cur.key
            cur = cur.right

# 사용 예시
if __name__ == "__main__":
    root = None
    for k in [7, 3, 9, 1, 5, 8, 10]:
        root = insert(root, k)
    print(list(inorder(root)))  # [1, 3, 5, 7, 8, 9, 10]
    print(search(root, 5) is not None)  # True

이 구현은 중복 정책을 드러내고 반복 순회로 재귀 한계를 피한다. 다만 불균형은 해결하지 않으므로, 실무에서는 AVL이나 Red-Black 트리로 대체하는 편이 적합하다.

워크로드에 맞는 트리 선택

선택 기준은 범위 질의 빈도, 쓰기와 읽기의 비중, 일관된 지연 요구, 구현 복잡도를 감당할 수 있는지다. 회전과 재균형의 오버헤드는 최악 시간 보장과 맞바꾸는 비용이며, 노드 수에 따른 GC 영향과 캐시 지역성도 함께 봐야 한다.

구조	성능(평균/최악)	확장성(높이 보장)	일관성(지연 분산)	안정성(재균형 비용)	운영 편의
BST(미균형)	평균 O(log n)/최악 O(n)	보장 없음	분산 큼	비용 없음	구현 단순, 성능 변동 큼
AVL	거의 O(log n)/최악 O(log n)	매우 엄격	지연 안정	삽입/삭제 시 회전 더 빈번	구현 복잡, 조회 성능 우수
Red-Black	평균 O(log n)/최악 O(log n)	엄격	지연 안정	회전 수 평균 적음	범용 표준, 라이브러리 풍부

순서가 보장되는 컬렉션, 범위 질의, 실시간 우선순위 처리가 필요한 서비스에는 균형 이진트리를 적용할 수 있다. 범용 맵·셋은 표준 라이브러리의 Red-Black 기반 구현을 우선 활용하고, 범위 질의가 집중되면 AVL이나 세그먼트 트리를 고려한다. 디스크 인덱싱에는 B-트리군이 적합하다.