C++로 구현하는 스레드 이진 트리(Threaded Binary Tree)의 중위 순회

이번 글에서는 스레드 이진 트리(Threaded Binary Tree) 자료구조와 이를 활용한 중위 순회(Inorder Traversal) 방법을 알아보겠습니다.

스레드 이진 트리란?

일반적인 이진 트리에서 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다. 그런데 자식이 하나뿐이거나 아예 없는 경우, 연결 리스트 표현 방식에서는 해당 링크 포인터가 null로 남게 되어 메모리가 낭비됩니다. 스레드 이진 트리는 이렇게 비어 있는 링크 공간을 스레드(thread)로 재활용하여 효율성을 높인 자료구조입니다.

즉, 어떤 노드의 왼쪽 또는 오른쪽 자식 영역이 비어 있다면, 그 영역을 순회에 유용한 포인터(스레드)로 활용하는 것입니다. 스레드 이진 트리에는 두 가지 종류가 있습니다.

• 단일 스레드 이진 트리(Single Threaded Tree): 왼쪽 또는 오른쪽 한쪽 방향만 스레드로 사용
• 완전 스레드 이진 트리(Fully Threaded Binary Tree): 양쪽 방향 모두 스레드로 사용

노드 구조

완전 스레드 이진 트리에서 각 노드는 다섯 개의 필드를 가집니다. 일반 이진 트리 노드의 세 가지 필드(데이터, 왼쪽 링크, 오른쪽 링크)에 더해, 각 링크가 실제 자식을 가리키는 링크인지 아니면 스레드인지를 나타내는 불린(Boolean) 플래그 두 개가 추가됩니다.

다음은 완전 스레드 이진 트리의 예시입니다.

중위 순회 알고리즘

inorder():
Begin
    temp := root
    repeat infinitely, do
        p := temp
        temp = right of temp
        if right flag of p is false, then
            while left flag of temp is not null, do
                temp := left of temp
            done
        end if
        if temp and root are same, then
            break
        end if
        print key of temp
    done
End

C++ 구현 예제

아래 코드는 스레드 이진 트리에 값을 삽입하고, 스택이나 재귀 없이 중위 순회를 수행하는 전체 과정을 보여줍니다. 스레드 덕분에 순회 시 별도의 보조 자료구조가 필요하지 않다는 점이 큰 장점입니다.

#include <iostream>
#define MAX_VALUE 65536
using namespace std;

class N { // 노드 선언
    public:
        int k;
        N *l, *r;
        bool leftTh, rightTh;
};

class ThreadedBinaryTree {
    private:
        N *root;
    public:
        ThreadedBinaryTree() { // 변수 초기화 생성자
            root = new N();
            root->r = root->l = root;
            root->leftTh = true;
            root->k = MAX_VALUE;
        }

        void insert(int key) {
            N *p = root;
            for (;;) {
                if (p->k < key) { // 오른쪽 스레드로 이동
                    if (p->rightTh)
                        break;
                    p = p->r;
                }
                else if (p->k > key) { // 왼쪽 스레드로 이동
                    if (p->leftTh)
                        break;
                    p = p->l;
                }
                else {
                    return; // 중복 값은 삽입하지 않음
                }
            }

            N *temp = new N();
            temp->k = key;
            temp->rightTh = temp->leftTh = true;

            if (p->k < key) {
                temp->r = p->r;
                temp->l = p;
                p->r = temp;
                p->rightTh = false;
            }
            else {
                temp->r = p;
                temp->l = p->l;
                p->l = temp;
                p->leftTh = false;
            }
        }

        void inorder() { // 트리 출력
            N *temp = root, *p;
            for (;;) {
                p = temp;
                temp = temp->r;
                if (!p->rightTh) {
                    while (!temp->leftTh) {
                        temp = temp->l;
                    }
                }
                if (temp == root)
                    break;
                cout << temp->k << " ";
            }
            cout << endl;
        }
};

int main() {
    ThreadedBinaryTree tbt;
    cout << "Threaded Binary Tree\n";
    tbt.insert(56);
    tbt.insert(23);
    tbt.insert(89);
    tbt.insert(85);
    tbt.insert(20);
    tbt.insert(30);
    tbt.insert(12);
    tbt.inorder();
    cout << "\n";
}

실행 결과

Threaded Binary Tree
12 20 23 30 56 85 89

정리

스레드 이진 트리는 null 포인터로 낭비되던 공간을 스레드로 활용하여, 재귀 호출이나 스택 없이도 선형 시간에 중위 순회를 수행할 수 있게 해주는 자료구조입니다. 특히 메모리 사용량을 줄이면서 순회 성능을 개선하고 싶은 상황에서 유용하게 활용할 수 있습니다.