스레드 트리, 개념, 구현, 연산 (순회 삽입 삭제)

스레드 트리

개요

• 스레드 트리의 발생 배경: 이진 트리의 순회 과정에서 스택을 사용하여 관리하는 번거로움을 해결하기 위해 등장. 이 과정에서 방문하지 않은 노드들을 스택에 저장하는 대신, 스레드라는 포인터를 사용하여 순회를 효율적으로 수행한다.
• 스레드 트리의 특징: 스레드 트리는 오른쪽 및 왼쪽 스레드를 활용하여 순회 순서를 유지한다. 오른쪽 스레드는 후속 노드를, 왼쪽 스레드는 선행 노드를 가리킨다.

개념

• 스레드의 정의와 역할: 스레드는 특정 순회 방법에 따라 다음에 방문할 노드를 가리키는 포인터이다. 이를 통해 순회 과정에서 다음 노드로의 이동이 간소화된다.
• 스레드 트리의 구현 방식:
  • 포인터 추가 방식: 이 방법은 왼쪽 및 오른쪽 스레드 포인터 필드를 추가하여 노드 구조를 확장한다. 기억장소 부담이 커질 수 있다.
  • 빈 포인터 활용 방식: 기존 이진 트리의 노드 구조를 유지하면서, 잎 노드의 빈 포인터를 활용한다. 이 경우, 포인터가 스레드인지 서브트리 포인터인지 구분하기 위해 태그 필드가 필요하다.
• 스레드 트리의 장단점: 스레드를 활용함으로써 순회 과정이 간편해지고 효율적으로 이루어진다. 그러나 트리에서 노드의 삽입과 삭제 연산이 복잡해질 수 있다.
• 스레드 트리의 활용: 예를 들어, 전위, 중위, 후위 순회 방법을 적용할 때 각각의 순회 순서를 유지하는 스레드 트리를 구성할 수 있다. 이를 통해 다양한 순회 방식에서의 효율적인 노드 방문이 가능하다.

스레드 트리는 이진 트리의 순회 과정을 개선하기 위해 개발된 특별한 형태의 이진 트리이다. 기존의 이진 트리 순회에서 스택을 사용하는 대신, 스레드라는 포인터를 도입하여 순회 과정의 효율성을 높였다. 스레드 트리는 오른쪽 및 왼쪽 스레드를 활용해 순회 순서를 유지하며, 이를 통해 순회 과정에서 다음 노드로의 이동을 간소화한다.

 

전위 순회

중위 순회

후위 순회

스레드 트리의 구현

스레드 트리를 구현하는 두 가지 주요 방법이 있다. 첫 번째는 노드 구조에 스레드 포인터 필드를 추가하는 것이고, 두 번째는 기존 이진 트리의 구조를 유지하면서 사용하지 않는 포인터를 활용하는 방법이다.

 

포인터 추가 방식

이 방식에서는 각 노드에 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 등 다섯 가지 필드를 추가한다. 구조체는 다음과 같이 정의된다.

typedef struct tfNode{ 
   struct tfnode *left;
   struct tfnode *lthread;
   char data;
   struct tfnode *right; 
   struct tfnode *rthread; 
} tfnode; 

 

자바 코드 구현

class ThreadedTreeNode {
    ThreadedTreeNode left, right;
    boolean lthread, rthread;
    int data;

    ThreadedTreeNode(int item) {
        data = item;
        left = right = null;
        // 처음에 스레드 플래그는 false로 설정
        lthread = rthread = false;
    }
}

// 여기서 lthread와 rthread는 각각 왼쪽과 오른쪽 포인터가 실제 자식 노드를 가리키는지 아니면 스레드를 가리키는지를 나타내는 불리언 플래그.

 

각 노드는 이러한 포인터들을 통해 다른 노드와 연결되며, 스레드 트리를 중위 순회하는 비순환 알고리즘을 구현할 때 이 포인터들이 활용된다. 이 방식의 장점은 스레드 트리의 순회가 매우 간단해진다는 것이지만, 추가적인 메모리 사용이 단점으로 작용한다.

빈 포인터 활용 방식

