트리(Tree)란?
트리(Tree) 자료구조는 계층적인 구조를 표현할 때 매우 유용한 자료구조이다. 트리(Tree)는 그래프(Graph)의 한 종류로, 노드(Node)와 간선(Edge)을 이용해 계층적인 구조를 표현하는 자료구조이다. 트리의 구조는 루트(Root) 노드와 서브트리(Subtree)로 나누어진다.
루트 노드는 트리의 최상위 노드를 의미하며, 서브트리는 특정 노드를 루트로 하는 하위 트리를 말한다. 간선은 노드 간의 관계를 나타내며, 부모(Parent) 노드와 자식(Child) 노드로 구분된다.
트리의 특징
- 루트 노드를 제외한 모든 노드는 유일한 부모 노드를 가진다.
- 각 노드는 0개 이상의 자식 노드를 가질 수 있다.
- 순환하지 않는 구조이다.
트리의 구성 요소 및 용어
노드(Node)
노드(Node)는 트리를 구성하는 가장 기본적인 단위이다. 각 노드는 데이터를 저장하는 역할을 하며, 이 데이터는 해당 노드의 특성을 나타내는 정보로 사용된다. 예를 들어, 이진 검색 트리(Binary Search Tree)에서는 각 노드가 정렬된 데이터를 저장하며, AVL 트리(AVL Tree)에서는 노드의 높이 정보를 저장한다.
간선(Edge)
간선(Edge)은 노드 간의 관계를 나타내며, 부모 노드와 자식 노드를 연결한다. 이 간선은 방향성을 가지며, 자식 노드에서 부모 노드로는 간선이 존재하지 않는다.
루트(Root) 노드
루트(Root) 노드는 트리의 최상위 노드를 의미한다. 모든 노드는 루트 노드의 서브트리에 속한다. 예를 들어, 위의 이진 트리에서 A는 루트 노드이다.
부모(Parent) 노드
어떤 노드의 상위 레벨에 있는 노드를 부모(Parent) 노드라고 한다. 예를 들어, 위의 이진 트리에서 F 노드의 부모 노드는 B 노드이다.
자식(Child) 노드
어떤 노드의 하위 레벨에 있는 노드를 자식(Child) 노드라고 한다. 예를 들어, 위의 이진 트리에서 A 노드의 자식 노드는 B, C, D 노드이다.
형제(Sibling) 노드
부모 노드로부터 같은 레벨에 있는 노드들을 형제(Sibling) 노드라고 한다. 예를 들어, 위의 이진 트리에서 E 노드와 F 노드는 서로 형제 노드이다.
리프(Leaf) 노드
자식 노드를 갖지 않는 노드를 리프(Leaf) 노드라고 한다. 예를 들어, 위의 이진 트리에서 E, K, L 노드가 리프 노드이다.
차수(Degree)
차수(Degree) 한 노드가 가진 자식(서브트리)의 수이다. 위의 이진 트리에서 A 노드의 차수는 3이다.
레벨(Level)
루트에서 자신에게까지 걸리는 거리를 레벨(Level)이라고 한다. 루트를 레벨0 혹은 1로 시작해서 아래 계층으로 갈 수록 레벨이 커진다.
높이(Height)
높이는 깊이(Depth)라고도 부른다. 특정 노드의 높이는 루트 노드에서 해당 노드까지의 거리를 높이라고 부른다. 위 트리의 F 노드의 높이는 2이다.
트리의 높이는 루트 노드에서 가장 높은 레벨의 노드까지이다. 위 트리의 높이는 3이다.
이진 트리(Binary Tree)
여러 종류의 트리가 존재하지만 가장 많이 사용되는 이진 트리(Binary Tree)에 대해 알아보자. 이진 트리는 모든 노드의 차수가 2 이하인 트리이다. 이진 트리의 형태에 따라 부르는 명칭이 존재한다.
이진 트리의 형태
Full Binary Tree
- 모든 노드가 0개 혹은 2개의 children 을 가지고 있을 때 “Binary Tree 는 full” 이라고 한다.
- 같은 의미 다른 말로, “Full Binary Tree 는 leaf 노드들을 제외한 모든 노드들이 2개의 children 을 가지는 Binary Tree” 라고도 할 수 있다.
Perfect Binary Tree
- 모든 internal node 가 두개의 children 을 가지고 있고, 모든 leaf 노드가 같은 level 에 있으면 Perfect Binary Tree 라고 한다.
- Height 가 h 인 Perfect Binary Tree 는 2h - 1 개의 노드를 가진다.
Degenerate (or Pathological) Tree
- 모든 internal node 가 하나의 child 만을 가질 때 Degenerate (or Pathological) Tree 라고 한다.
- Linked List 성능과 동일하다.
Complete Binary Tree
- 마지막 level 을 제외한 나머지 level 에 node 들이 가득 차있고, 마지막 level 에서 node 는 가장 왼쪽 부터 채워지는 형태가 Complete Binary Tree 이다.
- Complete Binary Tree 구조를 그대로 사용하여 Binary Heap 이라는 데이터 구조를 만들 수 있고, 이것이 Heap 이다.
- Complete Binary Tree 구현에는 Array 를 사용하는 것이 일반적이다.
이진 트리의 순회
깊이 우선 순회(depth first traversal)
- 전위 우선 순회(pre-order traversal) : 노드 > 왼쪽 서브트리 > 오른쪽 서브트리 순으로 순회
- 중위 우선 순회(in-order traversal) : 왼쪽 서브트리 > 노드 > 오른쪽 서브트리 순으로 순회
- 후위 우선 순회(post-order traversal) : 왼쪽 서브트리 > 오른쪽 서브트리 > 노드 순으로 순회
넖이 우선 순회
- 수준(level)이 낮은 노드를 우선으로 방문
- 같은 수준의 노드들 사이에서는, 왼쪽 자식 노드를 오른쪽 자식 노드보다 먼저 방문
이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리(Binary Search Tree)는 이진 트리의 일종으로 모든 노드에 대해서, 왼쪽 서브트리에 있는 모든 데이터는 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 모든 데이터는 현재 노드의 값보다 큰 성질을 만족하는 트리이다. 또한 모든 노드는 중복된 값을 가지지 않는다. 이진 탐색 트리는 데이터를 정렬된 상태로 저장하고 효율적인 탐색이 가능하다.
이진 탐색 트리의 연산
insert(): 트리에 주어진 데이터 원소를 추가remove(): 특정 원소를 트리로부터 삭제lookup(): 특정 원소를 검색 (탐색)inorder(): 키의 순서대로 데이터 원소들을 나열min(), max(): 최소 키, 최대 키를 가지는 원소를 각각 탐색
이진 탐색 트리 생성 예시
다음은 28, 21, 15, 14, 32, 25, 18, 11, 30, 19 순서로 이진 탐색 트리에 원소를 추가하는 예시이다. 앞서 말한 이진 탐색 트리의 특징 한 눈에 볼 수 있다.
이진 탐색 트리 탐색 예시
아래는 이진 탐색 트리와 정렬된 배열에서 같은 값을 찾는 예시이다. 정렬된 배열에서 순차적으로 찾을 때의 시간 복잡도는 O(n)이고, 이진 탐색 트리에서의 시간 복잡도는 O(logn)이다. 따라서 이진 탐색 트리에서는 효율적인 탐색이 가능하다.
힙(heap)
힙(Heap)이란 완전 이진 트리의 한 종류로 최댓값이나 최솟값을 빠르게 찾아내기 위해 고안된 자료구조이다. 힙의 각 노드는 키(Key)라는 값으로 구성되며 부모노드와 자식노드와의 관계는 다음이 성립한다.
A가 부모노드, B가 자식노드일 경우 A의 키 값과 B의 키 값에는 대소관계가 주어진다.
힙은 자식 노드에 따라 여러가지 종류로 구분되지만 대부분 자식 노드 2개를 갖는 이진 힙(Binary Heap)을 사용하며 우선순위 큐(Priority Queue)의 구현체로 이용되거나 힙 정렬(Heap Sort)에 이용된다. 우선순위 큐가 사용되는 알고리즘으로는 최단경로를 찾는 다익스트라(Dijkstra) 알고리즘이 존재한다.
힙의 종류
최대 힙(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) >= key(자식 노드)
최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) <= key(자식 노드)
힙의 구현
- 힙을 저장하는 표준적인 자료구조는 배열이다.
- 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
- 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만 일어난다.
- 힙에서 부모 노드와 자식 노드의 관계는 다음과 같다.
노드 번호 m을 기준으로
왼쪽 자식의 번호 : 2 * m
오른쪽 자식의 번호 : 2 * m + 1
부모 노드의 번호 : m // 2
힙의 동작 방식
원소 삽입
힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입한다. 이후 새로운 노드를 부모 노드들과 교환함으로써 힙의 성질을 만족시킨다. 아래는 최대 힙에 새로운 원소 8을 삽입했을 때, 동작하는 방식의 예이다.
원소 삭제
힙에서 원소를 삭제하면 루트 노드의 원소가 삭제된다. 이후에 루트 노드를 새로 채우며 힙의 성질을 만족시키기 위해 힙을 재구성한다. 아래는 최대 힙에서 최대값을 삭제했을 때, 동작하는 방식의 예이다.
