Tree(2)

스레드 트리

원형 연결 리스트처럼, 메모리의 낭비를 줄이고자 고안됨.

이진트리의 노드를 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야하는 번거로움이 발생, '스레드'라는 포인터를 추가하여 트리 순회를 편리하게 한 것

(* 트리 순회를 할 때 스택을 사용하여 일일이 방문하지 않아도 된다)

• 스레드 : 순회방법에 따른 방문순서를 유지하는 포인터

스레드 트리의 구현

• 포인터 필드의 추가: 스레드를 저장하는 포인터를 추가
  • 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의(*포인터가 두 배 가량 늘어남)
• 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 후속 노드를 가르킴
• 왼쪽 스레드: 그 노드의 선행노드를 가리킴

struct TNode {
  int info;
  TNode left;
  TNode right;
  TNode right_thread;
  TNode left_thread;
}

예제 ) 추가된 포인터 필드를 이용한 중위 순회 연산

void inorder(struct TNode *frstin) {
  struct TNode *p;
  p = firstin;
  while(p != NULL) {
    printf("%d", p->info);
    p = p->right_thread
  }
}

1. 순회할 트리의 시작 노드를 가리키는 포인터 firstin을 매개변수로 하는 함수의 이름을 inorder()로 지정
2. 노드를 가리킬 수 있는 (TNode)타입의 포인터 p를 생성 후 루트노드를 가리키도록 한다.

👉 추가된 포인터 필드에 의한 스레드 구현은 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회할 수 있다는 장점이 있으나, 스레드를 위해 추가 기억장소를 사용한다는 부담이 생긴다.

• 스레드의 구현방법(1)

  스레드를 이용한 전위 순회

  

  스레드를 이용한 중위 순회

  

• 스레드의 구현방법(2)

  • 노드의 빈 포인터 필드를 활용: 기존 이진트리의 노드 구조를 그대로 사용하면서, 노드에 있는 미사용 포인터를 활용

    • 추가 기억장소를 사용하지 않아도 되는 장점

    -루트 노드를 제외한 각 노드 개수는 모두 진입 차수는 ‘1’이 되므로,

    -루트 노드를 제외한 전체 노드, 즉 누군가로부터 가리켜져야 할 노드의 개수는 n - 1

    -null이 아닌 포인터 개수는 n - 1

    -2n - (n-1) = n + 1개의 null포인터가 노드에 존재

  • 잎 노드의 빈 포인터 필드 활용

    • 노드 개수를 n개라고 가정하면, 왼쪽 서브트리를 가르키는 포인터 n개 + 오른쪽 서브트리를 가리키는 n개 = 2n개의 포인터

  • 이진트리의 중위 순회: 어떤 노드 x에 대해 오른쪽 포인터가 null이면 이 포인터를 x노드의 후행노드를 가리키도록 하고, 왼쪽 포인터가 null이면 X노드의 바로 직전에 순회된 노드를 가리키게 한다.

  • 스레드를 이용한 전위 순회 - 각 노드의 왼쪽 포인터 필드를 스레드로 사용하는 제한을 가정.

    • 어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면 그대로 두고, null일 경우 전위 순회로 순회할 때 다음으로 순회되는 노드를 가리키도록 지정

    

    • 각 노드에 대해 포인터가 스레드로 사용 중인지 서브트리에 대한 포인터인지 구분하기 위한 태그필드 필요(삽입/삭제 연산시 필수)