4 min to read

자료구조(8) - 트리

트리의 정의와 관련 용어 설명

Featured image

🔚 짧게 하는 복습

✅ 1. 단일 연결 리스트를 구현할 수 있다.

✅ 2. 이중 연결 리스트를 구현할 수 있다.

✅ 3. 단일, 이중 연결 리스트의 장단점을 각각 안다.

✅ 4. 원형 단일, 이중 연결 리스트의 장단점을 각각 안다.(과제!!)

혹시 기억이 안 난다면, 다시 돌아가자

저번 강의까지 해서 선형 자료구조를 모두 끝냈다.

비선형 자료구조의 종류는 트리, 그래프 2개밖에 없다.

이번 강의는 그 중 트리에 대해 깊게 다루어 보도록 하겠다.

트리란?

트리란 계층적인 구조를 나타내는 비선형 자료구조이다.

각각의 데이터는 노드에 저장되어있고, 노드 중 몇몇은 edge라는 간선으로 연결되어있다.

즉 트리는 노드와 간선의 집합이며 가장 중요한 점은 순환성(Cycle)이 없어야한다는 점이다.

순환성이 없다는 말은 어떤 노드에서 시작해서 다른 노드로 이동하더라도 어떤 경로를 따라가더라도 자기 자신으로 돌아오지 않는다는 뜻이다.

다시 말해, 임의의 두 노드를 선택하더라도 그들 간에 순환 경로가 존재하지 않는다.

사진을 보며 이해해보자.

위의 사진에선 그 어떤 경로에서도 자기 자신으로 돌아오지 않는다.

또한, 어떠한 두 점을 골라도, 그 두 점 사이에는 고유한 경로만 존재한다.

이를 순환성(Cycle)이 없다고 하고, 이런 노드와 간선의 집합을 우리는 트리라고 한다.

반면 아래의 사진을 보자.

만약 1, 4를 골랐다고 하고, 두 점 사이 경로를 살펴보자.

1 -> 4, 1 -> 3-> 4, 1 -> 3 -> 4 -> 1 -> 4 등 무수히 많은 경로가 존재한다.

심지어 1에서 시작했지만 1로 다시 돌아오는 경로도 존재한다.

이런 경우 우리는 “순환성(cycle)”이 있다고 하고, 이런 노드와 간선의 집합을 우리는 그래프라고한다.

아직은 그래프를 다루지 않을 것이므로, 그래프에 대한 자세한 설명은 생략하겠다.

트리의 관계에 대한 용어 설명

트리의 맨 위, 시작 노드를 root 노드라고 한다.

트리의 노드들은 위에서 아래로 계층구조를 가지게 된다.

이 관계에서 위에 있는 노드를 부모 노드(parent), 아래에 있는 노드를 자식 노드라고 한다.(child)

예를 들어, B의 자식 노드는 E, F이고 B의 부모 노드는 A이다.

또한, 같은 부모 노드를 가지는 자식 노드의 집합을 형제(sibling) 관계라고 한다.

이를 이용해서 루트 노드를 다시 정의할 수 있다. 루트 노드는 부모 노드가 없이 자식 노드만 가지는 노드이다.

이의 반대 관계는 리프 노드(leaf node)인데, 리프 노드는 반대로 부모 노드만 가지고, 자식 노드가 없는 노드이다.

어떤 노드의 조상(ancestor) 관계은 그 노드로부터 루트 노드까지의 경로상에 있는 모든 노드을 포함한다.

반대로, 후손(descendant) 관계은 특정 노드로부터 리프 노드까지의 경로상에 있는 모든 노드을 나타낸다.

트리의 레벨, 높이, 깊이란?

이번엔 관계의 관점이 아니라, 각 노드의 위치의 관점에서 보자.

level(레벨)은 특정 노드가 루트에서 얼마나 떨어져 있는지를 나타낸다.

레벨은 루트 노드에서 출발하여 해당 노드에 도달하는 데 필요한 단계의 수이다.

일반적으로 루트 노드의 레벨은 0이며, 아래로 내려갈수록 레벨이 1씩 증가합니다.

또한, 레벨은 깊이(depth)라는 용어로 불리기도 한다.

예를 들어, 루트 노드인 A의 깊이는 0, B는 1, E는 2, I는 3이다.

반면에 어떤 노드의 높이는 해당 노드에서부터 가장 깊이에 있는 리프 노드까지의 경로상에 있는 레벨의 수를 의미한다.

직관과는 반대로, 깊이는 위를 향하는 개념이고 높이는 아래를 향하는 개념이다. (하지만 대부분 문맥에서 높이와 깊이를 사실 혼용한다.)

예를 들어, 루트 노드인 A의 높이는 3, C의 높이는 2, H의 높이는 1, J의 높이는 0이다.

그 중 루트 노드의 높이는 트리의 높이라고도 한다.

즉, 위의 그림에서 트리의 높이는 3이다.

트리의 구조

구조적 관점에서 하나의 큰 트리는 수많은 작은 서브 트리로 구성되어있다.

예를 들어, A를 root로 보게 되면 깊이 3의 큰 트리로 볼 수 있다.

그런데 B, C, D를 루트로 본다면 B, C, D도 각각의 트리로 볼 수 있다.(트리는 하나의 노드 이상이기에, 하나의 노드도 트리로 볼 수 있다.)

이때 원래 트리의 루트인 A 말고, B, C, D를 루트로 하는 각각의 트리를 서브 트리라고 한다.

그리고 이 관점에서 본다면 B와 D 역시, 각각 E, F, G, H를 루트로 하는 서브 트리로 이루어져 있다.

이러한 성질이 중요한 이유는, 하나의 큰 트리를 일반성을 잃지 않고, 각각의 서브 트리로 다루기 쉽기 때문이다.

더 쉽게 말하면, 여러 가지 함수를 만들 필요 없이, 재귀 함수(자기 자신을 호출하는 함수)로 다룰 수 있다는 장점이 있다.

트리의 분류1 - 루트의 유무

트리라는 자료구조는 루트 노드가 있냐 없냐에 따라, rooted tree와 unrooted tree로 나눌 수 있다.

사실 우리가 다룰 대부분의 트리는 루트가 있는 rooted tree이기 때문에, 그렇게 중요한 개념은 아니다.

(unrooted tree는 연결성만을 강조하는 분자 구조, 진화 트리 등에 사용된다.)

트리의 분류2 - k-ary tree

k-ary tree란 모든 서브 트리가 자식 노드의 개수가 최대 k개인 트리를 말한다.

이진 트리(binary tree)는 대표적인 k-ary 트리로, 어떤 서브 트리를 잡아도 자식 노드를 최대 2개까지만 가지는 트리이다.

이진 트리(binary tree)는 굉장히 다양하게 응용되기 때문에 익숙해질 필요가 있다.

여기서 중요한 점은, 모든 서브 트리가 자식 노드를 2개씩 가지는 것이 아니다., 최대 2개까지 가질 수 있는 것이다.

즉, 얘네 모두 이진 트리이다.

이진 트리의 더 자세한 내용은 다음 시간에 자세하게 다루어 보겠다.

📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

✅ 1. 트리의 정의를 안다.

✅ 2. 트리의 용어들을 안다.

✅ 3. k-ary tree, 그 중 이진 트리에 대해서 정확하게 안다.

⚠️ 트리의 용어는 많고 복잡하니, 잘 외우자.

💣 과제,

  1. 위의 트리 중 아무 그림이나 골라서 구현해보자. (난이도 中)

  2. 하나의 트리를 골라서, root/부모/자식/선조/후손, height/depth, 서브 트리 구조를 분석해보자(난이도 中)