728x90
반응형
01. 스레드 트리의 정의
이진 트리의 노드를 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야 하는 번거로움이 발생함
*이진 트리의 노드 순회: 전위 순회, 중위 순회, 후위 순회
=> 이러한 방법을 사용하지 않고 놀고 있는 링크들을 사용하여 순회를 빠르게 하는 스레드 트리 탄생
✅ 스레드 트리
- '스레드'라는 포인터를 추가하여 트리 순회를 편리하게 한 것
- 스레드: 순회 방법에 따른 방문 순서를 유지하는 포인터
🔸세 가지 순회에 대한 스레드 트리
- 전위 순회(PLR)
- 중위 순회(LPR)
- 후위 순회(LRP)
02. 스레드 트리의 구현
🔸스레드의 구현 방법 - 포인터 필드의 추가
- 스레드를 저장하는 포인터를 추가하는 것
- 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의함
- 왼쪽 스레드: 해당 노드의 선행 노드를 가리킴
- 오른쪽 스레드: 정해진 순회 순서에 따른 해당 노드의 후행노드를 가리킴
- 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회할 수 있지만 스레드를 위해 추가 기억장소를 사용한다는 부담이 생김
▪️ 포인터 필드의 추가
▪️ 추가된 포인터 필드를 이용한 중위 순회 연산과정
① 순회할 트리에서 가장 먼저 접근해야하는 노드를 가리키는 포인터 firstin을 매개변수로 하는 함수의 이름을 inorder()로 지정
② 노드를 가리킬 수 있는 TNode 타입의 포인터 p를 생성하고 firstin에 담긴 노드를 가리키도록 함
③ 포인터 p가 가리키는 데이터(info)를 출력하고 p를 p의 오른쪽 스레드 값으로 바꾸어(p→right_thread) 중위 순회에 따른 다음 노드를 가리키도록 수정함
④ 이 과정을 p가 null이 될 때까지 반복함
스레드를 이용한 전위 순회
- 자기 자식을 가리키는 것과 스레드가 동일한 경우가 많기 때문에 전위 순회를 할 거면 굳이 스레드를 추가해서 사용할 필요가 없음을 깨달음
🔸스레드의 구현 방법 - 노드의 빈 포인터 필드를 활용
- 기존 이진 트리의 노드 구조를 그대로 사용하면서 노드에 있는 사용하지 않는 포인터를 활용하는 방법
- 추가 기억장소를 사용하지 않아도 되는 장점이 있음!
- 잎 노드의 빈 포인터 필드의 활용
- 이진 트리의 포인터 갯수(노드의 개수를 n개라 가정): 왼쪽 서브트리를 가리키는 포인터 n개+오른쪽 서브트리를 가리키는 n개 = 2n개의 포인터
- 루트 노드를 제외한 전체 노드의 진입 차수 1 = 루트 노드를 제외한 전체 노드 즉, 누군가로부터 가리켜져야 할 노드의 개수: n-1
- null이 아닌 포인터 개수: n-1
- null 포인터 개수: 2n - (n-1) = n+1 그래서 이 null 포인터를 스레드로 활용
- 각 노드에 대해 포인터가 스레드로 사용 중인지, 서브트리에 대한 포인터인지를 구분하기 위해 태그 필드가 필요함(삽입/삭제 연산에서 반드시 필요)
▪️스레드를 이용한 전위 순회
- 전위 순회: 각 노드의 왼쪽 포인터 필드를 스레드로 사용하는 제한을 가정함
- 어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면 그대로 두고, null이면 전위 순회로 순회할 대 다음으로 순회되는 노드를 가리키도록 지정
▪️ 스레드를 이용한 중위 순회
- 어떤 노드 X에 대해 오른쪽 포인터가 null이면 이 포인터를 X 노드의 후행 노드를 가리키도록 하고, 왼쪽 포인터가 null이면 X 노드의 선행 노드를 가리키게 함
▪️ 스레드를 이용한 후위 순회
- 자식 노드를 가리키는 것과 스레드가 불일치할 경우 프로그램적인 처리가 추가 필요
728x90
반응형
'KNOU > 자료구조' 카테고리의 다른 글
| [자료구조] 10. 선택트리, 숲, 이진 트리 개수 (1) | 2022.12.05 |
|---|---|
| [자료구조] 9. 힢 (0) | 2022.12.04 |
| [자료구조] 7. 트리 (1) | 2022.12.04 |
| [자료구조] 6. 연결 리스트의 응용 (0) | 2022.11.30 |
| [자료구조] 5. 연결리스트 (0) | 2022.11.28 |