이 방법은 기존 이진 트리의 노드 구조를 변경하지 않고, 잎 노드의 빈 포인터를 스레드로 활용한다. 잎 노드는 자식 노드가 없으므로, 보통 이 포인터들은 null 값으로 채워진다. 이 방법에서는 null 포인터를 스레드로 사용하여, 이진 트리를 중위 순회할 때 어떤 노드 x에 대해 오른쪽 포인터가 null이면 이 포인터를 x 다음으로 순회되는 노드를 가리키도록 설정한다.

 

class TreeNode {
    TreeNode left, right;
    int data;

    TreeNode(int item) {
        data = item;
        left = right = null;
    }
}

 

노드 구조는 기존 이진 트리의 노드 구조와 동일하게 유지되지만, 포인터가 스레드인지 아니면 서브 트리 포인터인지를 구분하기 위해 태그 필드를 사용해야 한다. 이 방법의 장점은 추가적인 메모리 사용이 없다는 점이다. 그러나, 스레드 트리의 노드 삽입과 삭제 연산이 복잡해진다는 단점이 있다.

예시: 중위 순회

void inorder(tfNode *startNode) { 
   tfNode *ptr; 
   while (ptr != null) { 
       printf("%d", ptr -> data); 
       ptr = ptr -> rthread; 
   }
}

자바 코드

void inorder(ThreadedTreeNode startNode) {
    ThreadedTreeNode ptr = startNode;
    while (ptr != null) {
        // 왼쪽 스레드가 실제 자식 노드를 가리키는지 확인
        while (ptr.lthread == false) {
            ptr = ptr.left;
        }
        // 데이터 출력
        System.out.print(ptr.data + " ");

        // 오른쪽 스레드를 따라가며 순회
        while (ptr.rthread == true) {
            ptr = ptr.right;
            System.out.print(ptr.data + " ");
        }
        // 다음 노드로 이동
        ptr = ptr.right;
    }
}

 

이 예시는 중위 순회를 수행하는 비순환 알고리즘이다. 시작 노드를 가리키는 포인터 startNode를 매개변수로 전달하고, 순회를 위해 ptr 포인터를 사용한다. 데이터를 출력한 후 ptr을 오른쪽 스레드로 업데이트하여 순회를 계속한다. 이 알고리즘은 스레드 트리의 구조를 이용하여 스택이나 재귀 호출 없이 순회를 가능하게 한다.

스레드 트리 순회, 삽입, 삭제

1. 스레드 트리 순회

스레드 트리의 순회는 이진 트리 순회와 다른 특별한 접근 방식을 필요로 한다. 중위 순회를 예로 들면, 스레드 트리의 중위 순회는 노드의 threadFlag를 확인하여 스레드를 통한 순회를 결정한다.

typedef struct tfNode { 
    struct tfNode *left;
    char data;
    struct tfBode *right;
    int threadFlag;
} tfNode;

tfNode* inorderStart(tfNode* ptr) { 
    if(ptr==null) return null; 
    while (ptr -> left != null ) ptr = ptr -> left; 
    return ptr; 
}

void inorder(tfNode* root){
    tfNode* ptr = inorderStart(root);
    while(ptr !=null) { 
       printf("%c", ptr -> data); 
       if (ptr -> threadFlag) ptr = ptr -> right;
       else ptr = inorderStart(ptr -> right);
       }
    }

• 초기 단계: 순회를 시작하기 위해 가장 왼쪽 노드를 찾는다. inorderStart 함수는 가장 왼쪽 노드로 이동하여 순회의 시작점을 반환한다.
• 순회 과정: 순회는 현재 노드의 데이터를 처리한 후(printf 사용) threadFlag 값을 검사하여 다음 노드로 이동한다.
  • threadFlag가 참이면 오른쪽 포인터는 스레드를 통해 다음 노드를 가리킨다. 이 경우, 현재 노드의 오른쪽 포인터를 따라 다음 노드로 직접 이동한다.
  • threadFlag가 거짓이면 오른쪽 포인터는 실제 자식 노드를 가리킨다. 이 경우, inorderStart 함수를 사용하여 오른쪽 서브트리에서 다시 가장 왼쪽 노드로 이동한다.
• 순회 예시: 예를 들어, 교재에서 노드 '/', '+', '', '+'는 실제 자식 노드를 가리키는 반면, 노드 'A'와 'B'는 각각 노드 '+', ''를 가리키는 스레드를 사용한다. 마지막 방문 노드인 'G'의 오른쪽 포인터는 null이며, 이는 순회의 종료를 의미한다.

 

