[자료구조] 8강 - 스레드트리

✅ 1. 스레드 트리 개념

(1) 스레드 트리란?

[ 기존 이진 트리의 단점 ]

• 이진 트리: 각 노드가 데이터를 저장하고 최대 두 개의 자식 노드를 갖는 자료구조임.
• ( 또한, 일반 이진 트리는 재귀 또는 스택을 이용해 구현을 할 수 있음. )
• 기존 이진 트리에서 잎 노드의 left/right 포인터가 항상 NULL 이기 때문에 순회(전위, 중위, 후위 방식)를 할 때, 이전의 노드로 돌아가야 하는 경우가 있는데 이때, 재귀 호출마다 함수 호출 스택이 쌓이는 문제점이 발생함.
• 스택 오버헤드: 트리가 깊거나 노드 수가 많아지면 스택 오버플로우가 발생 할 가능성이 높아짐.
• 실행 속도: 함수 호출/복귀 비용이 반복되어 실행 속도가 느려질 수 있음.

[ 스레드 트리 ]

• 스레드 트리: 위와 같이 이진 트리의 단점을 보완하고자, 기존 이진 트리의 NULL 포인터를 활용하여 순회 경로를 연결함으로써, 스택이나 재귀와 같이 되돌아가지 않고 연결 된 형태로 다음으로 넘어갈 수 있게 만들어 놓은 자료구조임.
• 즉, 스레드 트리의 핵심 목적은 순회 시 스택이나 재귀 호출을 사용하지 않고 다음 노드를 찾아갈 수 있도록 하는 것임.

(2) 스레드 트리 구현 예시 - 포인터 필드 추가 방식(덜 일반적인 방식임)

• 스레드 트리는 이진 트리 노드에 필드를 left_thread, right_thread 두 개를 추가함으로써, 다음 / 이전 순회 노드를 직접 카리키게 하는 방식이다.

• left_thread: 왼쪽 자식이 없을 때 중위 순회에서 이전 노드를 가리키는 용도
• right_thread: 오른쪽 자식이 없을 때 다음 노드를 가리키는 용도
• 이 방식은 기존 이진 트리에 잎 노드의 left, right 필드가 NULL 인 경우에 left_thread, right_thread 를 참조하게 함으로써, 기존의 스택에 쌓아서 돌아가는 재귀 구조를 단순히 다음으로 넘어가는 순환 구조로 바꿀 수 있음.
• 이 구조는 스레드 트리가 NUL 포인터 공간 재활용이라는 본래의 목적을 달성하지 못해서 덜 일반적인 방식이됨.
• 어떻게 보면 잘못된 방식으로 볼 수 있으며, 포인터 필드의 추가로 메모리 효율성이 크게 떨어지게 됨.

(3) 스레드 트리 사용 이유

[ 스레드 트리 사용 이유 예시 ]

• 위와 같이 기존의 이진트리는 중위 순회의 경우 왼쪽 서브트리를 다 돌고 나면 부모로 되돌아와야하는 구조임.
• 하지만, 트리 구조에서는 부모로 돌아가는 포인터가 없고 내려가는 포인터만 존재함.
• 그래서 기존 이진 트리는 스택을 통해 재귀 호출을 하는 방식을 이용해서 되돌아왔었음.
• 즉, “방문하지 않고 지나쳐 온 노드를 기억하기 위해 스택에 저장해야 하는 번거로움이 발생한다.”는 단점이 있음.

[ 중위 순회 시 구현 방법 예시 ]

• 왼쪽 자식이 없는 경우: 그 왼쪽 링크를 중위 순회 시, 자기보다 이전 노드(predecessor) 로 연결
• 오른쪽 자식이 없는 경우: 그 오른쪽 링크를 중위 순회 시, 자기보다 다음 노드(successor) 로 연결
• 이렇게 하면 중위 순회할 때 스택이나 재귀 없이도 바로 다음 노드를 찾을 수 있음.

(4) 스레드 트리 순회

