[Data Structure] 스레드 이진 트리(threaded binary tree)

---

스레드 이진 트리

 

이진 트리의 빈 포인터를 활용하여 트리 순회 속도를 향상시키기 위해 고안된 자료구조이다. 순회시 이진 트리에서 자식이 없는 노드를 만나면 일반적으로 부모노드로 돌아가지만, 스레드 이진 트리에서는 이 빈 포인터를 활용하여 그 다음 순회에 필요한 노드로 바로 찾아갈 수 있다.때문에 재귀 호출이나 스택 없이 순회가 가능하여 함수 호출에 필요한 시간을 효율적으로 절약할 수 있다.

빈 포인터를 다음 순회 노드인 후속 노드(successor)를 가리키는 스레드로 활용하게 되면 해당 포인터가 더이상 빈 포인터가 아니기 때문에 일반적인 포인터인지 스레드인지가 구분 불가능해진다. 따라서 스레드 이진 트리의 노드는 해당 포인터가 스레드인지 아닌지를 나타내는 변수가 들어간다.

이진 트리에서는 왼쪽과 오른쪽 자식이 존재하고, 따라서 왼쪽과 오른쪽 모두 빈 포인터가 될 수 있기 때문에 스레드 개수는 최대 두 개가 있을 수 있다. 만약 스레드가 하나만 있다면 이를 단일 스레드 이진 트리(single threaded binary tree)라 하고, 스레드가 두 개 있다면 이중 스레드 이진 트리(double threaded binary tree)라 한다.

 

---

간단한 구현 | C

 

이중 스레드 이진 트리의 노드는 아래와 같이 구현된다.

typedef struct ThreadedTreeNode {
    int data;
    struct ThreadedTreeNode *left;
    struct ThreadedTreeNode *right;
    int leftThread;
    int rightThread;
} ThreadedTreeNode;

이를 이용하여 중위순회를 한다면 아래와 같은 코드를 활용할 수 있을 것이다.

void inorder(ThreadedTreeNode* root) {
    ThreadedTreeNode* current = root;
    while (current->leftThread == 0) {
        current = current->left;
    }
    while (current != NULL) {
        printf("%d ", current->data);
        if (current->rightThread == 1) {
            current = current->right;
        } else {
            current = current->right;
            while (current != NULL && current->leftThread == 0) {
                current = current->left;
            }
        }
    }
}

스레드 이진 트리를 활용하면 순회는 빨라지지만, 스레드인지 아닌지를 확인하는 연산이 부가적으로 필요해지고, 때문에 여러 연산에서 구현이 복잡해지기 때문에 필요 여부를 잘 판단해야 한다.