[자료구조] 스레드 이진트리

목표

스레드 이진 트리에 대해 알아보자

들어가기 전 

본 글에서 직접적으로 설명하지 않지만, 언급하고 있는 내용입니다. 

• 중위 순회

스레드 이진 트리

---

스레드 이진 트리란?

이진 트리의 한 종류로, 중위 순회 시 모든 왼쪽 널 포인터에 중위 선행자 또는 모든 오른쪽 널 포인터에 중위 후속자를 연결한 트리

 

스레드 이진트리는 중위 순회를 하며, 기존의 스택을 사용하여 재귀적으로 순회하던 방식과 달리 중위 후속자를 가리키는 포인터를 통해 재귀적인 방법 없이 빠르게 순회한다.

출처: 위키백과

 

스레드 이진 트리를 왜 사용하는가?

 

이진 트리의 순회를 순환 호출(재귀) 없이 효율적으로 빠르게 하기 위함이다. 일반적으로 이진 트리는 순회 시 스택을 이용 순환 호출(=재귀 호출)을 사용하는데 함수를 반복 호출해야 한다는 점에서 오버헤드가 발생하기 때문에 비효율적이다. 또한, 노드의 개수가 n일 때, 각 노드당 2개의 링크가 연결되어 있으므로 전체 링크의 수는 2n이다. 이들 중 루트를 제외한 n-1개의 노드가 부모와 연결되어 있으므로(=간선 수) 나머지 n+1개의 링크는 항상 NULL이다.  이처럼 낭비되는 링크 필드(메모리)와 순환 호출의 느린 속도를 보완하기 위해 순환 호출 방법 대신 포인터를 이용하여 순회하는 방법이 스레드 이진 트리이다. 순회를 빠르게 하는 대신 스레드 설정을 위해 함수 내에서 더 많은 일을 하도록 설계해야하는 것이 단점이다.

 

스레드, 중위 선행자, 중위 후속자란?

스레드	스레드란 실을 이용하여 노드들을 순회 순서대로 포인터로 연결시켜 놓은 것을 의미한다. 일반적으로 알고 있는 OS 프로세스의 멀티스레딩과 관련된 스레드와는 다른 의미이다.
중위 선행자	중위 선행자란 중위 순회 시 직전에 방문한 노드를 의미한다.
중위 후속자	중위 후속자란 중위 순회 시 다음에 방문할 노드를 의미한다.

 

스레드 이진트리를 어떻게 사용하는가?

 

C언어를 이용한 스레드 이진 트리 코드를 통해 설명한다. 

스레드 이진 트리는 아래 2가지를 해야 한다.

 

• 스레드 이진 트리 순회 시 오른쪽 링크가 가리키는 것이 자식 노드인지, 스레드(중위후속자)인지 구분하기 위해 노드 구조체에 구분용 변수 bIsThread를 추가한다.
• 노드 오른쪽 null 링크에 중위 후속자를 지정한다.

 

1. 스레드 구분용 변수 추가

오른쪽 링크가 자식 노드인지 스레드인지 구분용 변수 bIsThread를 추가한다.

bIsThread가 오른쪽 링크를 기준으로 하는 이유는 중위후속자(다음에 순회할 노드)를 가리킬 링크 필드는 1개면 충분하기 때문이고, 오른쪽 서브 트리는 왼쪽/루트를 모두 방문한 후 가장 나중에 방문하기 때문이다.

• true - 오른쪽 링크는 스레드이다. (=중위후속자)
• false - 오른쪽 링크는 자식 노드이다.

struct tTreeNode {
    char iData;
    tTreeNode* pLeft;
    tTreeNode* pRight;
    bool bIsThread; // 만약 오른쪽 링크가 스레드이면 true 아니면 fale
};

 

2. 오른쪽 null 링크에 중위 후속자를 지정한다.

중위 후속자를 지정하기 위해선 중위 순회의 순서를 당연히 알고 있어야 한다.

중위 순회는 왼쪽(L) → 루트(V)  → 오른쪽(R) 순으로 순회한다. 

 

    tTreeNode Node1 = { 'A',NULL,NULL,true };
    tTreeNode Node2 = { 'B',NULL,NULL,true };
    tTreeNode Node3 = { 'C',&Node1,&Node2, false };
    tTreeNode Node4 = { 'D',NULL,NULL, true };
    tTreeNode Node5 = { 'E',NULL,NULL, false };
    tTreeNode Node6 = { 'F',&Node4,&Node5, false };
    tTreeNode Node7 = { 'G',&Node3,&Node6, false };
    tTreeNode* test = &Node7;

 

 

오른쪽 null 링크에 중위 후속자를 지정한다.

   Node1.pRight = &Node3;
   Node2.pRight = &Node7;
   Node4.pRight = &Node6;

 

3. 순회 코드

• bIsThread == true, 오른쪽 링크는 중위 후속자
  • 중위 후속자로 이동
• bIsThread == false, 오른쪽 링크는 자식 노드
  • 자식 노드로 이동 후, 가장 왼쪽 노드로 이동

// 중위 순회 스레드
void Thread_InOrder(tTreeNode* InNode)
{
    tTreeNode* pNode = InNode;
    // 가장 왼쪽 노드로 이동
    while (nullptr != pNode->pLeft)
    {
        pNode = pNode->pLeft;
    }

    // null이 아닐 때까지 반복
    do
    {
        printf("%c->", pNode->iData);
        pNode = Find_Successor(pNode);
    } while (nullptr != pNode);

}

// 중위후속자 찾는 노드
tTreeNode* Find_Successor(tTreeNode* pNode)
{
    // 오른쪽 포인터가 null이거나 스레드면 오른쪽 포인터 반환
    if (nullptr == pNode->pRight
        || true == pNode->bIsThread)
        return pNode->pRight;

    // 오른쪽 자식이라면 가장 왼쪽 노드로 이동
    while (nullptr != pNode->pRight->pLeft)
        pNode->pRight = pNode->pRight->pLeft;
    return pNode->pRight;
}