방송대 자료구조 교재 요약 제8 장 - 스레드 트리

제8 장 스레드 트리)

 

개관)

이진 트리를 순회할 때 방문하지 않고 지나쳐 온 노드는 스택에 저장한다.

이러면 스택 관리하기가 번거로운데 이런 번거로움을 없앤 트리가 스레드 트리다.

https://en.wikipedia.org/wiki/Threaded_binary_tree

(네...? 이 괴랄한 건 뭐죠...)

정해진 순회 방법에 따른 방문 순서를 유지하는 포인터를 스레드라고 한다.

이 스레드 포인터를 갖는 이진 트리가 스레드 트리다.

...

스레드는 오른쪽 스레드, 왼쪽 스레드, 2가지가 있다.

오른쪽 스레드는 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킨다.

왼쪽 스레드는 그 노드의 선행 노드를 가리킨다.

...

스레드 트리는 두 가지 방법으로 구현할 수 있다.

한 가지는 스레드를 저장하는 포인터를 추가하는 방법이다.

...

내가 여기까지 읽고 도저히 이해가 안 돼서 유튜브 영상을 하나 보고 왔다.

https://www.youtube.com/watch?v=B7Bl1VbFCI4

 

이거라도 하나 보니까 이해가 더 된다.

듣기 쉬운 영어로 된 영상은 못 찾았고 힌디는 내가 못 듣겠어서 이놈으로 정함.

자, 다시 본문으로 돌아가자.

스레드 트리는 두 가지 방법으로 구현할 수 있다.

하나는 스레드를 저장하는 포인터를 추가하는 방법이다.

왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터.

이게 기본적인 스레드 트리의 노드 구조다. <- 이 부분은 동영상에 나온다.

다른 방법으로는 이진 트리를 위한 연결 리스트의 노드 구조를 그대로 사용하면서, 잎 노드에 있는 빈 포인터를 활용하는 방법이다.

이 방법은 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브트리에 대한 포인터인지를 구분하기 위해 태그 필드를 사용해야만 한다. <- 이 부분은 동영상에 나오지 않는다.

...

학습 목표)

1. 스레드 트리가 뭔지 알아 보자.

2. 스레드 트리를 어떻게 만드는지 알아 보자.

3. 스레드 트리의 순회 연산과 삽입, 삭제 연산을 이해해 보자.

...

용어 정리)

스레드(thread): 정해진 순회 방법에 따른 방문 순서를 유지하는 포인터

스레드 트리: 스레드라는 포인터를 갖는 이진 트리

...

1. 스레드 트리

스레드 트리는 이진 트리 순회 방법 중 하나를 적용했을 때의 순서를 유지한다.

필요하다면 다중 스레드를 사용해 모든 순회에 따른 순서를 유지하는 스레드 트리를 구성할 수도 있다.

교재에서는 감사하게도, 특정한 한 가지 순회에 의한 방문 순서를 유지하는 경우만 언급한다.

...

2. 스레드 트리 구현

스레드 트리는 두 가지 방법으로 구현할 수 있다.

트리를 연결 리스트로 구현할 때 노드 구조를 정의하면서 스레드를 저장하는 포인터를 추가하는 게 한 가지 방법이다.

다른 방법으로는 이진 트리를 위한 연결 리스트의 노드 구조를 그대로 사용하면서, 잎 노드에 있는 사용하지 않는 포인터를 활용하는 방법이 있다.

...

스레드를 저장할 포인터 필드를 노드 구조에 추가하면 스레드를 위해 추가 기억 장소(메모리)를 사용한다는 부담이 있다.

잎 노드의 빈 포인터 필드를 활용하는 방법은 어떨까?

이 방법을 사용하면 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브트리에 대한 포인터인지를 구분하기 위해 플래그 필드를 사용해야만 한다.

...

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

교재 195페이지에 이르니, '중위 순위 스레드 트리의 중위 순회 코드'라는 표현이 자연스럽게 이해되지 않는다면 잠시 휴식을 취한 후 앞에 배운 배용을 복습하는 걸 권장한다고 한다.

이게 그냥 읽기만 해서 이해가 점점 되는 식이었으면 그렇게 했겠다... 🥹...

...

각 노드의 포인터는 스레드가 아니면 실제 자식을 가리키는 포인터다.

스레드 트리에 삽입이나 삭제 등의 작업을 한다면 스레드 트리 구조를 유지하기 위해 두 개의 스레드 필드를 사용한다.

...

여기까지 읽느라고 정말 힘들었다.

이제 힙 차례다.