• 스레드: 스레드 트리에서 스레드의 의미는 순회 방법에 따른 방문순서를 유지하는 포인터이다.
• 순회는 기존의 이진 트리와 동일하게 전위, 중위, 후위 순회를 대표적으로 사용함.
• 기존 이진 트리: 해당 순회에서 스택을 사용한 재귀호출
• 스레드 트리: 스레드 필드를 활용해 순회 방법에 따라 방문 순서에 맞게 다음으로 넘어가는 방식임.

---

✅ 2. 스레드 트리 구현 - 포인터 필드의 추가 방식

(1) 포인터 필드의 추가 방식이란?

• 포인터 필드의 추가: 스레드를 저장하는 포인터를 추가하는 것을 의미함.
• 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의함.

• 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴
• 왼쪽 스레드: 그 노드의 선행 노드를 가리킴.

(2) 포인터 필드의 추가 - 객체

• 특정 노드 객체의 정의로 볼 수 있으며, 스레드 트리는 lthread, rthread 두 개의 필드가 증가한 모습으로 정의 됨.

(3) 포인터 필드의 추가 - 중위 순회 연산과정 예제

• 위의 정의된 포인터 필드를 활용한 중위 순회 연산 과정을 나타낸 코드이다.
• startNode: inoder() 함수의 매개변수의 값으로는 순회할 트리의 시작 노드를 가리키는 포인터이다.
• tfNode *ptr: 노드를 가리킬 수 있는 타입인 tfNode 타입의 포인터 ptr 생성
• ptr = startNode: 시작 노드를 가리키도록 함.
• while(ptr != NULL): 반복문을 통해 ptr 이 NULL 이 아닌 경우에 지속적인 반복을 요구함.
• ptr = ptr -> rthread: ptr 에는 startNode 가 처음 들어가 있는 경우고, 이후에 반복적으로 해당 노드의 rthread 의 필드값인 rthread 의 주소값을 참조하게 된다. 이후, ptr 에 넣어주게 됨.
• 결과적으로 원형 연결 리스트처럼 잎 노드 필드에 주소값이 NULL 이 아닌 주소값을 넣게 되어, 참조를 하게되는 방식임.

• 핵심: 전위, 중위, 후위 순회 순서에 따라, 시작하는 startNode 가 달라 질 수 있음.
• ( 전위면 startNode 가 root 인 C가 될 것임. 중위 = startNode L , 후위 = startNode L )
• 일반적인 트리에서는 root 를 이용해 트리를 가리키는게 기본이지만, 스레드 트리에서는 순회순서에 따라서 시작점이 달라짐

(4) 포인터 필드의 추가 - 스레드 트리가 맞나?

• 이 구조는 스레드 트리가 NULL 포인터 공간 재활용이라는 본래의 목적을 달성하지 못해서 덜 일반적인 방식이됨.
• 어떻게 보면 잘못된 방식으로 볼 수 있으며, 포인터 필드의 추가로 메모리 효율성이 크게 떨어지게 됨.
• 즉, NULL 포인터 공간을 그대로 두고 필드를 추가한 것이므로, 스레드 트리에 부적합한 모습을 보임.

(5) 포인터 필드의 추가 - 핵심

• 트리는 기본적으로 비선형 구조라서, 부모에서 자식으로는 쉽게 내려갈 수 있지만 다시 올라가는건 불가능함.
• 그렇기 때문에 내려 갈 때 돌아올 위치를 기억해둘 필요가 있음 이유는, 그래야 순회를 돌 수 있으니까
• 그래서 트리에서 기본적으로 순회를 할 때 사용하는 방법이 재귀적 호출 방식이고, 이건 Stack 으로 볼 수 있음.
• 하지만, 이러한 재귀적 호출 또는 스택을 사용하는 방식은 함수가 호출될 때마다 스택 프레임(매개변수, 복귀 주소 등)을 저장해야 하고, 노드 수가 많으면 메모리 낭비 + 호출 비용이 증가 할 수 있다는 단점이 있음.
• 특히 트리의 깊이가 깊을수록 오버헤드가 발생할 확률이 매우 높아짐 결과적으로 스택 오버플로우가 발생할 수 있음.
• 이러한 다양한 문제점을 해결하기위해 스레드트리가 나오게 된것임.
• 이 스레드 트리는, 스택 또는 재귀 없이 트리를 순회할 수 있도록 만든 구조임.
• 즉, 스레드 트리는 기존의 트리구조에서 필드를 추가하여 추가적으로 노드의 주소를 저장하게 되는 것임.

