스레드 이진트리로 구현하는 스택 없는 중위 순회

null 링크를 순회 경로로 바꾸는 방식

연결리스트 방식으로 이진트리를 표현하면 전체 링크 2n개 가운데 n+1개가 null로 남는다. 스레드이진트리(Threaded Binary Tree)는 이 빈 링크를 중위 선행(predecessor) 또는 후행(successor)을 가리키는 포인터로 바꾼다. 순회 시 별도 스택이나 재귀 호출 없이 노드를 따라갈 수 있는 구조다.

링크가 자식 포인터인지 스레드인지 구분하려면 태그 비트(tag bit)가 필요하다. ltag와 rtag가 각각 0이면 자식 링크, 1이면 스레드 링크를 뜻한다. 이 구분이 없으면 스레드를 하위 트리로 잘못 따라가는 문제가 생긴다.

중위 스레딩이 가장 일반적이며, 전위·후위 스레딩도 가능하다. 순회의 시작과 끝, 공트리 처리는 헤더 노드로 감싸면 일관되게 다룰 수 있다.

태그와 헤더가 경계를 관리한다

포인터 수는 일반 이진트리와 같지만, null이었던 링크에 의미를 부여한다. 추가 주기억 공간은 태그 비트에 해당한다.

중위 순회 중 왼쪽 자식이 없는 노드는 선행 노드를 가리키도록 만들고, 직전 노드의 오른쪽 자식이 없으면 현재 노드를 후행으로 연결한다. 이렇게 구성하면 임의 노드에서 다음 노드로 이동하는 연산은 O(1) 분기와 제한된 이동으로 처리할 수 있다.

헤더 노드는 경계 처리를 담당한다. header.rlink는 루트를 가리키고, 가장 왼쪽 노드의 llink와 가장 오른쪽 노드의 rlink는 헤더로 연결된다. 공트리와 순회 종료 조건도 같은 방식으로 정리된다.

스레드 링크를 따라가거나 자식 링크로 하향하는 결정은 ltag와 rtag 검사로 이뤄진다. 그 결과 중위 순회는 O(n)에 수행하면서도 추가 공간은 O(1)만 사용한다. 깊은 트리에서 재귀 스택 오버플로우가 발생할 위험도 없다.

읽기 경로에는 유리하고 갱신에는 비용이 따른다

스레드이진트리는 추가 스택 없이 구조를 순회해야 하는 임베디드·제한 메모리 환경에 맞는다. 반복 기반 펌웨어 루프에서 트리를 탐색할 때도 활용할 수 있다.

컴파일러나 표현식 트리에서는 중위 표기 변환과 코드 생성 과정에서 다음 노드로 빠르게 이동하는 용도로 쓸 수 있다. 스토리지 인덱스의 메모리 캐시 계층에서는 읽기 중심 탐색 경로에서 재귀를 없애 분기 예측과 캐시 지역성 향상을 기대할 수 있다. 단일 스레드 컨텍스트의 런타임·라이브러리 이터레이터에도 안전한 중위 이터레이션을 제공한다.

대신 삽입과 삭제는 단순하지 않다. 인접한 선행·후행 스레드를 함께 수정해야 하므로 표준 이진트리보다 구현 난이도와 유지 비용이 커진다. 읽기가 많은 워크로드에는 적합하지만, 쓰기가 빈번한 경우에는 이 비용을 고려해야 한다.

중위 스레딩 뒤의 순회 경로

일반 이진트리의 루트를 입력으로 받아 중위 순회하면서 null 링크를 선행·후행 스레드로 연결한다. 이어 헤더 노드를 만들고 양끝 경계와 공트리를 처리하면, 헤더 기반의 O(1) 추가 공간 순회 구조가 완성된다.

공트리에서는 header.rlink = header, ltag = 0, rtag = 1로 설정하면 순회가 곧바로 끝난다. 순회 도중에는 태그를 검사한 뒤 자식으로 내려갈지 스레드를 따라갈지 결정해야 한다. 삽입이나 삭제 뒤에는 인접 스레드를 재구성해 정합성을 유지한다.

⤢✕

일반 이진트리와 다른 운영 특성

지표	일반 이진트리(중위 재귀/스택)	스레드이진트리(중위 스레딩)
성능(순회)	O(n), 함수 호출/스택 오버헤드 존재	O(n), 분기 중심, 호출/스택 오버헤드 없음
확장성(깊이)	깊이에 비례한 스택 사용, 오버플로우 리스크	O(1) 추가 공간, 깊이 무관 안전성
일관성(순서)	안정적 중위 순서	동일, 선후 링크로 next 전진 용이
안정성	재귀 한계 의존	헤더/태그로 경계 명확, 예외 상황 단순
운영 편의	구현 단순	갱신 시 스레드 유지 비용 증가

C 구현으로 보는 중위 스레딩

