[알고리즘 지식 공부] 트리(Tree) 자료구조를 알아보자!

서론

안녕하세요~~ 개발자 제라스입니다~👋🏻🤖👋🏻

요즘 알고리즘 공부를 많이 하는 중인데 근래 들어 가장 문제 풀이에 시간이 많이 들었던 트리 구조를 한번 살펴보고자 합니다.

 

트리 구조는 2학년 때부터 학부 수업때 손코딩을 해볼 정도로 빠삭하게 공부했던 자료구조인데 막상 코드로 적용할 때는 항상 오랜시간이 걸려서 풀어내는 것 같습니다.

 

이게 또 종류가 몇가지 있고 각각마다 사용 시점이 달라서 한번 정리해두면 좋을 것 같아서 정리를 해보려고 합니다 ㅎㅎ

 

그럼 오늘도 한번 시작해보겠습니다~!!

트리 구조가 뭔데?

트리구조는 Node라고 하는 여러 지점들을 갖고 있는 형태로 가장 최상단의 한 Node에서 시작해서 뿌리가 퍼져나가 듯한 형태의 자료구조입니다.

 

간단하게 예시를 보면 다음 그림과 같은 형태에요.

출처: 나무위키 - 트리(그래프)

이렇듯 루트 노드(A)에서 자식 노드들로 선(간선, edge)을 연결하는 방식으로 연결하는 방식입니다.

 

트리에는 여러가지 소속된 것들이 있는데 명칭은 다음과 같아요!

 

가장 위에 있는 노드를 루트 노드(root node)

가장 끝에 달려있는 노드들을 리프 노드(leaf node)

어떤 노드를 기준으로 위에 있는 것을 부모 노드(parent node) / 아래에 있는 것을 자식 노드(child node)

같은 부모 노드에 달려있는 노드를 형제 노드(sibling node)

트리 내에 속한 트리 형태의 일부를 서브 트리(sub-tree)

 

이 외에도 노드에는 차수(degree), 크기(size), 깊이(depth), 레벨(level)이, 트리에는 높이(height)란 개념이 있습니다.

 

차수: 노드가 가진 자식 노드 수 or 간선 수

ex) 위 그림에서 A,B,C,D의 경우엔 차수가 2, 나머지는 0임.

 

크기: 자신을 포함한 모든 자식 노드의 개수

ex) 위 그림에서 B의 경우엔 크기가 5, C의 경우엔 3

 

깊이: 루트 노드에서 해당 노드에 도달하기 위해 거쳐야 하는 간선 수

ex) 위 그림에서 D의 경우 2, H의 경우 3

 

레벨: 해당 노드의 깊이와 동일함

ex) 위 그림에서 D의 경우 2, H의 경우 3

 

※ 근데 사실 레벨은 루트 노드를 0이 아닌 1로 시작하는 경우도 있습니다.

생각의 기준이 다른 것인데 이 부분은 크게 중요하지 않으니 레벨보단 깊이로 판단하시는 것이 더 일반적입니다.

 

높이: 트리에서 가장 깊이 아래에 있는 노드의 깊이

ex) 위 그림에서는 H가 가장 아래에 있기 때문에 트리의 높이는 3

 

개념이 너무 많죠...ㅎㅎ

그래도 한번 알아두면 편하니 스윽 읽어보시구 다음에 필요하면 다시 보면서 확인만 해도 충분합니다!

 

이 정도면 트리 개념은 이해가 되시죠??

이진 트리(Binary Tree)

그 다음은 이진 트리입니다.

이진 트리는 사실 중학교 때 배운 이진법! 이 이진법과 같은 개념입니다!

출처: https://heytech.tistory.com/105

 

이진 트리는 간단히 각 노드가 최대 자식 노드 수가 2인 트리입니다. 

한 노드에 자식 노드가 0~2개인 트리를 말하는 거죠!

여기서 완전 이진 트리는 리프 노드(맨 끝단에 있는 노드)들을 제외하고는 모든 노드들이 자식 수가 반드시 2인 트리입니다.

이렇지 않은 트리들은 불완전 이진 트리입니다. 

 

간단하죠?

그래서 보통 각 Node가 left, right, value 이렇게 3개의 데이터를 갖습니다.

python에서는 다음과 같이 초기화를 해요.

class Node:
    def __init__(self, key):
        # Node의 왼쪽에 빈 값(추후 노드를 둘 예정)
        self.left = None
        # Node의 오른쪽에 빈 값(추후 노드를 둘 예정)
        self.right = None
        # Node 자체가 가지는 값(value)
        self.value = key

 

