트리 (Tree)

트리는 계층적 데이터를 나타내는 노드들의 집합이다. 가장 중요한 속성은 '루트 노드를 제외한 모든 노드는 단 하나의 부모 노드를 갖는다'는 것이다.

트리는 아래의 성질을 만족해야 한다.

• 임의 노드에서 다른 노드로 가는 경로는 유일하다.
• 순환하지 않는다.(= 사이클이 없다)
• Edge를 하나 자르면 트리가 2개로 분리된다.
  • 트리 안에 또 다른 트리가 존재한다.
• Edge의 수 = Node의 수 - 1
• 비선형 자료구조

✅ 선형 자료구조? 자료들 간의 앞뒤 관계가 1:1인 자료구조로 배열, 연결 리스트, 스택, 큐 등이 있다.
✅ 비선형 자료구조? 자료들 간의 앞뒤 관계가 1:n이거나 n:n인 자료구조로 트리와 그래프가 대표적이다.

트리에서 사용되는 용어

• 노드(node) : 트리를 구성하는 기본 요소로 데이터가 담긴다.
• 간선(edge) : 노드와 노드 간 연결선
• 경로(path) : 엣지로 연결된 인접한 노드들로 이뤄진 시퀀스(sequence)
• 루트 노드(root) : 부모가 없는 최상위 노드
• 부모 노드(parent) : 자식 노드를 가진 노드로 상대적인 개념
• 자식 노드(children) : 부모 노드의 하위 노드로 상대적인 개념
• 형제 노드(siblings) : 같은 부모를 가지는 노드
• 리프 노드(leaf) : 자식 노드가 없는 노드
• 깊이(depth) : 루트에서 해당 노드까지의 간선 수
• 높이(height) : 어떤 노드에서 리프노드까지 가장 긴 간선의 수

구현 방법

연결 리스트

각 노드는 데이터와 하위 노드에 대한 포인터를 가지는 구조이다.

struct Node {
	int data;
	struct Node *left_child;
	struct Node *right_child;
}

배열

• 주로 이진 트리에서 많이 사용되는 구현 방법이다. 그 외에는 메모리 낭비가 심하여 사용하지 않는다.
• 노드 N이 있을 때, 부모-자식 관계는 다음과 같이 설정한다.
  • 부모 노드 인덱스 : N / 2
  • 왼쪽 자식 인덱스 : 2N
  • 오른쪽 자식 인덱스 : 2N + 1

트리의 종류

이진 탐색 트리 (Binary Search Tree)

✅ 이진 트리? 각 노드의 자식 노드 수가 최대 2개인 트리를 의미한다.
이진탐색(binary search)와 연결리스트(linked list)를 결합한 자료구조이다.
이진탐색의 효율적인 탐색을 유지하면서도 빈번한 자료 입력과 삭제가 가능하게끔 고안됐다.

아래의 조건을 만족해야 한다.

• 각 노드들의 키는 중복되지 않아야 한다.
• 루트 노드의 왼쪽 서브트리는 루트 노드의 키보다 작은 키값을 갖는 노드들로 구성되어 있다.
• 루트 노드의 오른쪽 서브트리는 루트 노드의 키보다 큰 키 값을 갖는 노드들로 구성되어 있다.
• 루트 노드의 서브 트리도 이진 탐색 트리여야 한다.

균형 잡혀있는 경우 삽입/삭제/탐색은 모두 $O(logN)$의 시간복잡도를 갖는다.
만약, N개 노드가 일렬로 늘어져 연결 리스트의 형태가 되는 경우 시간복잡도는 $O(N)$이다.

이진 탐색 트리의 3가지 순회 방법

• 전위 순회 : 루트 → 왼쪽 서브 트리 → 오른쪽 서브 트리
• 중위 순회 : 왼쪽 서브 트리 → 루트 → 오른쪽 서브 트리
• 후위 순회 : 왼쪽 서브 트리 → 오른쪽 서브 트리 → 루트

자가 균형 이진 탐색 트리 (Self-balancing Binary Search Tree)

