8강. 스레드트리

학습개요

이진 트리를 순회할 때 방문하지 않고 지나쳐온 노드를 저장하는 방법으로 스택을 사용했습니다. 하지만 스택에 저장하고 스택을 관리해야 하는 번거로움이 있었습니다. 이러한 번거로움을 없애기 위한 새로운 방법이 스레드 트리입니다.

정해진 순회 방법에 따른 방문 순서를 유지하는 포인터를 스레드라고 합니다. 그리고 스레드라는 포인터를 갖는 이진 트리를 스레드 트리라고 합니다. 스레드의 종류는 두 가지가 있습니다. 오른쪽 스레드와 왼쪽 스레드입니다. 오른쪽 스레드는 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킵니다. 왼쪽 스레드는 그 노드의 선행 노드를 가리킵니다. 스레드 트리는 2가지 방법으로 구현할 수 있습니다. 한 가지는 스레드를 저장하는 포인터를 추가하는 방법이 있습니다. 즉 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정하는 것입니다.

이 방법은 기억장소에 대한 부담이 있습니다. 다른 방법은 이진 트리를 위한 연결 리스트의 노드 구조를 그대로 사용하면서, 잎 노드에 있는 사용하지 않는 포인터를 활용하는 방법입니다. 이 방법은 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브 트리에 대한 포인터인지를 구분하기 위해 하나 혹은 두 개의 플래그 필드를 사용합니다. 스레드를 사용한 만큼 편리한 점도 있지만, 트리에서 노드의 삽입과 삭제 연산은 복잡한 편입니다. 코드를 한 줄 한 줄 따라가며 정확하게 이해하는 것이 도움이 될 것입니다.

학습목표

1. 스레드 트리의 개념을 이해할 수 있다.
2. 스레드 트리의 구현 방법을 이해할 수 있다.
3. 스레드 트리의 순회 연산과 삽입, 삭제 연산을 이해할 수 있다.

연습문제

1. 이진 트리의 노드 개수를 n이라 하면, 잎 노드의 사용하지 않는 포인터 필드의 개수는 모두 몇 개인가?
   1. n-1
   2. n
   3. n+1
   4. n+2
      –
2. 스레드 트리에 대한 설명으로 옳은 것은 무엇인가?
   1. 중위순회에서 사용 가능한 스레드는 후위순회나 전위순회에서는 사용할 수 없다.
   2. 루트노드의 빈 포인터 필드를 활용한다.
   3. 잎 노드의 빈 포인터 필드를 활용한다.
   4. 경우에 따라서 스택을 활용하여 순회 연산을 수행한다.
      –
3. 다음 그림의 스레드는 어떤 순회 방식은 무엇인가?
   
   1. 전위 순회
   2. 중위 순회
   3. 후위 순회
   4. 중복 순회

정리하기

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