이 예시는 GCC/Clang과 C11 이상을 전제로 한다. gcc -std=c11 threaded_bt.c -O2 -Wall -o threaded_bt로 빌드할 수 있으며, BST 삽입으로 트리를 만든 뒤 중위 스레딩으로 변환하고 스택·재귀 없이 순회 결과를 출력한다.

// threaded_bt.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct ThreadNode {
    unsigned char ltag;            // 0: child, 1: thread
    struct ThreadNode* llink;      // left child or predecessor
    int data;                      // payload
    struct ThreadNode* rlink;      // right child or successor
    unsigned char rtag;            // 0: child, 1: thread
} ThreadNode;

static ThreadNode* header = NULL;  // sentinel
static ThreadNode* prevInorder = NULL;

static ThreadNode* new_node(int key) {
    ThreadNode* n = (ThreadNode*)calloc(1, sizeof(ThreadNode));
    if (!n) { perror("calloc"); exit(1); }
    n->data = key;
    n->ltag = n->rtag = 0; // initially treat links as children
    n->llink = n->rlink = NULL;
    return n;
}

// BST insert (before threading)
static ThreadNode* bst_insert(ThreadNode* root, int key) {
    if (!root) return new_node(key);
    if (key < root->data) root->llink = bst_insert(root->llink, key);
    else                  root->rlink = bst_insert(root->rlink, key);
    return root;
}

// Inorder threading: convert nulls to threads using prevInorder
static void inorder_threading(ThreadNode* cur) {
    if (!cur) return;
    if (cur->ltag == 0) inorder_threading(cur->llink);

    // left null -> predecessor thread
    if (!cur->llink) {
        cur->ltag = 1;
        cur->llink = prevInorder ? prevInorder : header;
    }
    // previous right null -> successor thread
    if (prevInorder && !prevInorder->rlink) {
        prevInorder->rtag = 1;
        prevInorder->rlink = cur;
    }
    prevInorder = cur;

    if (cur->rtag == 0) inorder_threading(cur->rlink);
}

// Build header sentinel and finalize edge threads
static ThreadNode* build_threaded(TreeNode* root); // forward decl typo guard
static ThreadNode* build_threaded_internal(ThreadNode* root) {
    header = new_node(-1); // sentinel value
    header->ltag = 0;      // llink unused
    header->rtag = 1;      // rlink as thread to first when empty
    header->llink = header;
    header->rlink = root ? root : header;

    prevInorder = NULL;
    if (root) {
        inorder_threading(root);
        // close the circle: last node's successor -> header
        if (prevInorder && !prevInorder->rlink) {
            prevInorder->rtag = 1;
            prevInorder->rlink = header;
        }
        // first node's predecessor already set to header via first null-left
    }
    return header;
}

// get leftmost node starting from x (respecting ltag)
static ThreadNode* leftmost(ThreadNode* x) {
    if (!x) return NULL;
    while (x->ltag == 0 && x->llink) x = x->llink;
    return x;
}

// Inorder traversal without stack/recursion, starting from header
static void inorder_traverse(ThreadNode* hdr, void (*visit)(int)) {
    if (!hdr) return;
    ThreadNode* cur = leftmost(hdr->rlink);
    while (cur && cur != hdr) {
        visit(cur->data);
        // if thread, successor is rlink directly; else go to leftmost of right subtree
        cur = (cur->rtag == 1) ? cur->rlink : leftmost(cur->rlink);
    }
}

static void print_int(int x) { printf("%d ", x); }

int main(void) {
    // Example: build BST then convert to threaded and traverse
    int keys[] = { 30, 10, 40, 5, 20, 35, 50, 15, 25 };
    size_t n = sizeof(keys)/sizeof(keys[0]);

    ThreadNode* root = NULL;
    for (size_t i = 0; i < n; ++i) root = bst_insert(root, keys[i]);

    ThreadNode* hdr = build_threaded_internal(root);

    inorder_traverse(hdr, print_int);
    printf("\n");
    return 0;
}

스레드 상태의 트리에 직접 삽입하거나 삭제하려면 인접 선행·후행 스레드를 갱신하는 로직이 필요하다. 동시성 환경에서는 스레드 링크와 자식 링크를 일관되게 보호할 락·RCU 등의 동기화 전략도 함께 마련해야 한다.

순회 비용과 안정성의 변화

순회 시간 복잡도는 O(n)으로 동일하지만 함수 호출이 사라져 상수항이 줄어든다. 추가 메모리는 태그 비트(실제 구현상 1바이트 정렬)와 헤더 노드 1개 수준이다. 추가 스택 공간은 O(h)에서 O(1)로 줄며, h는 트리 높이다.

재귀 스택 오버플로우 없이 깊은 트리도 순회할 수 있고, 헤더와 태그를 기준으로 종료 조건을 분명히 처리할 수 있다. 이터레이터 구현도 단순해지며, next 연산을 기반으로 중위 순서에 접근하기 쉬워진다.