자바 코드

class TfNode {
    TfNode left;
    char data;
    TfNode right;
    boolean threadFlag;

    public TfNode(char data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.threadFlag = false;
    }
}

public class ThreadedTree {

    public TfNode inorderStart(TfNode ptr) {
        if (ptr == null) return null;
        while (ptr.left != null) ptr = ptr.left;
        return ptr;
    }

    public void inorder(TfNode root) {
        TfNode ptr = inorderStart(root);
        while (ptr != null) {
            System.out.print(ptr.data + " ");
            if (ptr.threadFlag) ptr = ptr.right;
            else ptr = inorderStart(ptr.right);
        }
    }

    public static void main(String[] args) {
        // 트리 구성 및 순회 코드...
    }
}

2. 스레드 트리 삽입 및 삭제

스레드 트리에 노드를 삽입하는 과정은 일반 이진 트리보다 복잡하다. 스레드 트리에서는 노드의 스레드 포인터와 자식 포인터를 적절하게 조정해야 한다. 이 과정은 삽입하려는 노드의 위치와 트리의 현재 상태에 따라 달라진다.

그림 a - 노드 X가 잎인 경우

그림 b - 노드 x가 내부 노드인 경우

    struct tfnode *left;
    ... 생략 
 }

 void insert (tfNode *x, tfNode **ttree) { 
     ttree -> left = null;
    ttree -> right = x -> right;
    ttree -> lthread = x;
    ttree -> rthread = x -> rthread;
    x -> right = ttree;
    x -> rthread = ttree;
 }

• 노드 삽입 과정:
  • 삽입하려는 노드의 왼쪽 포인터는 null로 설정하고, 오른쪽 포인터는 삽입 위치에 있는 노드의 오른쪽 포인터를 가리킨다.
  • 삽입할 노드의 왼쪽 스레드 포인터에는 삽입 위치의 노드 주소를 저장하고, 오른쪽 스레드 포인터는 삽입 위치의 노드 오른쪽 스레드에 저장한다.
  • 삽입 위치의 노드 오른쪽 포인터와 오른쪽 스레드 포인터를 모두 새로운 노드의 주소로 업데이트한다.
• 노드 삭제 과정:
  • 스레드 트리에서의 노드 삭제는 복잡하다. 특히, 삭제할 노드가 내부 노드인 경우 처리가 더욱 까다롭다.
  • 한 가지 방법은 해당 노드의 자식 노드를 모두 삭제하는 것이다. 이 경우, 관련 스레드들도 모두 업데이트해야 한다.
  • 다른 방법으로는, 삭제할 노드의 왼쪽 또는 오른쪽 서브트리의 루트를 삭제한 노드의 위치로 이동시키는 것이다. 이 경우, 해당 서브트리에 대한 추가 처리가 필요하다.
  • 가장 효과적인 방법은 잎 노드가 아닌 노드를 삭제하지 않는 것이다. 이 방법은 트리의 구조를 유지하면서 스레드의 업데이트를 최소화한다.

 

요약

• 정해진 순회 방법에 따른 방문 순서를 유지하는 스레드라는 포인터를 갖는 이진 트리를 스레드 트리라고 한다.
• 오른쪽 스레드는 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리키고, 왼쪽 스레드는 그 노드의 선행 노드를 가리킨다.
• 스레드를 구현할 때 스레드를 저장하는 포인터를 추가하는 방법이 있다.
• 스레드를 구현하는 다른 방법은 이진 트리를 위한 연결 리스트의 노드 구조를 그대로 ㅏ용하면ㄴ서, 잎 노드에 있는 사용하지 않는 포인터를 활용하는 방법이다.
• n 개의 노드를 가진 이진 트리를 연결 리스트로 구현할 때 null 포인터는 항상 2n - (n - 1) = n +1 개가 존재한다.
• 잎 노드에 있는 포인터를 활용할 때는 각 노드에 대해 포인터가 스레드로 사용중인지 아니면 서브트리에 대한 포인터인지 구분하기 위해 하나 혹은 두 개의 플래그 필드를 사용한다.

 

 

---

참고 자료: 자료구조 (강태원, 정광식 공저, KNOU press 출판)