1. 개요

• 앞서 살펴본 List와 Stack, Queue등은 메모리 소모도 적은편이고, 사용함에 있어 시간도 오래걸리지 않는다.

• 하지만, 만약 원하는 데이터가 중간에 있다면, 그 이전의 데이터들을 모두 삭제해야만 얻을 수 있다.

• 위와 같은 특성으로 인해, 탐색이 매우 불편하다. 대부분의 경우 O(n)이며, Sorted ArrayList에 한하여 O(log n)이지만, 이 경우 add/remove가 O(n)이다.

• Tree는 탐색이 자주 일어나는 경우 사용하기 적합한 자료구조이다. Tree는 Node들이 서로 연결된 부모 자식 관계에 있으면서 순환하지 않는 자료구조로, 한 Node는 반드시 하나의 부모 Node만을 가지지만, 자식은 여럿일 수 있다. 그래서 Linear하지는 않을 수 있다.

• Node들 가운데 자식을 가지는 Node는 Internal Node라고 하며, 자식이 없는 Node는 External Node 혹은 Leaf라고 부른다.

• 자식 Node에서 부모 Node로 이동하다보면, 어디서 시작하느냐에 상관없이 반드시 최종적으로 부모를 가지지 않는 하나의 Node로 수렴하는데, 이를 Root라고 한다.

• Root를 기준으로 자식으로 내려갈수록 Depth가 증가한다. Root는 Depth가 0이고, 자식으로 내려갈수록 1씩 증가한다.

• 반면, Height는 자식, 그 중에서도 Leaf를 기준으로 한다. Leaf의 Height는 0이며, Leaf의 바로 위의 부모의 Height는 1, 그 이상의 부모로 갈수록 1씩 늘어난다.

2. Binary Tree

• Binary Tree는 다음의 조건을 만족하는 Tree이다.

  	1. 모든 부모는 최대 2명의 자식만을 가진다.
  	2. 자식은 left 혹은 right로 부른다.
  	3. left child가 right에 선행한다.

• 고로, Node는 인스턴스로 data, left pointer, right pointer를 가진다.

• 모든 Node가 0 혹은 2의 자식을 가지고 있으면, Full 상태라고 한다.

• 최하 Depth, 즉, 가장 Depth가 깊은 층을 제외한 모든 층의 Node들이 2명의 자식을 가지고 있으며, 최하층 또한 왼쪽부터 오른쪽까지 빈 공간이 없이 있으면 Complete 상태라고 한다.

• Leaf를 제외한 모든 Node가 1명의 자식만을 가지고 있으면, Degenerate tree라고 부른다. 즉, SinglyLinkedList는 Degenerate tree라고 할 수 있다.

3. Traversal

• Tree의 모든 Node를 정확히 한번만 방문하는 것을 traversal이라고 부르는데, Stack의 원리를 기반으로 회귀를 이용한 Depth-first traversal과 Queue를 이용한 Breadth-first traversal로 나눌 수 있다.

• Depth-first는 다시 preorder, postorder, inorder traversal로 나눌 수 있다.

• Preorder와 postorder, inorder의 Pseudo Code는 다음과 같다.

preorder(Node node):
	if node is not null:
    	look at the data in node
        recurse left
        recurse right

postorder(Node node):
	if node is not null:
    	recurse left
        recurse right
        look at the data in node


inorder(Node node):
	if node is not null:
    	recurse left
        look at the data in node
        recurse right

• 만약 상기의 traversal을 Binary Search Tree에 적용할 경우, preorder와 postorder의 결과물을 각각 앞과 뒤에서부터 순서대로 tree를 작성할 경우, 원본 BST와 똑같은 tree를 얻을 수 있다. inorder의 경우, tree의 가장 작은 값부터 가장 큰 값까지 정렬한 결과를 얻을 수 있다. 중요한 것은, 이 특징들은 오직 BST를 traversal한 경우에만 적용된다는 것이다.

• Breadth-first traversal은 levelorder traversal이 존재한다. Pseudo Code는 다음과 같다.

levelorder():
	Create Queue
    Add root to q
    while Queue is not empty:
    	Node curr = dequeue()
        if curr is not null:
        	enqueue(curr.left)
            enqueue(curr.right)

• Levelorder를 이용한 결과물은, root부터 각 level의 데이터를 왼쪽부터 오른쪽까지 순서대로 나열한 것과 같다.

• 상술한 4개의 traversal은 탐색에도 적용할 수 있다. 넷 모두 BST에 적용할 경우, preorder은 원하는 결과가 root에 가까울수록 빠르게 찾을 수 있고, postorder은 leaf에 있을수록 빠르다. Inorder는 BST에 적용할 경우 정렬된 결과물을 받을 수 있고, levelorder의 결과물은 tree 구조를 파악하기 쉽다. 물론, 넷 모두 O(n)의 시간복잡도를 가지긴 한다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xII+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.