스레드 이진 트리(Threaded Binary Tree)란? 개념과 종류 쉽게 이해하기

이번 글에서는 데이터 구조 중 하나인 스레드 이진 트리(Threaded Binary Tree)에 대해 알아보겠습니다.

스레드 이진 트리가 필요한 이유

이진 트리(Binary Tree)의 노드는 최대 두 개의 자식 노드를 가질 수 있습니다. 하지만 어떤 노드는 자식이 하나만 있거나 아예 없는 경우도 있는데, 이럴 때 연결 리스트 방식으로 트리를 표현하면 해당 링크(포인터) 부분은 null로 비어 있게 됩니다.

스레드 이진 트리는 바로 이렇게 낭비되는 빈 링크 공간을 재활용하는 자료구조입니다. 자식 노드가 없어 비어 있는 포인터 영역을 '스레드(thread)'라고 불리는 특수한 참조로 대체하여 활용합니다.

스레드 이진 트리의 종류

스레드 이진 트리는 크게 두 가지 유형으로 나눌 수 있습니다.

• 단일 스레드 이진 트리(Single Threaded Binary Tree)
• 완전 스레드 이진 트리(Fully Threaded Binary Tree)

단일 스레드 이진 트리

단일 스레드 방식은 다시 두 가지 변형으로 나뉩니다.

• 좌측 스레드(Left Threaded): 어떤 노드에 왼쪽 자식이 없다면, 왼쪽 포인터가 해당 노드의 중위 순회 선행자(inorder predecessor)를 가리키도록 합니다.
• 우측 스레드(Right Threaded): 어떤 노드에 오른쪽 자식이 없다면, 오른쪽 포인터가 해당 노드의 중위 순회 후속자(inorder successor)를 가리키도록 합니다.

두 경우 모두 선행자나 후속자가 존재하지 않을 때는 헤더 노드(header node)를 가리키게 됩니다.

완전 스레드 이진 트리

완전 스레드 이진 트리에서 각 노드는 총 5개의 필드를 가집니다. 일반적인 이진 트리 노드의 세 필드(왼쪽 링크, 데이터, 오른쪽 링크)에 더해, 해당 링크가 실제 자식 노드를 가리키는 링크인지 아니면 스레드인지를 나타내는 불리언(Boolean) 플래그 두 개가 추가됩니다.

예시 그림

아래 그림은 좌측 스레드와 우측 스레드 트리의 예시입니다.

다음은 완전 스레드 이진 트리의 예시입니다.

정리

스레드 이진 트리는 기존 이진 트리에서 null로 남겨지던 포인터 공간을 중위 순회 정보 저장에 활용함으로써 메모리를 효율적으로 사용할 수 있게 해줍니다. 또한 스택이나 재귀 호출 없이도 중위 순회를 빠르게 수행할 수 있다는 장점이 있습니다.