이진 트리, 힙
원래는 트리 자체로도 설명글을 적으려 했었는데 다른 자료구조와 마찬가지로 기본은 생략하려 한다.
여기서는 트리 중 가장 자주 사용되는 이진 트리와 이를 활용한 힙을 설명한다.
이진 트리
이진 트리는 트리 중에서 차수가 2인 트리를 말한다.
즉 모든 노드는 자식 노드를 최대 2개까지만 가질 수 있다.
이진 트리의 특성
높이 n에서의최대 노드 개수는 2ⁿ개높이 n 이진 트리가 가질 수 있는최소 노드는 n+1개,최대 노드는 2^(n+1)-1개
이진 트리의 종류
1. 포화 이진 트리
위의 사진처럼 모든 레벨에 노드가 포화로 가득 차 있는 이진 트리를 뜻한다.
2. 완전 이진 트리
포화 이진 트리에서 노드가 빠지되, 1번부터 n번까지 중간에 빈 자리가 없는 이진 트리이다.
즉 포화 이진 트리에서 뒤쪽이 빠진 형태이며, 중간 노드가 빠지면 완전 이진 트리가 아니다.
3. 편향 이진 트리
최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 한쪽 방향의 자식 노드만을 가진 이진 트리이다.
노드 번호의 성질
현재 노드 번호가 i일 때
- 부모 노드 :
i/2 - 자식 노드 :
2i,2i+1 - 높이 n의 시작 노드번호 :
2ⁿ
수식 트리
수식을 이진 트리를 이용하여 표현한 것으로 아래의 특징이 있다.
- 루트, 가지 노드 : 연산자
- 단말 노드 : 피연산자 (숫자)
이진 트리의 탐색
1. BFS (너비 우선 탐색)
너비 우선으로 탐색하는 방법이다. 우선 루트에서 자식 노드들을 먼저 방문한 후,
방문했던 자식 노드를 기준으로 다시 해당 노드의 자식들을 차례로 방문한다.
-> 인접한 노드들 먼저 탐색 후, 다시 탐색해야하므로 큐를 활용한다.
public void bfs() {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 루트 먼저 탐색
while(!queue.isEmpty()) {
int current = queue.poll(); // 큐에서 하나 꺼낸다. (방문)
System.out.println(nodes[current]);
if(current*2 <= lastIndex) queue.offer(current*2); // 왼쪽 자식노드
if(current*2+1 <= lastIndex) queue.offer(current*2+1); // 오른쪽 자식노드
}
}
2. DFS (깊이 우선 탐색)
깊이 우선으로 루트에서 한 방향으로 갈 수 있는 끝까지 탐색한 후,
더 이상 갈 곳이 없어지면 마지막 갈림길로 돌아와 다른 방향으로 탐색한다.
-> 마지막 갈림길로 돌아와야 하므로 재귀적으로 구현하거나 스택을 활용한다.
public void dfs(int current) {
if (current > lastIndex)
return;
System.out.println(nodes[current]);
dfs(current*2);
dfs(current*2+1);
}
힙
힙은 완전 이진 트리를 활용한 자료구조로 키 값이 가장 크거나 가장 작은 노드를 찾기 위해 사용한다.
그렇기에 조건에 따라 루트노드가 최대값 혹은 최소값이 된다.
힙의 삽입
- 우선
완전 이진 트리의 다음 자리에 원소를 삽입한다. 부모 노드와 비교하면서제 위치가 아니면교체를 반복한다.
최악의 경우 루트까지 올라가야 하므로, 트리의 높이만큼 반복될 수 있다.
-> 노드 개수가 n개일 경우 1번의 삽입 시간은 대략 log₂n
-> 전체 n개를 삽입해야 하므로 O(nlog₂n) 시간복잡도를 가진다.
힙의 삭제
루트 노드를 제거한다.- 완전 이진 트리를 만들기 위해
마지막 노드를 루트로 이동시킨다. 자식 노드와 비교하며제 위치까지교체를 반복한다.
삭제도 마찬가지로 최악의 경우 트리의 높이만큼 반복될 수 있으므로
동일한 시간 복잡도 O(nlog₂n)을 가진다.
우선순위 큐
우선순위 큐를 구현하는 가장 효율적이고 대중적인 방법은 힙을 사용하는 것이다.
그렇기에 힙을 구현해야 한다면 보통 우선순위 큐를 사용한다.
시간복잡도 정리
- 최대값, 최소값 :
O(1) - 노드1개 삽입, 삭제 :
O(log₂n) - 전체 삽입, 삭제 :
O(nlog₂n)
힙 정렬
모든 값을 힙에 삽입한 후, 순차적으로 값을 하나씩 꺼내 정렬하면 된다.
생각하는 것과 동일하게 O(nlog₂n) 시간복잡도를 가진다.
여기서 주의할 점은 하나씩 꺼낸 값들이 정렬된 값이라는 점이고,
힙에 삽입한 상태에서는 루트 노드를 제외한 값들은 정렬되어 있지 않다는 점이다.
중간 값 구하기
힙을 활용한다면 최대값, 최소값은 구할수 있겠으나, 중간값은 구할 수 없다.
이 때는 힙 2개를 활용하여 중간값을 구하는 방법이 있다.
최대 힙과최소 힙을 각각 준비한다.최대 힙의 크기가최소 힙의 크기와 같거나 1개 많도록유지한다.최대 힙의 루트 노드는최소 힙의 루트 노드보다 작거나 같아야한다.- 3번의 조건이 만족하지 않는다면
두 힙의 루트 노드를 swap한다.
즉. 최대 힙의 루트 노드값이 중간값이 되는 것이다.
중간값을 기준으로 작은 값은 최대힙, 큰 값은 최소 힙에 넣으면서 균형을 유지하는 방식이다.
