Tree
정의
단방향 그래프의 한 구조, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
구조
- Node : 트리 구조를 이루는 개별 데이터
- Leaf : 트리 구조의 끝 지점, 자식 노드가 없는 노드
Binary Search Tree
정의
자식 노드가 최대 두개인 노드들로 구성된 트리, 효율적인 탐색에 용이
모든 왼쪽 자식의 값은 루트나 부모보다 작고, 모든 오른쪽 자식의 값은 루트나 부모보다 크다.
종류
| 종류 | 설명 |
|---|---|
| 정 이진 트리 | 각 노드가 0개 혹은 2개의 자식노드를 가짐 |
| 포화 이진 트리 | 정 이진트리이면서 완전 이진 트리일 경우, 모든 리프 노드의 레벨이 같고 모든 레벨이 가득 차 있는 트리 |
| 완전 이진 트리 | 마지막 레벨을 제외한 모든 노드가 차 있고 마지막 레벨의 노드는 전부 차 있지 않고 왼쪽만 존재하는 트리 |
Heap Tree
정의
우선 순위에 따라 빠르게 자료를 검색할 수 있는 트리
구조
- 느슨한 정렬 구조
- 부모 노드의 값은 자식 노드의 값보다 크거나 작게 정렬되어 있지만 자식 노드끼리는 정렬하지 않는다.
특징
1. 완전 이진 트리
완전 이진 트리로 구성되어 있으며, 단순히 최소값, 최대값을 찾기 위해 완전 이진트리를 구성할 필요는 없지만 삽입/삭제 성능을 위해 완전 이진 트리로 구현하게 된다.
2. 중복된 값 저장
중복된 값을 저장할 수 있다. 이는 최대값/최소값을 찾아내기 위한 구조이기 때문이다.
3. 최대 힙/최소 힙
- 루트 노드에 가장 큰 값이 위치하고 자식 노드로 내려갈수록 작은 값을 가지게 되면 최대힙이 된다.
- 루트 노드에 가장 작은 값이 위치하고 자식 노드로 내려갈수록 큰 값을 가지게 되면 최소힙이 된다.
4. 구현
PriorityQueue를 이용해서 Max/Min Heap Tree를 구현할 수 있다.
- 최대힙 구현
import java.util.*;
public class MaxHeap {
public static void main(String[] args) {
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>(
Collections.reverseOrder()); // reverse를 통한 우선순위 변경
pq.add(1);
pq.add(5);
pq.add(6);
pq.add(8);
pq.add(10);
pq.add(11);
Iterator<Integer> itr = pq.iterator();
while (itr.hasNext())
System.out.println(itr.next());
}
}
- 최소힙 구현
import java.util.*;
public class MinHeap {
public static void main(String[] args) {
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>();
pq.add(1);
pq.add(5);
pq.add(6);
pq.add(8);
pq.add(10);
pq.add(11);
Iterator<Integer> itr = pq.iterator();
while (itr.hasNext())
System.out.println(itr.next());
}
}Heap Tree 데이터 처리 방식
최대값과 최소값을 찾기 위해 걸리는 시간 복잡도는 O(1)이다. root 노드에 최대힙의 경우 최대값이, 최소힙의 경우 최소값이 위치하기 때문이다.
데이터 삽입과 삭제는 조금 복잡하기 때문에 좀 더 알아보기로 한다.
1. 데이터 삽입
[최대힙의 데이터 삽입]
- 가장 마지막 노드에 새로운 값을 저장
- 삽입된 노드의 값과 부모 노드의 값을 비교
- 최대 힙일 경우, 부모의 값이 더 크다면 부모의 값과 위치를 서로 변경
최소힙일 경우, 부모의 값이 더 작다면 부모의 값과 위치를 서로 변경 - 더 이상 위치가 바뀌지 않을 때까지 1~3까지의 과정을 반복
2. 데이터 삭제
[최대힙의 데이터 삭제]
- 루트 노드의 값을 제거
- 루트 자리에 마지막 노드의 값을 삽입
- 올라간 노드의 값과 그 자식 노드들의 값과 비교
- 부모보다 더 큰 자식이 있다면(최대 힙) 해당 자식의 값과 서로 교환(만약 두 자식의 값이 모두 부모보다 작다면, 두 값 중 큰 값과 위치를 변경)
부모보다 더 작은 자식이 있다면(최소 힙) 해당 자식의 값과 서로 교환(만약 두 자식의 값이 모두 부모보다 크다면, 두 값 중 작은 값과 위치를 변경) - 더 이상 큰 값이 없을 때까지 반복
Heap Tree를 배열로 구현
-
heap tree는 완전 이진 트리로 구현어 배열로 표현가능
-
완전 이진 트리의 특성상 중간에 빈값이 없기 때문에, 루트 노드부터 높이 순서대로 배열에 모두 정렬이 가능
-
구현과 노드의 위치를 찾기 쉽게 하기 위해 일반적으로 배열의 0번째 인덱스는 사용하지 않고, 첫 번째 인덱스부터 사용
-
배열로 heap tree를 구현한다면 배열의 크기에 따라서 heap tree의 depth가 얼마인지, 부모와 자식 노드의 위치까지도 쉽게 검색 가능
-
depth(깊이)는 배열의 길이가 1, 3, 7, 15 순서대로 2의 배수를 계속 더한 만큼 depth(깊이)가 늘어난다.
※ 참고 - Heap Tree를 사용되는 곳
힙정렬