• 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴
• 왼쪽 스레드: 그 노드의 선행 노드를 가리킴.
• 이렇게 기존 노드 구조에 스레드용 포인터 필드 2개를 만들어서 넣게 됨.
• 즉, 스레드 트리는 원형 연결 리스트가 단순 연결 리스트의 구조를 활용해서 개선한 것과 동일하게 트리 구조를 개선한 느낌임.
• 결과적으로 left 나 right 는 이진 트리의 구조를 유지하기 위해서 필요한 것이고, left_thread 와 right_thread 는 순회 순서인 전위, 중위, 후위에 따라서 주소값을 부여하면 되는 것임.
• 즉, 처음에는 left, right 를 통해서 내려가게 되는데, 만약 left 나 right 가 null 인 경우 자식 노드가 없는 경우로 보고, left_thread 와 right_thread 를 통해서 다음 노드로 가게 되는 것임.
• left 와 right 의 존재는 노드간의 관계를 명확하게 해주고 삽입과 삭제를 하는 구조적으로 다룰 때에 필요함.
• 쉽게말해, left, right는 자식 노드의 주소를 가지고 있으므로 해당 구조가 트리라는 것을 알 수 있게 해주는 필드임.
• 포인터 필드 추가 방식은 구현이 쉽지만 메모리 사용량이 필드수 만큼 늘어나는 단점이있음.

---

✅ 3. 스레드 트리 구현 - 빈 포인터 활용 방식

• 스레드 트리의 구현 방식으로 빈 포인터의 활용은 대표적으로 가장 많이 쓰이는 진정한 스레드 트리로 볼 수 있음.

(1) 빈 포인터 활용 방식 이란?

• 기존 이진 트리의 노드 구조를 그대로 사용하면서, 노드에 있는 사용하지 않는 포인터(빈 포인터)를 활용하는 방법임.
• 추가적인 메모리 공간을 사용하지 않아도 되는 장점이 있지만, 소스코드가 많이 복잡해진다는 단점이 있음.
• 즉, 스레드 필드를 따로 추가하지 않으므로써, 추가적인 메모리 공간을 사용하지 않는다는 의미임.
• **특정 노드 X에 대해 오른쪽 포인터가 NULL이면 이 포인터를 노드 X의 후행 노드를 가리키도록 하는 방식임.**

• 위와 같이 잎 노드의 빈 포인터 필드를 활용하는 방식이다.
• 또한, 노드 총 개수: n || null 포인터 총 개수 : n + 1 이다.
• 즉, 노는 포인터(빈 포인터)가 실제 노드보다 훨씬 많음.
• 결과적으로 null pointer 는 스레드로 불리며, 이것을 활용하고자 하는 것이 스레드 트리임.
• 또한, 해당 스레드 트리 구조에서는 newNode 가 추가가 될 때, 잎 노드의 경우 right 포인터에 후행노드를 가리키게 주소값을 참조하는 로직이 포함이 되어야 함. 이렇게 되면, 순회는 간단하지만 삽입, 수정, 삭제 로직이 복잡해질 수 있음.

(2) 빈 포인터 활용 방식 - 구분을 위한 태그 필드 추가

• 해당 스레드 트리의 빈 포인터가 스레드로 사용 중인지 아니면 서브트리에 대한 자식을 가리키는 포인터인지 구분을 해줘야함.
• 즉, 스레드 사용여부 태그 필드(플래그)가 필요함. ( 삽입/삭제 연산에서 반드시 필요함 )
• 이유는, 삽입 시 해당 필드가 자식인지 스레드인지 모르면 노드 밑이 아닌 후행 노드로가서 넣을 수도 있기 때문임.

(3) 빈 포인터의 활용 방식 - 구현 방법

