[자료구조] 트리 (Tree)

목차

트리(Tree)의 개념

 

트리는 노드와 간선으로 이루어진 계층적 관계를 표현하는 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.

 

트리는 다음과 같은 특징들이 있다.

 

1. 트리는 하나의 루트 노드를 갖는다.

2. 루트 노드는 0개 이상의 자식 노드를 갖는다.

3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다.

4. 트리는 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다.

5. N개의 노드를 갖는 트리는 항상 N - 1개의 간선을 갖는다.

6. 모든 자식 노드는 한 개의 부모 노드만을 갖는다.

7. 모든 노드는 서로 연결되어 있다.

8. 임의의 노드에서 다른 노드로 가는 경로(path)는 단 1개만 존재한다

 

추가로, 트리에는 사이클(Cycle)이 존재할 수 없다. 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있는 것을 뜻한다. 따라서, 트리는 사이클이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다. 당연하게 트리의 노드는 self-loop이 있어서는 안 된다. 즉, 노드 자기 자신과 연결된 간선이 존재해서는 안 된다.

 

 

이제부터 트리 유사한 그림들을 보면서 트리가 맞는지 아닌지를 살펴보겠다. 

 

트리 1

 

트리 1은 트리가 아니다. 사이클이 있기 때문이다. D에서 시작해 B, C, E를 거치면 다시 D로 올 수 있기 때문에 트리가 아니다.

 

트리 2

트리 2도 트리가 아니다. 사이클은 없지만 1에서 4로 가는 경로가 유일하지 않기 때문이다. 즉, 1 → 2 → 4로도 4로 가고 1 → 3 → 4를 통해서도 4로 갈 수 있기 때문에 트리가 아니다.

 

트리 3

트리 3도 트리가 아니다. 모든 노드들이 연결되어 있는 상태가 아니기 때문에 트리가 아니다.

 

 

 

트리 관련 용어

트리의 구조

루트 노드(root node) : 부모가 없는 노드로 트리는 단 하나의 루트 노드를 가진다. 부모 노드라고도 불린다. (ex : A)

단말 노드(leaf node) : 자식이 없는 노드로 terminal 노드라고도 부른다. (ex : C, D, E)

내부 노드(internal node) : 단말 노드가 아닌 노드. 즉, 자식이 있는 노드 (ex : A, B)

간선(edge) : 노드를 연결하는 선

형제(sibling) : 같은 부모 노드를 갖는 노드들 (ex : D-E, B-C)

노드의 깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수(ex : D의 depth : 2)

노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 ( ex : level 1- {B, C} )

노드의 차수(degree) : 자식 노드의 개수 (ex : B의 degree - 2, C의 degree - 0)

트리의 차수(degree of tree) : 트리의 최대 차수 (ex : 위 트리의 차수는 2이다)

경로(path) : 간선으로 연결된, 즉 인접한 노드들로 이뤄진 시퀀스(sequence)를 뜻한다.

경로 길이(path length) : 경로에 속한 간선의 수 (ex : A → B → D의 경로 길이는 2가 된다)

 

 

 

트리의 종류

이제 다양한 트리의 그림과 특징들을 알아보겠다.

 

 

1. 이진트리 (Binary Tree)

 

이진 트리 (Binaryt Tree)

 

특징:

이진트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 뜻한다. 즉, 각 노드는 자식이 없거나 한 개 이거나 두 개만을 갖는 것이다. 

 

 

2. 완전 이진트리 (Complete Binary Tree)

 

완전 이진 트리

 

특징:

• 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
• 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
• 마지막 레벨 h에서 1~2h-1 개의 노드를 가질 수 있다.
• 완전 이진트리는 배열을 사용해 효율적으로 표현 가능하다.

 

3. 전 이진트리 (Full Binary Tree)

 

전 이진 트리

 

특징:

전 이진트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

 

 

4. 포화 이진트리 (Perfect Binary Tree)

 

포화 이진 트리

 

특징:

• 포화 이진트리는 모든 레벨이 (마지막 레벨을 제외하고) 노드로 꽉 차 있는 트리를 뜻한다. 
• 전 이진트리의 성질도 만족해야 한다. 즉 모든 노드가 0개 혹은 2개의 자식 노드를 갖는다.
• 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.
• k는 트리의 높이일 때, 트리의 노드 개수가 정확히 2^(k-1) 개여야 한다. 

 

5. 이진 탐색 트리 (Binary Search Tree)

 

이진 탐색 트리는 효율적인 탐색을 위해 이용하는 이진트리이다. 

 

특징:

• 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
• 부모의 키가 왼쪽 자식 노드의 키보다 크다.
• 부모의 키가 오른쪽 자식 노드의 키보다 작다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

6. 균형 이진트리 (Balanced Binary Tree)

 

 

특징:

균형 이진트리는 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리이다. 왼쪽 트리는 균형 이진트리가 맞다. 하지만 오른쪽 트리는 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 2가 나기 때문이다.

 

7. 편향 이진트리 (Skewed Binary Tree)

 

 

특징:

편향 이진트리란 모든 노드가 부모의 왼쪽 자식이기 때문에 왼편으로 편향되어 있거나 반대로 모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로 편향되어 있어야 한다