스레드 이진트리

일반적인 이진 트리에서, 많은 노드들이 자식 노드를 하나만 가지거나 전혀 가지지 않는 경우가 많습니다. 

이진 트리의 많은 부분에 빈 공간이 생기며, 트리를 순회 (recursion)할 때 이 빈 공간을 효율적으로 사용하지 못하는 문제가 있습니다.

 

스택 없이 이진트리의 연산을 구현하는데에 2가지 방법이 있습니다.

1. node 객체에 부모를 가리키는 레퍼런스 필드를 추가로 선언하고 순회

2. 노드의 null 레퍼런스 사용 = 스레드 이진 트리

스레드 이진 트리(Threaded Binary Tree)는 이러한 문제를 해결하기 위해 고안된 자료구조입니다. 스레드 이진 트리는 트리의 노드들이 자식 노드가 없는 경우, 그 노드의 포인터를 다른 유용한 노드에 연결하여 메모리 공간을 효율적으로 사용합니다. 이 연결을 '스레드'라고 합니다.

 

스레드 이진트리는 대부분 중위 순회에 기반하여 구현됩니다.

이 스레드는 주로 두 가지 방식으로 구현됩니다:

단일 스레드 이진 트리 (Single Threaded)

각 노드가 자식이 없는 경우, 그 노드의 오른쪽 포인터를 이용하여 중위 순회에서 다음에 방문할 노드를 가리킵니다.

 

이중 스레드 이진 트리 (Double Threaded)

각 노드가 자식이 없는 경우, 그 노드의 왼쪽 포인터는 중위 순회의 이전 노드를, 오른쪽 포인터는 다음 노드를 가리킬 수 있도록 설정됩니다.
스레드 이진 트리의 가장 큰 장점은 트리 순회 시 필요한 스택이나 재귀 호출 없이 빠르고 간단하게 순회가 가능하다는 점입니다. 이는 순회 과정에서 포인터를 따라가기만 하면 되기 때문에, 연산 처리 속도가 향상됩니다.

 

이런 특성 덕분에 스레드 이진 트리는 메모리 사용을 최적화하고, 트리 순회를 더 효율적으로 할 수 있게 도와줍니다. 이 자료구조를 이해하고 활용하면, 복잡한 트리 구조를 보다 쉽게 관리하고 활용할 수 있습니다.

다만 구현이 비교적 복잡하여 성능이 저하됩니다.