스레드 트리
스레드의 개념
- 스레드 Thread : 특정 순회 방법에 따라 다음에 방문할 노드를 가리키는 포인터.
- 왼쪽 스레드 Left Thread : 순회 순서에서 그 노드의 선행 노드를 가리키는 포인터.
- 오른쪽 스레드 Right Thread : 순회 순서에서 그 노드의 후속 노드를 가리키는 포인터.
스레드 트리의 개념
- 정해진 순회 방법에 따른 방문 순서를 항상 유지하는
스레드라는 포인터를 추가해 트리 순회를 편리하게 한 것 - 이진 트리의 경우 순회시 방문하지 않고 지나쳐 온 노드들을 스택에 저장하고 관리해야 하는 번거로움 발생함
- 그래서 잎 트리가 가지는 Null 을 가리키는 포인터를 활용하여 스레드 트리라는 것을 구현함
- 트리 순회의 효율성을 높이고, 추가적인 메모리 사용을 최소화 하는 목적.
스레드 트리는 순회 시 재귀 호출이나 스택을 사용하지 안혹도 모든 노드를 효율적으로 방문할 수 있도록 노드 간의 선호 관계를 연결한 자료구조이다.
스레드 트리의 구현
| 구분 | 포인터 추가 방식 | 빈 포인터 활용 방식 |
|---|---|---|
| 구현 방법 | 노드 구조체에 왼쪽 및 오른쪽 스레드 포인터 필드를 추가하여,각 노드가 다음에 방문할 노드를 가리키도록 한다. 메모리 사용량이 늘어나므로, 기억장소 부담이 커질 수 있다. |
기존 이진 트리의 노드 구조를 유지하면서 리프 노드의 빈 포인터를 활용해 스레드를 설정한다. 포인터가 스레드인지 실제 자식 노드를 가리키는지 구분을 위한 태그 필드가 필요. |
| 장점 | 스택 없이 트리에 속한 모든 노드 순회 가능 | 추가 기억장소 필요 없음 |
| 단점 | 스레드를 위한 추가 기억 장소 필요 |
스레드 트리의 연산
스레드 트리의 순회
패스
스레드 트리의 노드 삽입
패스
스레드 트리의 노드 삭제
패스