스레드 이진 트리

스레드 이진 트리

스레드 이진 트리(Threaded binary tree)는 이진 트리의 한 종류로, 가리키는 곳이 없는 모든 오른쪽 널 포인터(null pointer)를 중위 후속자 노드로 연결하고, 가리키는 곳이 없는 모든 왼쪽 널 포인터를 중위 선행자 노드로 연결한 것을 말하며, 재귀적인 중위 순회를 빠르게 할 수 있는 방법으로 사용된다.

이는 또한 조금 느리더라도 부모 포인터나 스택을 사용하지 않고도 스레드 이진 트리에서 노드의 부모를 찾을 수 있게 해 준다. 이는 스택 공간을 쓸 수 없거나, 부모 노드의 위치를 알 수 없을 때 유용하게 사용될 수 있다.

예시

어떤 노드 k가 오른쪽 자식 노드 m을 가지고 있다면 m의 왼쪽 포인터는 왼쪽 자식이나 스레드를 통해 다시 k를 가리킬 수 있다. 또한 노드 k가 왼쪽 자식 노드 n을 가지고 있다면 n의 오른쪽 포인터는 오른쪽 자식이나 스레드를 통해 다시 k를 가리킬 수 있다. 이는 어떠한 노드의 자식이 그 부모가 되는 상황과 비슷하다.

구현

C 코드로 스레드 이진 트리를 나타내면,

Node* parent(Node* node)
{
    Node *x, *y, *p;
    if (node == root)
        return null;
    x = y = node;
    while (1)
    {
        if ( is_thread(y->right) )
        {
            p = y->right;
            if (p == null || p->left != node)
            {
                p = x;
                while ( !is_thread(p->left) )
                    p = p->left;
                p = p->left;
            }
            return p;
        }
        else if ( is_thread(x->left) )
        {
            p = x->left;
            if (p == null || p->right != node)
            {
                p = y;
                while ( !is_thread(p->right) )
                    p = p->right;
                p = p->right;
            }
            return p;
        }
        x = x->left;
        y = y->right;
    }
}

외부 링크

• (영어) 스레드 이진 트리 튜토리얼
• (영어) GNU libavl 2.0.2의 스레드 이진 탐색 트리