Chapter 8: Tree

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

Tree

data 간에 위계 질서, 즉 hierarchy가 존재할 때 data를 표현하는 방식을 tree라고 한다.

• e.g., 조직도, 파일 시스템

 

Nodes

▶ Parents and Children Nodes

▶ Root Node

▶ Leaf Nodes

 

Level

▶ Level 0

▶ Level 1

▶ Level 2

 

Subtree

▶ Left subtree

▶ Right subtree

 

Type Data

▶ Char Type Data

▶ Int Type Data

 

Unique Path

▶ A unique path exists from the root node to every other node.

• The path from E to Z: E -> C -> Z (acyclic structure)

 

만약 F와 Z가 연결되어 있으면, 즉 cyclic structure이면 E -> Z path가 unique 하지 않게 된다.

 

Binary Tree

▶ Each node in a binary tree can have up to two child nodes.

 

바이너리 트리에서 요구하는 정의는 모든 노드들이 2개 이하의 child node만 가지고 있는 다는 것 뿐이다.

즉, 0개를 가지고 있어도 되고, 1개를 가지고 있어도 된다.

 

▶ Level of Binary Tree (# Nodes)

• level 0의 노드 개수는 1개 혹은 root 노드가 아예 없을 (트리가 아예 빈 경우) 수 있다.

 

Some Terms

• Ancestors of a node: any node on the path from the root to that node (parent, grandparent, ...)
• Descendants of a node: any node on the path from that node to the last node in the path (child, grandchild, ...)
• Height of a tree: number of levels (여기선 4)

 

▶ Max Nodes in Binary Tree

 

▶ Max and Min Heights of N Nodes

• 양쪽에 밸런스 있게 노드를 두면 높이가 낮아지고, 반대로 child를 한 방향으로 몰아 넣게 되면 높이가 높아짐
• 한쪽으로 아예 일직선으로 몰아 넣게 되면node의 개수인 N이 Height가 됨 (최대 높이)
• 완전한 이진 트리라면 높이 h일 때 최대로 가질 수 있는 노드 수는 2^h - 1 이므로 h = log(N + 1)이 됨 (최소 높이)

 

※ 컴퓨터 분야에서 사용하는 로그들은 밑이 2라고 생각하면 된다.

 

▶ findItem() in a tree

• Time Complexity: O(N) (모든 노드를 한 번씩 다 살펴봐야 함, unsortedList와 비슷함)

 

이렇게 순수한 바이너리 트리를 만들었을 때의 이점은 없다.

때문에 여기에 추가적으로 성질을 부여한 다른 트리들에 대해 배워야 한다.

 

Binary Search Tree

Binary Search Tree (BST) 

A binary search tree is a special kind of binary tree in which:

• Each node contains a distinct value, -> 중복 값 없이 유니크한 값 (고유값)
• The key values in the tree can be compared using "greater than" and "less than" -> 숫자, 아스키 O / 색깔 X
• The key value of each node in the tree is less than every key value in its right subtree and greater than every key value in its left subtree. (작으면 왼쪽, 크면 오른쪽)

▶ Binary Search Tree Example

• All values in the left subtree < E
• E < All values in the right subtree

 

How to Build a BST

The shape of a BST depends on its key values and their order of insertion.

▶ Comparison

• 중간값이 가운데 와야 왼쪽과 같이 balanced -> 정렬 후, 중간값을 재귀적으로 삽입
• 오름차순, 혹은 내림차순 순서로 노드가 들어갈 때 오른쪽과 같이 unbalanced

▶ Exercise

▶ Exercise: Solutions

 

Why We Use a BST

It allows us to use a deterministic technique to find a specific value in the tree.

즉, 크기에 따라 자리가 정해져 있기에 search 하기에 좋다. (있어야 될 자리에 있으면 있고, 없으면 없는 것)

 

findItem(F) in a BST

• 1. Start at the root
• 2. Compare the value of the item you are searching for with the value stored at the root
• 3. If the values are equal, then item found; otherwise, if it is a leaf node, then not found
• 4. If it is less than the value stored at the root, then search the left subtree.
• 5. If it is greater than the value stored at the root, then search the right subtree.
• 6. Repeat steps 2-6 for the root of the subtree chosen in the previous step 4-5.

-> Time Complexity: O(H)

• 높이가 낮을 수록 알고리즘 효율성이 올라가기에, binary tree를 밸런스 있게 꽉꽉 채워주는 것이 좋음 -> min = O(log N)
• 반대로, 일직선으로 tree가 만들어져 높이가 최대 높이가 되면 linked structure와 비슷하게 됨 -> max = O(N)
• BST의 시간 복잡도는 평균적으로 O(log N), 최악으로 O(N)이 나옴

 

Binary Search Tree Implementation

▶ Node Structure for Binary Trees

▶ TreeType Definition

 

operator=

• 선언과 초기화가 동시에 일어나는 케이스, 패러미터로 넘어오는 케이스, 리턴되는 케이스, 이렇게 세 가지 케이스에 대해서는 copy constructor를 만들어 놓으면 자동으로 deep copy가 적용
• but, 선언과 초기화가 따로 이루어지는 경우에는 자동 적용 X

-> 선언과 초기화가 따로 이루어지는 상황에서도 deep copy를 하고 싶으면 operator overoading을 해주어야 한다.

 

※ TreeeType(const TreeType<ItemType> &); -> 복사 생성자를 통해 shallow copy가 아닌 deep copy로 새 객체 생성

 

IsFull() & isEmpty()

▶ Implementation Level

 

length() & countNodes()

▶ Logical Level

 

How can we count the number of nodes in a tree?

• Recursion: # nodes(tree) = # nodes(left) + # nodes(right) + 1
  • Base Cases: The (sub)tree is empty (length == 0)
  • General Cases: length(left) + length(right) + 1

▶ Implementation Level

• 노드 하나 이상 존재
  • 현재 노드 1개 (루트 노드, 즉 자기 자신)
  • 왼쪽 서브트리의 노드 수 countNodes(Tree->left)
  • 오른쪽 서브트리의 노드 수 countNodes(tree->right)

 

Time Complexity는 O(N), 이때 O(2^N) 아님을 주의해야 한다.

• 각 노드를 정확히 1번 방문하고, 중복 호출이 없기 때문에 시간 복잡도는 O(N)
• 재귀적으로 호출하며 분기한다고 해서 무조건 O(2^N)이 되는 것 X

 

※ countLevels 함수 구현

int TreeType::countLevels(TreeNode* tree) {
    if (tree == nullptr) {
        // 빈 트리의 높이는 0
        return 0;
    }
    else {
        int leftLevel  = countLevels(tree->left);
        int rightLevel = countLevels(tree->right);

        // 더 깊은 쪽 서브트리에 +1(현재 노드의 level)
        if (leftLevel > rightLevel)
            return leftLevel + 1;
        else
            return rightLevel + 1;
    }
}

 

findItem() & find() 

▶ Logical Level

 

Recursive Solution:

• 1. Compare 22 with 17 -> choose right subtree
• 2. Compare 22 with 25 -> choose left subtree
• 3. Compare 22 with 20 -> choose right subtree
• 4. Compare 22 with 22 -> item found!

Base Cases:

• When the "item" is found
• When the "current tree" is nullptr (not found)

General Cases:

• Search in the left or right subtrees

▶ Implementation Level

• Time Complexity: O(H) = O(log N) ~ O(N)

▶ findItem() through Iteration - Implementation Level

• Time Complexity: O(H) = O(log N) ~ O(N)

insertItem() & insert()

▶ Logical Level

 

How many recursive calls should be called until finding the proper location?

• 4 times (root, 25, 20, empty)
  • Base Cases: When the "current tree" is nullptr (insert)
  • General Cases: Search in the left or right subtrees

▶ Logical Level (3rd recursion)

 

Since "item (19)" < "tree->value (20)" it will call insert(tree->left)

And then 4th insert() should add the node accordingly.

 

4th insert() should modify the parent node's (node 20) "left" pointer.

How?

• Call (Pass) by Reference

▶ Implementation Level

• base 케이스에서 tree 매개변수는  root->left 라는 포인터 변수 자체의 별명이 됨
• 때문에, 실제로는 root->left = new TreeNode<ItemType>; 가 됨
• 즉, 부모 노드의 left 포인터가 새 노드를 가리키게 됨

 

deleteItem() & delete()

▶ Logical Level

 

Deleting the item from the tree requires additional work! 

Because we should manintain the linked structure and BST's property. (메모리 누수 방지 및 BST 성질 유지 필요)

▶ Case #1: Deleting a leaf node (e.g., deleteItem(22))

• Just delete it -> The remaining tree is still a BST

▶ Case #2: Deleting a node with one child (e.g., deleteItem(20))

• Delete it and move the child to its location

▶ Case #3: Deleting a node with two children (e.g., deleteItem(25))

 

How do we decide the node to be moved?

• What could make movements less? 삭제할 노드(25)와 가장 가까운 값
  • 왼쪽 서브 트리 안에서 가장 큰 값 (22) -> No more changes (predecessor 전임자)
  • 오른쪽 서브 트리 안에서 가장 작은 값 (27) -> No more changes (successor 후임자)
    

1. predecessor or successor (가장 가까운 값) 찾기 (일반적으로 predecessor를 사용)

2. 삭제 대상 노드 값에 predecessor 값을 복사

3. Delete a predecessor or successor node (case1, 2 삭제하는 방식과 동일)

▶ Implementation Level

• To update the tree, we define another function deleteNode()
• 시간 복잡도: O(H) (
  • getPredecessor 시간 복잡도의 상수 배이긴 하지만, 시간 복잡도에선 상수는 무시

 

▶ deleteNode() - Implementation Level

• tree = tree -> right or left: 부모의 포인터를 "지워질 노드"에서 "그 노드의 왼쪽 자식"으로 바꿈
• 그냥 할당 해제하는 delete가 아닌 recursive 함수인 delete 호출
  • subtree 중 젤 큰 값에 left subtre가 달려 있을 수 있기 때문 (case 2 delete 방식)

 

▶ getPredecessor() - Implementation Level

• findItem과 동일한 기능 just recursion -> iteration
• 시간 복잡도: O(H)

 

Tree Traversal

A tree traversal means visiting all the nodes in the tree.

• "Vist" means that the algorithm does something with the values in the node (e.g., print the value, etc.)

 

When Do We Need to Traverse?

 

When we want to do something with all nodes in the tree.

• Print the tree in ascending order - Inorder Traversal: left -> root -> right (오름차순)
• Copy the tree - Preorder Traversal: root -> left -> right (DFS)
• Delete the tree - Postorder Traversal: left -> right -> root

Inorder Traversal

▶ printf the tree (BST) in ascending order

• 1. Left subtree
• 2. Parent
• 3. Right subtree

※ 이때 일반 tree가 아닌 BST이기에 오름차순인 것이니 주의해야 한다.

 

inOrderPrint()

▶ Implementation Level

 

inOrder()

▶ Implementation Level

• 오름차순으로 Queue에 넣어 놓음
• 이후, 해당 Queue를 하나식 꺼내 처리하는 방식으로 원하는 기능 구현 가능

Preorder Traversal

▶ copy the entire tree (deep copy).

• 1. Parent
• 2. Left subtree (Child)
• 3. Right subtree (Child)

This traversal is also called "Depth-first search (traversal)", shortly DFS.

 

 

 

그래프를 탐색하는 방법

 

그래프란 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,

그래프를 탐색한다는 것은 하나의 정점에서 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

 

※ 트리: 그래프 중에서 방향성이 있는 비순환 그래프

 

1. 깊이 우선 탐색 (DFS, Depth-First Search)

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

DFS는 지나온 길을 기억해야 다음 갈림길로 되돌아가 다른 경로도 탐색할 수 있으므로

스택이나 재귀 함수로 구현한다. (되돌아오는 구조: 백트래킹)

• 스택: LIFO 구조라서 가장 마지막에 간 길부터 되돌아올 수 있음
• 재귀 함수: 탐색이 끝나면 되돌아옴

2. 너비 우선 탐색 (BFS, Breadth-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동 (최단 경로 알고리즘)

BFS는 바로 연결된 노드를 먼저 큐에 넣고, 그 다음 단계로 연결된 노드를 또 다른 큐에 넣는 식으로 구현한다.

• 큐: 다음에 방문할 노드를 저장하는 개념으로, 경로 전체를 기억하지는 못함

 

PreOrderPrint

▶ Implementation Level

 

PreOrder 

▶ Implementation Level

• We can use the queue to store the order of traversal. -> do something other than "print"

Postorder Traversal

▶ delete the entire tree

• Left subtree (Child)
• Right subtree (Child)
• Parent

postOrderPrint()

▶ Implementation Level

• We can use the queue to store the order of traversal. -> do something other than "print"

postOrder()

▶ Implementation Level

Big-O Comparison

 

tree에서 length를 계산할 때는 countNode를 사용해 recursive하게 구현하는 것이 기본이다.

물론, length라는 변수를 만들어서 상수 시간 복잡도로 구현해도 된다.

 

아이템을 찾고, 삽입하고 제거하는 것을 가장 많이 사용하기에 셋 중에 BST가 가장 성능이 좋다고 볼 수 있다.

 

Binary Tree Types

Binary Tree: 각 노드가 최대 2개의 자식 노드를 가지는 트리

 

Full Binary Tree (정 이진 트리)

모든 노드가 2개의 자식을 가지거나 자식이 없는 이진트리이다. (자식이 한 개인 경우가 없는 이진 트리)

 

⭐ Complete Binary Tree (완전 이진 트리)

마지막 level을 제외하고는 모든 노드가 채워져 있고, 노드는 왼쪽부터 채워진 트리이다.

complete binary tree의 경우, child가 하나인 경우도 존재할 수 있으니 주의한다. (젤 오른쪽 아래에 최대 1번 존재 가능)

 

Perfect Binary Tree (포화 이진 트리)

모든 노드가 2개의 자식을 가지고, leaf 노드가 모두 같은 level인 트리이다.

Binary Tree Types

	full binary tree	complete binary tree	perfect binary tree
a	O	O	O
b	X	X	X
c	X	O	X
d	O	O	O
e	X	X	X
f	O	O	X

 

Complete Binary Tree ⊂ Full Binary Tree (X)

-> 완전 이진 트리는 자식이 1개인 노드가 있을 수 있어서 Full이 아닐 수도 있음.

Complete Binary Tree ⊂ Perfect Binary Tree (X)

-> 완전 이진 트리는 마지막 레벨만 다를 수 있어서 항상 완전(perfect)하지는 않음.

Full Binary Tree ⊂ Complete Binary Tree (X)

-> Full은 자식 0개 또는 2개를 가졌다는 뜻이지, 꼭 왼쪽부터 채워져 있어야 하는 건 아님.

Full Binary Tree ⊂ Perfect Binary Tree (X)

-> Full이어도 레벨이 전부 안 찼을 수 있음

Perfect Binary Tree ⊂ Full Binary Tree (O)

-> Perfect는 모든 노드가 자식 0개 또는 2개를 가지므로 Full 조건을 항상 만족함.

Array Representation of Trees

▶ tree.nodes[index]

• left child: tree.nodes[index*2 +1]
• right child: tree.nodes[index*2 +2]
• parent: tree.nodes[(index-1)/2]

 

위쪽 이미지처럼 complete binary tree의 경우 array의 빈 공간 없이 쭉 채울 수 있다. 

 

그리고, 이렇게 array로 tree를 표현하는 것은 binary tree에서만 사용하는 방식이다.

• 이점: 한 번 내려오면 돌아갈 수 없는 linked structure의 한계를 해결 가능하다. (부모 노드 인덱스 계산 가능)

 

※ 힙이라는 특이한 형태의 트리가 존재를 하는데, 이때 array를 사용해 트리를 만든다.

 

---

참고자료

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

https://rosweet-ai.tistory.com/55

자료구조 이진트리(Binary Tree) 그림으로 쉽게 이해하기