[DataStructure] Threaded Binary Tree

토즐라·2022년 5월 4일
0

이번 글은 서강대학교 소정민 교수님의 강의와 Ellis Horowitz의「Fundamentals of Data Structures in C」를 바탕으로 작성했음을 밝힙니다.

From Textbook

There are more null links than actual pointers. Specifically, there are n+1n+1 null links out of 2n2n total links. A.J Perlis and C. Thornton replaced the null links by pointers, called threads, to other nodes in the tree.
(1) If ptr -> left_child is null, replace ptr -> left_child with a popinter to the node that would be visited befor ptr in an inorder travestal. That is we replace the null link with a pointer to the inorder predecessor of ptr.
(2) If ptr -> right_child is null, replace ptr -> right_child with a pointer to the node that would be visited after ptr in an inorder traversal. That is we replace the null link with a ppointer to the inorder successor of ptr.

From Wiki

쓰레드 이진 트리는 이진 트리의 한 종류로, 가리키는 곳이 없는 모든 오른쪽 널 포인터(null pointer)를 중위 후속자 노드로 연결하고, 가리키는 곳이 없는 모든 왼쪽 널 포인터를 중위 선행자 노드로 연결한 것을 말하며, 재귀적인 중위 순회를 빠르게 할 수 있는 방법으로 사용된다.

1.1 Notion

Thread Binary Tree는 이진트리에서 약간 확장한 개념으로, 절반 이상의 node가 NULL값으로 채워지는 이진트리의 특성에서 착안해, 이러한 NULL node를 활용하는 방법입니다.

만약 left pointer가 NULL이면, 해당 pointer은 inorder predeccessor을 가르키고, right pointer가 NULL이면 해당 pointer은 inorder successor를 가르킵니다.

이 때 Bottom Level에서 맨 왼쪽 node(H)의 왼쪽 pointer와 맨 오른쪽 node(J)의 오른쪽 pointer는 가르킬 node가 없게 되는데요.

이 때, Dummy Root를 만들어 이 dummy root를 가르키게 만듭니다.

Inorder Successor

이진 트리에서 node의 inorder successor는 이진 트리의 중위 순회(inorder traversal)시 다음으로 방문할 노드를 말합니다.

Inorder Predeccesor

이진 트리에서 node의 inorder predeccesor는 이진 트리의 중위 순회 시 이전에 방문했던 노드를 말합니다.

profile
Work Hard, Play Hard 🔥🔥🔥

0개의 댓글