2주차 개념 #2. 트리(Tree Data Structure)

2주차 개념 #2. 트리(Tree Data Structure)

오늘은 트리에 대해서 배워보도록 할게요.

저희 나무 한번 생각해볼까요.

이러한 나무를 뒤집으면 어떻게 될까요?

뒤집으면 이렇게 되겠죠? 이러한 모습, 그러니까 나무를 뒤집은 모습을 가지고 있는 자료구조를 트리다 라고 해요.

오늘은 트리에 대해서 배워보도록 하겠습니다.

트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미합니다.

먼저 자식노도와 부모노드로 잠깐 예를 들어볼게요.

중간에 있는 이 노드를 중심으로, 이 노드를 기반으로 만들어지는 경로 상에서 위에 있는게 부모, 아래에 있는게 자식입니다. 즉, 위에 있으면 부모구요. 아래에 있으면 자식 노드가 된다라는 거에요.

그리고 지금 보시면은 층층이 계단식 계층적 구조를 가지고 있죠.

우리가 회사를 가면은 보통 조직도 있죠. 그거를 생각하시면 돼요. 그래서 계층적인 구조를 가지고 있다는 거예요.

그리고 무방향 그래프의 일종이라는 얘기는 앞서서 단방향 간선과 양방향 간선을 배웠죠.

자 사실은 이건 방향 그래프에서 설명을 하는 거예요. 우리가 지금 그래프 이론을 배우고 있는 거예요.

자, 뭐냐면 그래프 이론 중에서 방향 그래프로 설명하는 게 있고, 무방향 그래프로 설명하는 게 있는 거예요.

자, 방향 그래프는 directed graph, 무방향 그래프는 undirected graph 라고 설명을 해요. 근데 방향 그래프는 u에서 v, v에서 u 라는 방향이죠.

근데 무방향 그래프에서의 간선은 이렇게 돼요.

방향이 없죠. 그래서 트리를 설명할 때는 방향 그래프로 설명을 하는 게 아니라, 트리를 설명할 때는 보통 무방향 그래프를 중심으로 설명을 합니다.

방향성이 없는, 그러니까 무방향은 얘에서 얘로 갈 수도 있고요. 반대로 얘에서 얘로도 갈 수가 있다는 걸 의미하는 거예요.

자 참고로 조금 더 자세히 설명을 하면,

이 방향성이 있는 간선을 directed Edge 라고도 하고 arc 라고도 해요.

이거는 참고 삼아 알아두시면 되구요. 트리는 방향성이 없는 무방향이라고 했고, 그리고 사이클이 없는 자료구조라고 했는데, 사이클이 뭐냐? 무한 루프를 생각하시면 돼요.

이런 거죠. 그런데 트리는 이런 게 없잖아요.

그래서 트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미합니다.

중요하니까 트리의 개념은 꼭 외워두세요.

---

그리고 트리는 그래프의 일종이에요.

그래프는 정점과 간선의 집합이 그래프라고 했죠. 그런데 이러한 집합 중에서 트리라는 특징을 가진, 그러니까 그래프의 하위 집합인 거죠.

하위집합이라는 걸 더 설명하자면,

이런 것처럼 그래프 이론, 그러니까 그래프 내에서 이 하위집합으로 Tree 라는 게 있다고 하는 거예요.

그러니까 정점과 간선으로 이루어진 집합인데, 트리라는 특징을 가진 자료구조를 트리다. 라고 하는 거예요. 그러한 특징을 보도록 하겠습니다.

일단 첫 번째는 앞서서 설명을 했는데, 계층적인 구조다라고 했는데, 예를 들어서 5번 노드를 볼게요.

자 5번 노드를 중심으로 봤을 때 6번 노드와 7번 노드한테는 5번 노드가 부모노드죠?

그리고 5번 노드의 자식 노드는 6, 7번이죠.

같은 경로상에 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식노드가 되는 거예요.

그리고 두 번째 V - 1 = E 라는 특징이 있습니다. 이 V는 vertex라고 부릅니다.

이건 뭐냐면,

이러한 트리가 있고, 트리의 정점의 개수를 세어보면

정점(vertex)는 7개죠. 영어 표현은 외워둡시다. 정점은 vertex, 간선은 Edge이고 이걸 축약적으로 V, E 라고 합니다.

간선의 개수도 세어보면 6개입니다. 따라서, V - 1 = E 라는 특징을 가진다는 겁니다. 그래서 간선 수는 노드 수 - 1 입니다.

그리고 세번째, 임의의 두 노드 사이의 경로는 ‘유일무이’하게 ‘존재’합니다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나밖에 없습니다.

