스레드 이진 트리

3. 필요성 (Motivation)

이진 트리, 특히 이진 탐색 트리는 데이터를 특정 순서(주로 키 기준)로 저장하는 데 유용하다. 이런 트리에서 중요한 연산 중 하나는 저장된 항목들을 키 순서대로 모두 방문하는 순회(traversal)이다.

이진 탐색 트리의 각 노드를 방문하는 간단한 방법은 재귀를 이용한 순회 알고리즘이다. 예를 들어, 중위 순회(in-order traversal)는 일반적으로 왼쪽 서브트리를 먼저 순회하고, 현재 노드를 방문한 뒤, 오른쪽 서브트리를 순회하는 방식으로 재귀적으로 구현된다.

하지만 이 재귀적 방식에는 몇 가지 고려해야 할 점이 있다.

• 스택 공간 사용: 재귀 호출은 프로그램 실행 스택에 정보를 저장해야 하므로, 트리의 높이에 비례하는 메모리 공간을 사용한다. 트리가 비교적 균형 잡혀 있다면 ''O''(log ''n'')의 공간이 필요하지만 (여기서 ''n''은 노드의 개수), 트리가 한쪽으로 치우친 사슬 형태가 되는 최악의 경우에는 트리의 높이가 ''n''이 되어 ''O''(''n'')의 공간이 필요하게 된다. 노드 수가 매우 많을 경우 이는 상당한 메모리 부담이 될 수 있다.
• 부모 노드 접근의 어려움: 일반적인 이진 트리 구조에서 각 노드는 자식 노드에 대한 정보만 가지고 있을 뿐, 부모 노드를 직접 가리키는 정보는 없다. 따라서 특정 노드에서 부모 노드로 거슬러 올라가기가 번거로우며, 대부분의 순회 알고리즘은 루트에서 시작해야 한다.

4. 부모 포인터와의 관계 (Relation to parent pointers)

어떤 노드 k가 오른쪽 자식 노드 m을 가지고 있다면, m의 왼쪽 포인터는 왼쪽 자식을 가리키거나 혹은 스레드를 통해 다시 부모 노드인 k를 가리킬 수 있다. 마찬가지로, 노드 k가 왼쪽 자식 노드 n을 가지고 있다면, n의 오른쪽 포인터는 오른쪽 자식을 가리키거나 스레드를 통해 다시 k를 가리킬 수 있다. 이러한 구조는 마치 자식 노드가 부모 노드를 가리키는 것과 유사한 방식으로 부모 노드에 대한 정보를 유지하는 방법이라고 볼 수 있다.

5. 종류 (Types)

스레드 이진 트리는 일반적으로 null 값을 가질 수 있는 포인터를 활용하여 특정 순서로 노드를 연결한다. 예를 들어, 오른쪽 자식 포인터가 null일 경우 중위 순회 순서상 다음 노드(후속자)를 가리키고, 왼쪽 자식 포인터가 null일 경우 중위 순회 순서상 이전 노드(선임자)를 가리키도록 만드는 방식이다.^[1] 이렇게 연결된 구조를 스레드라고 부르며, 이를 통해 트리를 특정 순서로 빠르게 순회할 수 있다. 스레드는 중위 순회 외에도 다양한 순서(예: 이름, 생년월일 등)로 노드를 연결하는 데 사용될 수 있다.

스레드 이진 트리는 스레드를 연결하는 방식에 따라 다음과 같이 나눌 수 있다.

• 단일 스레드(Single Threaded): 각 노드가 중위 순회 순서상 이전 노드 또는 다음 노드 중 하나만을 가리키도록 스레드를 설정한다. 즉, 왼쪽 스레드나 오른쪽 스레드 중 하나만 사용한다.
• 이중 스레드(Double Threaded): 각 노드가 중위 순회 순서상 이전 노드 및 다음 노드를 모두 가리키도록 스레드를 설정한다. 즉, 왼쪽 스레드와 오른쪽 스레드를 모두 사용한다.

6. 중위 순회 배열 (The array of in-order traversal)