Node(45) 이런 식으로 초기화한 Node를 만드는데 매개변수로 받아온 인자(key) 45는 해당 Node의 value 값으로 들어가집니다. 이때 left와 right는 각각 값을 갖는게 아니라 Node 객체가 들어가집니다. 자식 노드를 연결해야 하니까요!

트리 순회 방식 1 - 깊이 우선 탐색(DFS, Depth Fisrt Search)

이 방식은 깊이를 항상 먼저 생각하면서 탐색하는 방식입니다.

즉, 윗 레벨들을 모두 탐색하는 방식이 아닌 일단 깊게 깊게 파고 들어가서 탐색하고 천천히 위로 올라와 다음으로 넘어가는 방식입니다.

 

말로는 이해 어렵죠... ㅋㅋㅋㅋㅋㅋㅋ

그래서 다음 그림을 봅시다.

출처: https://cdragon.tistory.com/42

아니 이건 또 뭔 그림들이여...

사실 깊이 우선 탐색에는 3가지 방식이 있습니다.

이걸 이해하면 깊이 우선 탐색은 모두 이해한 것이나 마찬가지입니다.

 

한번 우리 아까 위에서 본 트리를 그대로 가져와서 설명해보겠습니다.

 

출처: 나무위키 - 트리(그래프)

(1) Preorder(전위 탐색): 루트 -> 왼쪽 -> 오른쪽 순으로 탐색

이 방식은 일단 어떤 노드에 도달하면 그 노드 값을 확인하고 그 다음에는 왼쪽 노드를 그 다음에는 오른쪽 노드를 탐색하는 방식입니다.

근데 만약 위에 있는 트리에서는 어떨까요?

 

1. 먼저 가장 루트에 있는 노드인 A를 탐색합니다.

2. 그 다음엔 당연히 왼쪽에 있는 B를 탐색합니다.

3. 그 다음엔 오른쪽의 C가 아닌 B의 왼쪽 D를 탐색합니다.(왜냐하면 우린 항상 어떤 노드에 들리면 그 노드를 탐색하고 그 노드의 왼쪽을 탐색하는 전위 탐색을 하기로 했기 때문입니다.)

4. 그 다음엔 또 D의 왼쪽인 H를 탐색합니다.

5. 그 다음 H에는 왼쪽 오른쪽 자식노드가 하나도 없으니 위(D)로 올라오는데 이미 우린 D-> H를 모두 탐색했으니 그 다음엔 오른쪽으로 가서 I를 탐색합니다.

6. 그 후엔 위로 쭉 올라와서 B-> D도 이미 탐색했으니 E를 탐색합니다.

7. 그 후엔 위로 쭉 올라와서 A-> B도 이미 탐색했으니 C를 탐색합니다.

8. C 이후엔 왼쪽 노드인 F를 탐색합니다.

9. 마지막으로 다시 C로 올라와서 오른쪽인 G를 탐색합니다.

 

그 결과 전위 탐색한 순서는 A-B-D-H-I-E-C-F-G 이 순서입니다.

 

(2) inorder(중위 탐색): 왼쪽 -> 루트 -> 오른쪽 순으로 탐색

이 방식은 항상 왼쪽이 먼저입니다.

그래서 트리에서도 루트인 A보다 B가 먼저고, B보다는 D가 먼저, D보다는 H가 먼저입니다.

 

1. H -> D -> I 순서로 탐색 후 다시 올라갑니다.

2. B -> E 순서로 탐색 후 다시 올라갑니다.

3. A를 탐색 후 C로 내려가는데 C보다는 F가 먼저라서 F -> C -> G 순서로 탐색을 합니다.

 

그 결과 중위 탐색한 순서는 H-D-I-B-E-A-F-C-G 입니다.

 

(3) postorder(후위 탐색): 왼쪽 -> 오른쪽 -> 루트 순으로 탐색

 

이 방식은 항상 자식들이 먼저이고 자식들 중 왼쪽이 먼저인 탐색 방식입니다.

그래서 트리에서도 A보다 B가 먼저, B보다는 D가 먼저, D보다는 H가 먼저입니다.

 

1. H -> I -> D 순서로 탐색 후 D의 형제 노드인 E를 탐색 후 B를 탐색합니다.

2. B의 형제노드인 C를 A보다 먼저 탐색하는데 C보다는 자식 노드들이 먼저이니 F -> G -> C 순서로 탐색합니다.

3. 마지막으로는 위로 올라와서 A를 탐색합니다.

 

그 결과 후위 탐색한 순서는 H-I-D-E-B-F-G-C-A 입니다.

트리 순회 방식 2 - 너비 우선 탐색(BFS, Breadth Fisrt Search)

너비 우선 탐색은 엄청 간단해요!!!

 

얘는 그냥 위에부터 같은 깊이인 애들 순서대로 탐색을 합니다!

 

