[알고리즘] 트리(Tree)

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

 

 

1. 트리(Tree)

 트리는 계층 구조를 표현하기에 적합한 자료구조로, 노드(Node)와 간선(Edge)으로 이루어져 있습니다. 시각적으로 표현해보면 이름처럼 나무의 뿌리가 밑으로 뻗어나가는 것과 비슷한 구조를 가지게됩니다. 구조상 그래프의 일종으로 볼 수도 있으나, 계층 구조를 표현하는 만큼 순환하는 부분이 있으면 안됩니다.

 

그림 1. 트리 관련 용어 정리

 또한 트리는 구조상 재귀적인 특성을 가집니다. 즉, 큰 트리에서 일부를 잘라내도 여전히 트리의 구조를 가집니다. 예를 들어 그림 1에서 B, D, E의 부분을 잘라내면 여전히 노드가 3개인 트리가 됩니다. 이렇게 잘라낸 트리의 일부분을 서브트리(sub tree)라고 부릅니다. 

 

 

2. 이진 트리(Binary Tree) / 이진 검색 트리(Bianry Search Tree)

 트리 중 모든 노드가 최대 2개의 자식 노드를 가지는 트리를 이진 트리(Binary Tree)라 합니다. 그림 1의 트리도 A, B, C가 각각 2개의 자식 노드를 가지므로 이진 트리에 속합니다. 또한 이진 트리 중에서도 왼쪽 자식은 부모보다 작은 값을 가지고, 오른쪽 자식은 부모보다 큰 값을 가진다는 규칙을 지키는 트리를 이진 검색 트리(Binary Search Tree)라고 합니다.

 

그림 2. 이진 검색 트리

 

 이진 검색 트리는 구조상 특정 값의 검색이 빠르다는 장점이 있습니다. 루트부터 시작해서 찾는 값이 현재 노드 값보다 작다면 왼쪽, 크다면 오른쪽으로 이동하면서 찾아가면 되므로 모든 원소를 확인하며 찾는 경우(O(n))보다 빠르게 동작합니다. 그림 2와 같이 모든 노드가 2개의 자식을 가지는 이상적인 형태라면 O(log(n))까지 줄어들 수 있습니다. 다만, 이진 검색 트리에는 다음과 같은 취약점이 있습니다. 

 

그림 3. 이진 검색 트리의 안좋은 예시

 그림 3은 이진 검색 트리의 극단적으로 나쁜 예시입니다. 루트보다 낮은 값만 계속해서 들어올 경우 이렇게 트리가 심하게 편향된 구조가 되고, 이 경우 검색 효율이 O(n)에 가까워집니다. 따라서 검색 효율을 유지하려면 트리가 편향되지 않도록 재배치하는 알고리즘이 필요하고, 이를 적용한 트리로는 AVL, Red-Black 트리 등이 있습니다.

(AVL, Red-Black 트리 등은 개별로 포스팅해야 할 정도로 복잡하며, 저도 아직 확실히 이해하지 못한 관계로 추후에 다루도록 하겠습니다.)

 

 

3. 힙 트리(Heap Tree)

 트리 중 다음과 같은 조건을 만족하는 트리를 힙 트리(Heap Tree)라고 합니다.

 

- 1) 부모 노드의 값이 항상 자식 노드의 값보다 큼
- 2) 마지막 층(layer)을 제외한 모든 층에 노드가 꽉 차있어야 함
- 3) 마지막 층에 노드가 있을 때는 항상 왼쪽부터 순서대로 채움

 

또한 상기 조건들에 의해 다음과 같은 특징을 가집니다.

 

- 루트 노드가 가장 큰 값을 가짐(by 1번 조건)

- 노드의 개수에 따라 트리의 구조가 고정된 형태로 나타남(by 2, 3번 조건)

 

그림 4. 힙 트리(Heap Tree)

 

 

 위와 같은 조건을 만족하여 힙 트리에 데이터를 추가하려면 다음과 같은 과정을 거치게 됩니다.

 

- 1) 트리의 마지막 노드 다음 위치에 데이터 추가

- 2) 새로 추가한 노드와 부모 노드를 비교하여 부모보다 값이 더 크다면 교환

- 3) 2번 과정을 값이 더 큰 부모를 만나거나 루트에 도달할 때까지 반복

 

 상기 과정을 통해 데이터를 추가하면 힙 트리의 구조를 유지하게 됩니다. 다음은 그림 4의 힙 트리에 새로운 값을 추가하는 예시입니다.

 

그림 5. 힙 트리에 데이터 추가

 

 또한 힙 트리에서 가장 큰 값, 즉 루트 노드를 제거하는 경우 다음과 같은 순서로 진행합니다.

 

- 1) 루트 노드 제거

- 2) 마지막 노드를 루트 노드로 이동(힙 트리 구조 유지)

- 3) 루트 노드와 자식 노드를 비교하여 자식노드의 값이 더 크다면 교환(더 큰 값을 가진 자식쪽으로)

- 4) 3번 과정을 값이 더 큰 자식이 없거나 잎(leaf) 노드에 도달할 때까지 반복

 

 다음은 그림 4의 힙 트리에서 루트 노드를 제거하는 예시입니다. 마찬가지로 루트 제거 후에도 힙 트리의 구조를 유지함을 알 수 있습니다.

 

그림 6. 힙 트리에서 루트 노드 제거

 

 

 루트 노드를 제거하는 경우가 중요한 이유는 루트 노드가 가장 큰 값을 가지는 힙 트리의 특성상 우선순위 큐(Priority Queue)에 사용되기 때문입니다. 우선순위 큐는 길찾기 알고리즘 등에서 효율적으로 쓰이는 중요한 자료구조로, 별도의 포스팅에서 다루도록 하겠습니다.