스레드 이진 트리는 일반적으로 비어있는(null) 오른쪽 자식 포인터가 해당 노드의 중위 순회 상 후행 노드(in-order successor)를 가리키도록 하고, 비어있는 왼쪽 자식 포인터는 중위 순회 상 선행 노드(in-order predecessor)를 가리키도록 연결하여 만들어진다.^[1] 이는 트리의 순회 순서가 중위 순회 방식과 동일하다고 가정하는 방식이다.

결과적으로 스레드는 중위 순회 순서에 따라 각 노드의 선행 노드와 후행 노드를 가리키는 역할을 한다.

아래 그림으로 예시된 스레드 트리의 중위 순회 순서는 A, B, C, D, E, F, G, H, I이다. 이 순서에 따라, 노드 E의 선행 노드는 D가 되고, 후행 노드는 F가 된다.

7. 예시 (Example)

일반적인 이진 트리를 스레드 이진 트리로 변환하는 과정은 다음과 같다.

8. 널 링크 (Null links)

스레드 이진 트리에서 널 링크(null link)는 자식 노드를 가리키는 포인터가 비어 있는 경우를 의미한다. 일반적인 이진 트리에서는 이 포인터들이 단순히 아무것도 가리키지 않지만(NULL), 스레드 이진 트리에서는 이 널 링크를 활용하여 중위 순회 순서상 바로 이전 노드(선행자, predecessor)나 바로 다음 노드(후행자, successor)를 가리키는 특별한 포인터, 즉 '스레드(thread)'로 사용하기도 한다. 예를 들어, 아래 그림과 같은 스레드 트리에서 중위 순회는 A, B, C, D, E, F, G, H, I 순서이며, 노드 E의 선행자는 D, 후행자는 F가 된다.

''n''개의 노드를 가진 ''m''-방향 트리(일반적인 이진 트리의 경우 ''m''=2)에서 각 노드는 최대 ''m''개의 자식 포인터를 가질 수 있다. 따라서 이론적으로 가능한 총 자식 포인터의 수는 ''n'' × ''m'' 개이다. 이 중에서 실제로 트리의 구조를 형성하는 데 사용되는 링크(부모-자식 연결)의 수는 루트 노드를 제외한 모든 노드가 하나의 부모 노드를 가지므로 ''n''−1 개이다.

결과적으로, 트리 내에서 실제로 자식 노드를 가리키지 않는 포인터, 즉 널 링크(무효 링크)의 총 개수는 다음과 같이 계산할 수 있다.

널 링크 개수 = (총 가능한 자식 포인터 수) - (실제 사용된 링크 수)

= ''n'' × ''m'' − (''n''−1)

9. 구현 (Implementation)

C 언어를 사용하여 스레드 이진 트리에서 특정 노드의 부모 노드를 찾는 함수의 예시는 다음과 같다. 이 코드는 주어진 노드(`node`)에서 시작하여, 왼쪽 또는 오른쪽 포인터가 스레드인지 확인하며 부모 노드를 탐색한다. 루트 노드의 경우 부모가 없으므로 null을 반환한다. `is_thread()` 함수는 해당 포인터가 실제 자식 노드를 가리키는지, 아니면 스레드를 가리키는지 판별하는 함수라고 가정한다.



Node* parent(Node* node)

{

Node *x, *y, *p;

// 루트 노드는 부모가 없음

if (node == root)

return null;

x = y = node;

while (1)

{

// 오른쪽 포인터가 스레드인 경우

if ( is_thread(y->right) )

{

p = y->right; // 스레드를 따라감

// 스레드가 null이거나, 스레드가 가리키는 노드의 왼쪽 자식이 현재 노드가 아닌 경우

// (즉, 잘못된 스레드이거나 다른 경로로 탐색해야 하는 경우)

if (p == null || p->left != node)

{

p = x; // 탐색 시작점을 x로 재설정

// 왼쪽 자식이 스레드가 아닐 때까지 왼쪽으로 이동

while ( !is_thread(p->left) )

p = p->left;

p = p.left; // 최종적으로 왼쪽 스레드가 가리키는 노드가 부모

}

return p; // 부모 노드 반환

}

// 왼쪽 포인터가 스레드인 경우 (오른쪽과 대칭적인 로직)

else if ( is_thread(x->left) )

{

p = x->left;

if (p == null || p->right != node)

{

p = y;

while ( !is_thread(p->right) )

p = p->right;

p = p.right;

}

return p;

}

// 스레드를 찾지 못한 경우, 왼쪽 및 오른쪽 자식으로 한 단계씩 내려감

x = x->left;

y = y->right;

}

}



