정의
스레드 이진 트리(Threaded Binary Tree)는 이진 트리의 널 포인터(Null Pointer)를 활용하여 순회(Traversal) 효율을 높이기 위해 고안된 자료 구조이다. 일반적인 이진 트리에서 자식이 없는 노드의 왼쪽 또는 오른쪽 포인터는 NULL을 가리키지만, 스레드 이진 트리에서는 이러한 NULL 포인터를 중위 순회 시에 앞서거나 뒤따르는 노드를 가리키도록 수정하여, 스택이나 재귀를 사용하지 않고도 순회를 가능하게 한다.
개요
스레드 이진 트리는 A. J. Perlis와 C. Thornton에 의해 1960년대 초반에 제안된 개념으로, 특히 반복적 중위 순회를 효율적으로 수행하려는 목적으로 개발되었다. 이는 메모리 사용량을 줄이고 속도를 향상시키기 위해 NULL 링크를 활용하는 방법을 제시한다. 스레드 이진 트리는 왼쪽 스레드와 오른쪽 스레드로 나뉘며, 각각 이전 노드와 다음 노드를 가리킨다. 일반적으로 중위 순회 기준으로 스레딩을 수행하며, 이를 중위 스레드 이진 트리라고 한다.
어원/유래
‘스레드(thread)’라는 용어는 여기서 프로그래밍 언어의 스레드(실행 흐름 단위)와는 무관하며, ‘실을 잇는다’는 의미를 가진 일반 명사에서 유래하였다. NULL 링크를 순회 순서에 따라 다른 노드에 ‘잇는다’는 의미에서 ‘스레드’라는 표현이 사용되었다. 이 개념은 1962년 A. J. Perlis와 C. Thornton의 논문에서 처음으로 공식적으로 제안되었으며, 이후 자료 구조 교과서에서 널리 다뤄지게 되었다.
특징
- 순회 시 스택이나 재귀 호출이 필요 없어 메모리 사용이 감소한다.
- NULL 포인터를 재활용하므로 공간 효율성이 높다.
- 중위 순회를 자연스럽게 지원하며, 전위 또는 후위 스레딩도 가능하나 덜 일반적이다.
- 노드 삽입 및 삭제 시 스레드 관리가 복잡할 수 있어 구현 난이도가 높다.
- 각 노드에는 포인터가 자식을 가리키는지, 아니면 스레드(선형 순서상의 이전/다음 노드)를 가리키는지 구분하기 위한 플래그 비트(예: left_thread, right_thread)가 추가로 필요하다.
관련 항목
- 이진 트리 (Binary Tree)
- 중위 순회 (In-order Traversal)
- 포인터 (Pointer)
- 트리 순회 알고리즘
- A. J. Perlis, C. Thornton