[ 사용 할 순회 방식: 전위 순회 방식 ]
[ 조건: 각 노드 오른쪽 포인터 필드를 스레드로 사용 ]
( 즉, right = 후행 노드 or left = 후행 노드 둘 중 하나로 구현 )

• 이것과 같이 다양한 순회 방식과 다양한 조건으로 구현이 가능함.
• 즉, 오른쪽 포인터가 후행 노드를 가리키겠다는 의미임.
• 점선: 후행 노드를 가리키는 선 ( 노드의 스레드가 후행 노드를 가리키면 점선 )
• 실선: 실제 자식을 가리키는 선 ( 노드의 스레드가 실제 자식을 가리키면 실선 )
• **해당 선은 밑의 이미지 예시를 위해서 정해둔 임의의 규정임.**

[ 스레드 활용 순회 방법 ]

• 위와 같이 스레드를 활용해서 순회를 돌 수 있으며, 플래그 필드를 다 추가를 해줘야함.

---

✅ 4. 스레드 트리 순회, 삽입, 삭제

(1) 스레드 트리 - 객체

• 스레트 트리 노드의 flag 를 추가한 객체로 볼 수 있으며, 이것은 하나의 노드를 의미한다.
• threadFlag = true: 일 경우 right 주소값은 후행 노드를 가리키는 주소값으로 본다.
• threadFlag = false: 일 경우 right 주소값은 자식 노드를 가리키는 주소값으로 본다.
• 위와 같은 조건을 알고리즘에서 구현하기 위해서 flag 필드를 따로 추가한 방식으로 볼 수 있음.
• 핵심은 위와 같은 객체는 중위 순회 뿐만 아니라 모든 순회에 필요한 객체임. 단지 예시를 든 것 일뿐임.

(2) 스레드 트리 - 중위 순회 연산

• (1) inorder(tfNode* root): root 노드의 주소값을 매개변수로 전달
• (2) tfNode* ptr = inorderStart(root): inorderStart() 함수 호출 매개변수로 root 주소 전달
• (3) inorderStart(): 중위 순회의 첫 번째 Start Node를 찾아주는 함수이다.
• (4) if(ptr == NULL): ptr 즉, 넘긴 root 의 주소값이 NULL 인지 보고 아닐 경우 이후 로직 수행
• (5) while(ptr -> left != NULL): 반복문을 통해서 ptr 객체의 left 필드가 가리키는 값이 NULL 인지 파악
• 그후, left 가 만약 NULL 인 경우 반복문을 나와서 return ptr; NULL 이 아닌 경우 계속 반복
• 즉, right 를 후행 노드를 가리키는 스레드로 사용 했으므로, left 의 마지막 부분은 NULL이 들어갈 수 있어서 가능함.
• (6) ptr = ptr -> left: left 필드가 null 이 아닌 경우 left 을 반복적으로 참조하게 됨.
• (7) inorderStart()는 최종적으로 left를 참조하다 보면, 마지막 NULL 인 부분으로 중위 순회의 시작점으로 갈 수 있음.
• (8) tfNode* ptr = inorderStart(root): ptr 에는 중위 순회 첫 번째 노드의 주소값이 들어오게 됨.
• (9) while(ptr != NULL): ptr 첫 번째 노드의 주소부터 NULL 여부를 조건으로 중위 순회 반복문을 돌림.
• (10) if(ptr -> threadFlag): ptr 의 threadFlag 가 true 인 경우 ptr = ptr -> right; ptr의 right 주소값을 참조해서 다시 ptr에 넣어주게 됨. 즉, flag 가 true 인 경우 후행 노드를 가리키게 만드는 작업임.
• (11) ptr = inorderStart(ptr -> right): 만약 flag 가 false 인 경우 자식 노드를 가리키는 노드이므로, inorderStart() 함수를 호출하면서 현재 ptr 의 right 필드 주소값을 전달하게 됨. 그러면, left 를 순회 하면서 NULL을 만날 때(잎 노드) 까지 또 자식 노드를 순회하게 됨.

(3) 스레드 트리 - 삽입 연산

(4) 스레드 트리 - 삭제 연산