1. 스레드 트리의 정의
1.1. 스레드 트리
•
이진 트리의 노드 순회
◦
전위, 중위, 후위 순회
•
이진 트리의 노드를 순회할 때, 방문하지 않고 지나쳐온 노드들은 스택에 저장하여 관리해야하는 번거로움이 발생
•
스레드 트리
◦
스레드 라는 포인터를 추가하여 트리 순회를 편하게 한 것
◦
순회 방법에 따른 방문 순서를 유지하는 포인터
1.2. 세가지 순회에 대한 스레드 트리
•
전위 순회 (PLR)
•
중위순회(LPR)
•
후위순회(LRP)
2. 스레드 트리의 구현 (1)
2.1. 포인터 필드의 추가
•
노드 구조
◦
왼쪽 스레드 포인터
◦
왼쪽 자식 포인터
◦
데이터
◦
오른쪽 자식 포인터
◦
오른쪽 스레드 포인터
•
오른쪽 스레드
◦
정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴
•
왼쪽 스레드
◦
그 노드의 선행 노드를 가리킴
left_thread | *left | info | *right | right_thread |
•
포인터 필드의 추가
struct TNode {
int info;
TNode left;
TNode right;
TNode left_thread;
TNode tight_thread;
}
C
복사
2.2. 추가된 포인터 필드를 이용한 중위 순회 연산
•
firstin
◦
순회한 트리의 처음에 찾아가야할 노드를 가리키는 포인터
◦
LPR에서 L에 해당
•
노드를 가리킬 수 있는 (TNode) 타입의 포인터 p를 생성하고 firstin 을 가리키게 함
•
포인터 p가 가리키는 데이터(info)를 출력하고 p를 p의 오른쪽 스레드 값으로 바꿔(p→right_thread) 중위 순회에 따른 다음 노드를 가리키게 수정
•
이 과정을 p가 null이 될 때까지 반복
void inorder(struct Tnode *firstin) {
struct TNode *p;
p = firstin;
while(p != NULL) {
printf("%d", p->info);
p = p->right_thread;
}
}
C
복사
2.3. 추가된 포인터 필드에 의한 스레드 구현
•
스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회할 수 있음
•
그러나 스레드를 위한 추가 기억장소를 사용한다는 부담이 생김
•
스레드를 이용한 전위 순회
•
스레드를 이용한 중위 순회
•
스레드를 이용한 후위 순회
3. 스레드의 구현방법 (2)
•
노드의 빈 포인터 필드 활용
◦
기존 이진 트리의 노드 구조를 그대로 사용
◦
노드에 있는 사용하지 않는 포인터를 활용하는 방법
•
추가 기억장소를 사용하지 않아도 되는 장점이 있음
3.1. 잎 노드의 빈 포인터 필드 활용
•
이진 트리의 포인터 갯수 (노드의 갯수를 n개라고 가정)
◦
왼쪽 서브트리를 가리키는 포인터 n개 + 오른쪽 서브트리를 가리키는 포인터 n개
⇒ 2개의 포인터
•
노드의 빈 포인터 필드 활용
◦
루트 노드를 제외한 각 노드 개수는 모두 진입차수는 1
◦
루트 노드를 제외한 전체 노드, 즉 누군가로부터 가리켜져야하는 노드의 개수: n-1
◦
null이 아닌 포인터 개수: n-1
▪
사용되는 포인터의 개수를 의미
→ 2n - (n-1) = n+1 개의 null 포인터가 노드에 존재함
•
2n - (n-1) = n+1개의 null 포인터를 스레드로 활용함
3.2. 중위 순회
•
이진 트리의 중위 순회
◦
어떤 노드 x에 대해
▪
오른쪽 포인터가 null이면 이 포인터를 x 노드의 후행노드 (다음순회되는 노드)를 가리키도록 함
▪
왼쪽 포인터가 null이면 x 노드의 바로 직전에 순회된 노드를 가리키게 함
•
태그 필드
◦
포인터가 스레드 vs 서브트리에 대한 포인터인지를 구분하기 위한 필드
◦
삽입/삭제 연산에서 반드시 필요
3.3. 전위 순회
•
각 노드의 왼쪽 포인터 필드를 스레드로 사용하는 제한을 가정
◦
어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면 그대로 둠
◦
null이면 전위 순회로 순회할 때 다음으로 순회되는 노드를 가리키도록 지정
3.4. 중위 순회
•
중위 순회 예시
3.5. 후위 순회
•
자식을 가리키는 포인터와 다음 순회해야할 노드를 가리키는 포인터가 불일치하게 됨
◦
B → + → C
4. 스레드 트리의 연산
4.1. 전위 순회 스레드 트리의 전위 순회 연산
void Preorderthr(struct TFNode *root){
struct TFNode *p;
p = root;
while (p != null) {
printf("%d", p->info);
p = p->left
}
}
C
복사
4.2. 스레드 트리의 노드 삽입 연산 (1)
•
노드 x가 잎 노드인 경우
void insert(struct Tnode *x, struct Tnode **ttree) {
ttree->left = NULL;
ttree->right = x->right; //x가 원래 가리키던 포인터/스레드는 ttree가 가리키게함
ttree->right_thread = x->right_thread;
x->right = ttree; // x는 ttree를 가키리게함
x->right_thread = ttree;
}
C
복사
•
노드 x가 내부 노드인 경우
4.3. 스레드 트리의 삭제 연산
•
스레드 트리의 내부 노드 삭제: 삭제된 노드의 자식 노드를 처리하는 방법이 필요함
1.
노드의 자식 노드를 모드 삭제하는 방법
2.
삭제하려는 노드 x의 왼쪽 서브 트리나 오른쪽 서브 트리의 루트를 x가 있던 위치로 옮기는 방법
3.
잎 노드가 아닌 노드를 삭제하지 못하게 하는 방법