너비 우선 탐색(BFS) 순서도

 

이런 식으로 말이에요~~!

이렇게 같은 레벨인 애들 먼저 탐색하고 다음 레벨로 넘어가기 때문에 Level Order Search 라고도 합니다.

 

위에서부터 쓱쓱 쓸고 내려오는 방식이라 외우기도 무척 쉽습니다.

 

그럼 BFS, DFS 얘네는 각각 언제 써요?

일단 공통적으로는 어떤 트리를 완전 탐색(모두 탐색하는 경우)에서는 둘 중 어느 걸 써도 똑같습니다.

이때는 시간복잡도가 약 O(N^2)입니다. 꽤 복잡하고 비효율적인 탐색이죠.(다 검색해본다는 것이니..ㅎㅎ)

 

(1) DFS(깊이 우선 탐색)

1. 사실상 모든 경우를 모두 탐색해서 답을 얻어내야 하는 경우

이건 조합, 순열 등 모든 경우의 수를 하나하나 다 찾아야 하는 경우에 사용합니다.

잉? 이게 무슨 소리?

예를 들면 {1,2,3,4,5,6,7}에서 부분집합을 구해야 하는 경우 방문 or 미방문 방식으로 하면 리프 노드에 모든 경우의 수가 모이게 됨.

 

2. 경로의 특징을 저장해야 하는 경우

각 지점마다 정해진 값이 있고 동일한 값은 들리면 안되는 경우 이런 특징을 고려하면 중간에 컷하고 들어갈 수 있어서 DFS를 쓰기 좋습니다. 사실 이건 BackTracking(백트래킹) 방식인데 둘이 비슷하고 때에 따라서는 깊이 끝까지 모두 탐색(DFS)하고 어떤 때는 중간에 조건에 안맞으면 되돌아가는(백트래킹) 방식을 사용합니다.

 

(2) BFS(너비 우선 탐색)

1. 최단경로 혹은 최단경로의 개수를 구해야 하는 경우

사실상 최단경로라는 말이 나오면 거의 반사적으로 BFS를 생각하면 됩니다.

정확히는 다익스트라, 플로이드-와샬 알고리즘 이 2가지 방식도 함께 생각해두면 좋습니다.

 

 

마무리

오늘은 트리 자료구조를 살펴봤습니다!

트리의 탐색 방식도 크게 두가지인 DFS, BFS 방식도 배웠고 어떤 알고리즘 문제에서 DFS를 쓸지 BFS를 쓸지도 알아보았습니다.

 

아 근데 사실 이 알고리즘에서 DFS를 쓸 지, BFS를 쓸 지는 사람마다, 문제마다 판단이 다르기 때문에 문제를 많이 풀어보면서 자신만의 감을 잡는게 중요한 것 같습니다 ㅎㅎ

 

엥...무책임하다 제라스...

 

이게 정답이란게 없기 때문에 이렇게 말씀드렸지만 사실 대부분은 최단경로 문제를 제외하고는 DFS를 중심으로 문제를 푸는 것 같습니다.

 

그럼 오늘도 이 정도로 마무리 짓고 다음번에는 트리를 활용한 코드들을 중심으로 살펴보는 포스팅을 올려볼게요!

끝까지 읽어주셔서 감사드리고 더 나은 포스팅으로 돌아오겠습니다 👍🏻🥹👍🏻

참고

https://worlf.tistory.com/16

트리(Tree)에 관한 개념 차수 등 정리

https://cdragon.tistory.com/42

[자료구조와 알고리즘 | 파이썬] Trees (트리 자료구조)

https://velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS-lp8zywtn

 

velog

https://foameraserblue.tistory.com/188

PS를 하며 느끼는 DFS와 BFS 선택의 기준

https://duckracoon.tistory.com/entry/DFS%EC%99%80-BFS-%EA%B0%81%EA%B0%81-%EC%82%AC%EC%9A%A9%ED%95%98%EB%8A%94-%EA%B2%BD%EC%9A%B0

DFS와 BFS 각각 사용하는 경우

https://choo.oopy.io/651eb670-9136-43e8-ad8d-7cdd65225cc1

완전탐색(DFS/BFS) VS 백트래킹+순열과 조합(백준N과 M)

https://veggie-garden.tistory.com/24   -> BackTracking과 DFS의 차이를 잘 설명한 블로그입니다!

[Python] 백트래킹 (+ DFS와 차이)

---

아직 꼬꼬마 개발자입니다.

더 나은 설명이나 코드가 있다면 언제든 환영입니다.

적극적인 조언과 피드백 부탁드립니다!

 

그럼 오늘도 개발 가득한 하루되세요!

- Xerath -

🤖🤖🤖🤖🤖🤖🤖