스레드 이진 트리에서 부모 노드를 찾는 다른 방법으로는 각 노드에 부모 노드를 직접 가리키는 포인터를 추가하는 방식이 있다. 이 방식을 사용하면 특정 노드에서 부모 노드로 쉽게 이동할 수 있다.

또한, 부모 포인터나 별도의 스택을 사용하지 않고도 스레드를 따라가며 부모 노드를 찾는 것이 가능하다. 예를 들어, 노드 ''k''가 오른쪽 자식 ''r''을 가질 때, ''r''의 왼쪽 포인터는 실제 왼쪽 자식이거나 ''k''를 가리키는 스레드이다. 만약 ''r''이 왼쪽 자식을 가진다면, 그 자식의 왼쪽 포인터 역시 자식이거나 스레드이다. 이 과정을 반복하여 왼쪽 포인터를 계속 따라가면 결국 ''k''를 가리키는 스레드를 찾게 되어 부모 노드 ''k''를 식별할 수 있다. 왼쪽 자식의 경우에도 오른쪽 포인터를 따라가며 유사한 방식으로 부모를 찾을 수 있다. 다만, 이 방법은 탐색 과정이 길어질 수 있어 상대적으로 느릴 수 있다.

파이썬으로 구현한 부모 노드 찾기 함수 예시는 다음과 같다. C 코드와 유사한 논리를 따르며, 실제 파이썬 환경에 맞게 노드 구조나 `is_thread` 함수 등을 정의해야 한다.



def parent(node):

# 루트 노드는 부모가 없음

if node is node.tree.root:

return None

x = node

y = node

while True:

# 오른쪽 포인터가 스레드인 경우

if is_thread(y.right): # is_thread는 스레드 여부 확인 함수로 가정

p = y.right

# 스레드가 None이거나, 스레드가 가리키는 노드의 왼쪽 자식이 현재 노드가 아닌 경우

if p is None or p.left is not node:

p = x

# 왼쪽 자식이 스레드가 아닐 때까지 왼쪽으로 이동

while not is_thread(p.left):

p = p.left

p = p.left # 최종적으로 왼쪽 스레드가 가리키는 노드가 부모

return p # 부모 노드 반환

# 왼쪽 포인터가 스레드인 경우 (오른쪽과 대칭적인 로직)

elif is_thread(x.left):

p = x.left

if p is None or p.right is not node:

p = y

while not is_thread(p.right):

p = p.right

p = p.right

return p

# 스레드를 찾지 못한 경우, 왼쪽 및 오른쪽 자식으로 한 단계씩 내려감

# 실제 구현에서는 x와 y가 유효한 노드인지 확인하는 로직 필요

if x.left is None and y.right is None:

# 이 예시 코드는 특정 조건에서 무한 루프에 빠질 수 있으므로

# 실제 구현 시에는 경계 조건 및 유효성 검사가 필요하다.

break # 루프 탈출 (예외 처리 또는 다른 로직 필요)

if x.left is not None:

x = x.left

else: # x.left가 None이면 더 이상 왼쪽으로 갈 수 없음

# 이 경우 y.right만 따라가거나, 로직 재검토 필요 (소스 기반 단순 이동)

pass # 또는 다른 처리

if y.right is not None:

y = y.right

else: # y.right가 None이면 더 이상 오른쪽으로 갈 수 없음

pass # 또는 다른 처리

참조

_[1] 서적 Data Structures and C Programs Addison-Wesley
_[2] 서적 Fundamental Algorithms Addison Wesley
_[3] 논문 Traversing binary trees simply and cheaply
_[4] 논문 Morris' tree traversal algorithm reconsidered
_[5] 서적 Fundamental Algorithms Addison Wesley
_[6] 논문 Symbol manipulation by threaded lists 1960-04