스레드 이진 트리(Thread Binary Tree) 개념 (1)

스레드 이진 트리란?

일반적으로 해석하는 이진 트리는 내부 스택 혹은 외부 스택을 통해서 순회를 하였다.

하지만 스레드 이진 트리는 스택을 이용하지 않고 포인터를 이용하여 순회의 시간을 단축시키는 방식이다.

(함수 호출보다 포인팅을 통한 코딩이 속도면에서 빠르다.)

이때 내부 스택은 흔히 이용하는 재귀 함수를 이용한 시스템 스택을 의미하고

외부 스택은 임의로 만든 stack class(struct)같은 것을 의미한다.

여기서 알아가는 스레드는 흔히 OS에 나타나는 프로세스와 관련된 멀티프로그래밍에 이용되는 스레드와는 다른 의미이다.

그리고 스레드 이진 트리는 중위 순회를 기본으로 한다.

일반적 이진트리는 위와 같이 생겼고, 스레드 이진 트리는 아래와 같이 생겼다.

스레드 이진 트리의 더욱 자세한 그림은 아래와 같다.

스레드 이진 트리의 노드는 다음과 같이 구성된다.

class node{
 
bool leftThread;
node *leftChild;
int data;
node *rightChild;
bool rightThread;
};
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>

이 노드를 그림과 함께 살펴보면 

leftThread :: 왼쪽에 스레드가 형성되있는지 확인해주는 bool 타입이다.

leftChild :: 노드의 왼쪽 부분이 어느 노드를 가리키는지 알려준다.

int data :: 노드에 데이터를 입력받는 변수이다.(여러 타입 지정 가능)

rightChild :: 노드의 오른쪽 부분이 어느 노드를 가리키는지 알려준다.

rightThread :: 오른쪽에 스레드가 형성되있는지 확인해주는 bool 타입이다.

그림에서 보이는 점선들이 모두 thread이다.

즉, 점선으로 나타난 부분들은 leftThread 혹은 rightThread가 T로 되어있고

실선 즉, 자식노드를 연결하고 있는 것들은 leftThread 혹은 rightThread가 F로 되어있다.

그렇다면 점선 즉, 스레드는 어떻게 나타내는 것인가?

* 스레드는 말단 노드(Leaf Node)에만 적용한다. *

중위 선행자(inorder predecessor) :: 중위 순회를 할 때 현재 노드를 방문하기 전이었던 노드를 의미한다.

(방문이라 함은 출력을 의미한다고 보아도 무방하다.)

중위 후속자(inorder successor) :: 중위 순회를 할 때 현재 노드 다음 순회 할 노드를 의미한다.

이 두가지를 이용하여 나타낸다.

위의 그림을 참조해보자.

F를 본다면, F의 중위 선행자는 A이다. 왜 A냐?

이 트리의 중위 순회를 보면 H D I B E A F C G이다.

즉, F앞에 방문하였던 노드는 A이기에 중위 선행자라 한다.

그렇다면 F의 중위 후행자는? C이다.

이렇게 말단 노드에 중위 선행자와 중위 후행자에 점선으로 스레드를 이어주면 스레드 이진 트리가 된다.

이때 H의 왼쪽과 G의 오른쪽이 의문이 갈 것이다.

중위 순회에서도 H의 중위 선행자, G의 중위 후행자는 없다.

이런것을 대비하기위해 스레드 이진 트리에서는  root라는 dummy node를 만들어 H와 G의 포인팅을 도와준다.

이 포인터를 만든 이유는 노드의 위치를 잃지 않고 저장하기 위함과 스레드 이진 트리 정의를 명확히 하기 위해서이다.