스레드 이진 트리란?(What is treaded binary tree?)
이진 트리를 연결 리스트로 표현했을 때 각 노드당 2개의 링크필드를 가지므로 n개의 노드에 대해 2n개의 링크필드를 가진다. 이때 마지막 노드가 n+1개의 링크필드를 가지는데 이 링크필드 모두 NULL을 가리켜 메모리 낭비가 심하다. 이를 해결하기 위해 펄리스(Perlis)와 손톤(Thornton)이 NULL링크들이 특정 노드를 가리키도록 하는 방법을 만든다. 여기서 조정된 NULL링크를 스레드(thread)라고 한다. 스레드 이진 트리는 기존 이진 트리의 구조에 2개의 쓰레드를 추가한다.
스레드 이진 트리에서 왼쪽 스레드와 오른쪽 스레드는 순회 방법에 따라 각각 특정 노드의 오른쪽 링크와 왼쪽 링크가 직전 방문 노드와 다음 방문할 노드를 가리키는지 판별한다.. 아래 그림은 중위 순회중 E를 방문한 상태를 나타낸다. 노드 E를 방문하기전 노드 B를 방문하는데 이를 노드 E에 대한 중위 선행자(inorder predecessor)라 한다. 노드 A는 노드 E에 대한 중위 후속자(inorder successor)라고 한다.
아래는 스레드 이진 트리가 중위 순회할 때 어떻게 구성되는지를 나타내는 그림이다.
그림에서 보면 이진 트리일 때 NULL을 가리키는 링크가 모두 다른 노드를 가리키도록 되어있다. 이진 트리에서 마지막 노드의 두 링크가 그림과 같이 연결이 되면 이 링크가 자식을 가리키는 링크인지 선행자, 후속자를 가리키는 링크인지 알 수 없다. 이때 스레드를 통해 값이 참이면 선행자, 후속자를 가리키고 거짓이면 자식을 가리키는 링크로 구분한다. 이런 방식으로 연결을 하다보면 한 가지 문제가 생긴다. 바로 처음 노드의 선행자와 마지막 노드의 후속자를 가리킬 수 없다는 문제이다. 이 문제는 헤드 노드를 추가하여 이를 가리키도록 하여 문제를 해결한다. 헤드 노드의 왼쪽 자식은 A노드를 가리키고 오른쪽 자식은 자기 자신을 가리킨다.
'자료구조' 카테고리의 다른 글
| 이진 탐색 트리(Binary search tree) (0) | 2022.03.29 |
|---|---|
| 일반 트리에서 이진 트리로 변환 (0) | 2022.03.29 |
| 트리 순회(Tree Traversal) (0) | 2022.03.01 |
| 트리(Tree) (0) | 2022.03.01 |
| 이중 연결 리스트(Doubly Linked List) (0) | 2022.02.25 |