스레드 이진 트리 (Threaded Binary Tree)

* 참고: https://youtu.be/AndqtbiTfe8

 

1. 기존 이진 트리의 문제점

---

왼쪽 자식, 값, 오른쪽 자식을 저장하는 일반적인 이진 트리의 경우 대다수의 포인터(n+1)들은 null을 가리키고, 이는 메모리의 낭비를 일으킨다.

이런 이진 트리의 순행하기 위해서 스택 또는 큐가 필요한데, 이 역시 많은 저장공간을 필요로 하게 된다.

이를 해결하기 위해 우리는 스레드 이진 트리를 사용한다.

2. 스레드 이진 트리의 특징

---

스레드 이진 트리는

1. 널 포인터 대신 의미 있는 정보들을 저장한다.
2. 운행을 위해 스택 또는 큐를 사용하지 않는다.

 

이때 의미 있는 정보들이란 중순위 선행/계승 정보를 가리킨다.

왼쪽 null 포인터는 선행 노드를 가리키고 오른쪽 null 포인터는 계승 노드를 가리키도록 한다.

 

3. 스레드 이진 트리의 종류

---

1. Single Threaded Binary Tree: 선행 또는 계승 노드에 관한 정보 한 가지만 담고 있는 이진 트리

2. Double Threaded Binary Tree: 선행, 계승 노드에 관한 정보 두 가지 모두 포함하는 이진 트리

 

4. 스레드 이진 트리 노드의 구조

---

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    boolean leftThread; // 왼쪽 포인터가 중순위 선행 노드를 가리키는지
    boolean rightThread; // 오른쪽 포인터가 중순위 계승 노드를 가리키는지
}

leftThread 또는 rightThread 가

true 라면 left 또는 right는 선행 또는 계승 노드를 가리키는 스레드 포인터일 것이고

false 라면 자식 노드를 가리키는 실제 포인터일 것이다.

 

5. 스레드 이진 트리의 운행

---

스레드 이진 트리의 운행은 morris traversal 이라는 이름으로도 불린다.

1. Initialize current -> leftmost(node)
2. Loop while current NOT_NULL && current != DUMMY_NODE
    - process Node
    - if current has Thread
    	- current --> current.right
    - else
    	- current --> leftmost(current.right)

 

6. 스레드 이진 트리의 단점

---

1. 트리 운행 알고리즘이 복잡해진다.

2. boolean 값을 저장하기 위한 추가 공간이 필요하다.

3. 삽입 및 삭제가 더욱 어려워진다.

 

7. 스레드 이진 트리를 활용하는 경우

---

1. 삽입 및 삭제 연산보다 운행을 주로 많이 할 때

2. 스택 공간이 제한되어 있을 때