트리 기초(의미, 구현, 용어, 종류)

지난 게시물에서 그래프에 대해 공부했습니다. 

트리는 그래프의 특수한 형태입니다. 

정말정말 다양하게 활용될 수 있는 재미있는 자료구조입니다.

 

트리란?

사이클이 없는 연결 그래프를 트리라고 부릅니다. 

가중치와 방향 여부는 별로 중요하지 않습니다. 

무슨 말인지 모르겠다면 지난 게시물을 참고하세요.

 

해당 형태의 그래프가 나무를 뒤집어 놓은 모양과 비슷해 트리라고 이름이 붙었다고 합니다.

 

트리의 용어

기본적으로는 그래프의 용어를 그대로 사용합니다. 

보통 '정점' 대신 '노드'라는 용어를 많이 쓰는 것 같습니다.

• 루트 노드 : 트리의 맨 꼭대기에 위치할 정점을 이야기합니다. 임의로 설정할 수 있습니다.
• 부모/자식 노드 : 이웃한 두 정점 중 루트 노드와 더 가까운 정점이 부모, 다른 정점이 자식이 됩니다. 
• 형제 노드 : 부모가 같은 노드들끼리 형제 관계라고 이야기합니다. 
• 서브 트리 : 부모 노드 입장에서 자식 노드를 보면 자식 노드를 루트로 하는 또 다른 트리를 발견할 수 있습니다. 이러한 트리를 서브 트리라고 합니다. 즉 트리는 재귀적인 구조로 이루어져 있습니다.
• 리프 노드 : 자식이 없는 정점들을 의미합니다. 
• 깊이 : 트리의 루트 노드와 가장 먼 리프 노드 사이의 거리입니다. 
• 이진 트리 : 모든 노드가 2개 이하의 자식 노드만을 가지는 트리입니다. 모든 노드가 k개 이하의 자식 노드만을 가진다면 k진 트리라고 부릅니다.
• 완전 이진 트리 : 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 빈 칸 없이 채워져 있는 이진 트리를 의미합니다. 배열로 구현할 수 있습니다.

트리의 구현

일반적으로는 그래프의 구현처럼 인접 리스트로 구현하며, 상황에 따라 부모 노드를 저장하는 배열을 만들기도 합니다. 

 

일반적인 트리와 달리, 완전 이진 트리는 배열을 이용하여 구현할 수 있습니다. 

완전 이진 트리는 위와 같이 위에서부터, 왼쪽에서부터 노드가 추가되어 중간에 빈 칸이 없는 트리입니다. 노드에 그림처럼 순서대로 1부터 숫자를 부여해 줍시다. 이렇게 숫자를 부여하면 n번 노드의 부모 노드는 (n / 2)번 노드이며, 자식 노드는 (n * 2), (n * 2 + 1)번 노드라는 사실을 관찰할 수 있습니다. 즉, 정점 번호를 배열의 인덱스로 생각하고 데이터를 저장한다면 인덱스를 통해 부모/자식 노드에 접근할 수 있습니다. 

일반 이진 트리도 이러한 방식으로 구현할 수 있지만, 공간의 낭비가 심해 일반적으로는 인접리스트 방식으로 구현합니다.

 

포인터를 이용하여 구현하기도 합니다. 

struct Node{
  int data;
  Node *left, *right;
}

위와 같은 노드 구조체를 만들고 left와 right에 자식 노드의 주소를 저장하는 방식입니다. 

이러한 방식은 주로 트리를 동적으로 할당하여 생성할 때 사용됩니다. 

 

다양한 트리들

트리는 수행하는 기능에 따라 여러 가지로 구분됩니다. 

• 힙 트리 : 부모 노드의 값과 자식 노드의 값이 항상 특정한 관계를 유지하는 트리입니다. $O(logN)$만에 데이터를 삽입/삭제할 수 있습니다. 
• 유니온 파인드 트리(분리 집합) : 데이터를 여러 개의 집합으로 분류하고 싶을 때 사용합니다. 두 집합을 합치고, 특정 원소가 속해 있는 집합을 찾는 연산을 $O(1)$에 가까운 시간복잡도로 수행할 수 있습니다. 
• 세그먼트 트리 : 구간에 대한 연산을 $O(logN)$만에 수행할 수 있는 자료구조입니다. 

이 외에도 트리를 이용한 다양한 자료구조들이 존재합니다.