이거 무슨 말이냐면,

제가 아래 노드에서 중간 노드로 갈 수 있을까요 없을까요? 갈 수 있죠.

이 노드에서도 옆의 자식 노드에게 이동하는 것이 가능하죠.

물론 이렇게 가는 것도 경로라고 할 수 있지만, 보통 경로를 얘기할 때는 최단경로를 얘기합니다. 그러니까 트리 내의, 트리라는 자료구조 안에 있는 노드라면, 어떤 노드든 갈 수 있다는 거예요.

그런데 트리의 특징을 가지지 않는 그래프라면 이런 게 불가능할 수 있어요.

그래프는 사실 정점과 간선의 집합이기 때문에

이런것도 그냥 그래프다라고 볼 수가 있는 거에요.

그래서 사실 이 정점에서 이 정점까지는 간선이 없으니까 못 가잖아요. 그런데 이 트리라는 자료구조 내에서는 무조건 어떤 노드든 그 노드부터 시작해서 어떤 노드까지 가는 경로가 유일무이하게 존재한다는 거예요.

자 그리고 1번 노드는 뭐라고 불러요?

1번 노드는 루트노드입니다. 대빵이죠.

자, 우리가 만약에 트리에 관련한 알고리즘 문제가 나왔어요. 그러면 루트 노드부터 시작해서 풀리는 게 좀 많아요.

그러니까 예를 들어서 문제에서 트리라는 자료구조라고 명시적으로 해놨어요.

자, 여러분 제가 문제를 낼 건데요. 이 그래프는 트리입니다. 이런 식으로 문제에서 알려주는 경우가 있어요.

그럴 때는 루트노드를 먼저 확인하고, 루트노드부터 시작해서 DFS든 BFS를 돌리면 쉽게 풀리는 게 많다는 거에요. 이거는 팁이었구요.

일단은 루트 노드는 뭐다? 가장 위에 있는 겁니다.

그럼 리프노드는 뭐에요? 리프 노드는 끝에 있어요. 그냥 맨 끝에 있는 게 리프 노드다.

자, 그럼 루트 노드와 리프 노드 사이에 있는 게 뭐죠? 내부 노드라는 거예요.

자, 다시 트리는 세 가지의 노드로 이루어져 있는 거예요. 루트, 내부, 리프 노드. 이렇게 세 가지로 이루어져 있고요.

알고리즘 고인물과 카톡한 내용인데 '난 리프해' 이러죠. 자식노드가 없어서 외롭다고 한 겁니다.

자 다시 리프노드는 뭐다? 자식노드가 없다.

---

자, 이제 트리의 높이와 레벨에 대해서 얘기를 해보도록 할게요.

자, 이게 높이에요. 가장 위부터 가장 아래까지.

그리고 이게 깊이 또는 레벨이 될 수가 있고,

이 부분을 서브트리라고 볼 수가 있어요. 서브트리는 트리 내에 트리 구조를 가지고 있는 거죠.

트리에서의 깊이는 각각의 노드마다 다르며, 루트 노드에서 특정 노드까지 최단거리로 갔을 때의 거리를 말합니다.

예를 들어 4번 노드의 깊이는 2입니다.

트리의 높이는 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리를 의미하며 앞 그림의 트리 높이는 3입니다.

레벨은 사실은 깊이랑 좀 같은 의미인데 사실 이게 문제마다 좀 달라요. 어떤 문제는 1번 노드를 0레벨로 하는 경우도 있고요. 어떤 문제는 0레벨이 아니라, 레벨 1로 하는 경우가 있어요.

만약에 1번 노드가 레벨 1이면 2, 3번은 레벨 2이고 그리고 4, 5, 8번 노드는 레벨 3 이렇게 되겠죠?

제가 그림을 그리면서 한번 설명해 볼게요. 레벨은 아까 설명한 깊이와 좀 비슷한 의미를 가지는데, 이게 좀 문제마다 달라요.

우리가 문제를 안 풀 수는 있지만 문제가 나온다라고 해보면 문제에서 만약에 1번 노드를 레벨 1로 주어지잖아요.

그럼 이렇게 되겠죠.

근데 만약 문제에서 1번 노드를 레벨 0으로 두면 이렇게 되는 거예요. 깊이랑 좀 비슷한 의미죠.

서브트리는 트리 내에 있는 부분집합 입니다.

숲은 뭐냐면 트리로 이루어진 집합을 숲이라고 해요.

트리가 많을 때 그래프로 이렇게 주어질 때가 있어요. 이러한 집합을 트리가 두 개 이상이네를 숲(Forest)이라고 한다.

자, 오늘은 트리에 대해서 알아봤습니다.