트리에서 노드의 삽입 혹은 삭제가 일어날 때 균형이 맞도록 조정이 일어나 어떤 노드도 왼쪽과 오른쪽 자식의 높이 차가 1 이하인 트리를 의미한다.

✅ 균형이 맞는 트리? 모든 하위 트리의 높이 차가 1 이하인 트리를 의미한다.

AVL Tree, Red-Black Tree가 자가 균형 이진 탐색 트리에 속한다.

AVL Tree

AVL 트리는 노드를 삽입 혹은 삭제할 때 자가 균형 조정 메서드를 호출해 트리의 균형을 유지한다. → 삽입/삭제/탐색에서 평균적으로 $O(logN)$의 시간복잡도가 소요된다.

Red-Black Tree

트리에 노드를 삽입 혹은 삭제할 때 특정한 규칙을 지키도록 조정이 이루어져 트리의 균형을 유지한다. 이때 red/black 이라는 추가적인 색상 bit를 사용한다.
→ 삽입/삭제/탐색에서 평균적으로 $O(logN)$의 시간복잡도가 소요된다.

Red-Black Tree는 아래의 조건을 만족해야 한다.

• 각 노드의 색은 red 또는 black 이다.
• root 노드는 black 이다.
• 모든 리프 노드는 black이다.
• red 노드의 자식들은 모두 black 이다.(=red는 연속되어 등장하지 않는다.)
• root 노드에서 시작해 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 존재한다.

Trie

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조로 검색어 자동완성에 사용된다.

아래의 특징을 갖는다.

• 문자열 탐색 속도가 찾는 문자열의 길이 M에만 영향을 받는다.→ $O(M)$
• 각 노드들이 자식 노드에 대한 포인터를 저장해야하므로 공간 복잡도가 높을 수 있다. (메모리 측면에서 비효율적일 수 있다.)

힙 (Heap)

완전 이진 트리를 이용해 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. 부모-자식 간의 대소 관계만 성립하면 되는 느슨한 정렬상태를 유지한다.

아래의 특징을 갖는다.

• 삽입/삭제 시간 복잡도는 $O(logN)$이 소요된다.
• 배열을 사용해 구현한다. (힙은 새로운 노드를 힙의 마지막 위치에 추가한 뒤 swap 하면서 정렬하는데, 이때 배열 기반으로 구현하면 이 과정이 수월해진다.)
  • 0번째 노드는 비워둔다. (구현의 편의를 위해)
  • N번째 노드의 왼쪽 자식 인덱스: $2N$
  • N번째 노드의 오른쪽 자식 인덱스 : $2N + 1$
  • N번째 노드의 부모 인덱스 : $N/2$

B-Tree

B-Tree는 모든 리프 노드들이 같은 높이를 갖도록 하는 트리다.

아래의 속성을 갖는다.

• 노드에는 2개 이상의 데이터(key)가 들어갈 수 있고, 항상 정렬된 상태로 저장된다.
• 특정 노드의 왼쪽 서브 트리는 특정 노드의 key보다 작은 값으로, 오른쪽 서브 트리는 큰 값으로 저장된다.
• M차 B트리일 때 노드는 $M/2 ~ M$개의 자식을 가질 수 있다.
• 모든 리프 노드들이 같은 레벨에 존재한다.
• 항상 균형 트리를 유지하므로 균등한 응답 속도를 보장해 DB에서 많이 사용한다.

B+Tree

B+tree는 B-tree와 비슷한데 리프 노드에만 데이터가 있고, 리프 노드가 연결 리스트 형태를 띄어 선형 검색이 가능한 트리다.

B-tree의 경우 B-Tree는 하나의 데이터를 탐색할 때는 효율적이지만 모든 데이터를 순회할 때는 트리의 모든 노드를 방문해야 해서 비효율적이다.
반면 B+tree는 리프 노드에만 데이터가 있고 연결되어 있어, 전체를 순회할 때 선형 시간 동안 탐색이 가능하다. 그렇기 때문에 DB 인덱스로는 B+트리를 많이 사용한다.

참고

• pino님의 블로그