Heap
Heap이란?
Heap은 Tree의 구조로 이루어진 자료구조로, 완전이진트리 자료구조임.
(완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 가능한 한 가장 왼쪽에 있는 트리)
최소힙과 최대힙이 존재함.
root Node가 최소값/최대값을 가지는 것이 보장되어 있기 때문에 최소값/최대값 찾는데에 O(1)을 보장함. 하지만 추가나 삭제에서는 O(logn)의 시간복잡도를 가짐.
(힙 트리는 중복된 값 허용함, 이진 탐색 트리는 중복값 허용하지 않음)
Heap 종류
최대힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (루트 노드가 최대값)
최소힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (루트 노드가 최소값)
Heap 구현
가장 표준적으로 구현되는 방식은 배열임. 물론 연결리스트로도 구현이 가능하지만 특정 노드의 검색, 이동 과정이 조금 번거롭기 때문임. 배열의 경우 특정 인덱스에 바로 접근할 수 있기 때문에 좀 더 효율적임.
최소힙 구현에 사용되는 중요 성질
- 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 X 2
- 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 X 2 + 1
- 부모 노드 인덱스 = 자식 노드 인덱스 / 2
[Heap.java]
import java.util.Comparator;
public class Heap<E> {
private final Comparator<? super E> comparator;
private static final int DEFAULT_CAPACITY = 10; // 최소(기본) 용적 크기
private int size; // 요소 개수
private Object[] array; // 요소를 담을 배열
// 생성자 Type 1 (초기 공간 할당 X)
public Heap() {
this(null);
}
public Heap(Comparator<? super E> comparator) {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
// 생성자 Type 2 (초기 공간 할당 O)
public Heap(int capacity) {
this(capacity, null);
}
public Heap(int capacity, Comparator<? super E> comparator) {
this.array = new Object[capacity];
this.size = 0;
this.comparator = comparator;
}
// 받은 인덱스의 부모 노드 인덱스를 반환
private int getParent(int index) {
return index / 2;
}
// 받은 인덱스의 왼쪽 자식 노드 인덱스를 반환
private int getLeftChild(int index) {
return index * 2;
}
// 받은 인덱스의 오른쪽 자식 노드 인덱스를 반환
private int getRightChild(int index) {
return index * 2 + 1;
}
}[배열 크기 재조정에 쓰이는 resize 메소드]
/**
* @param newCapacity 새로운 용적 크기
*/
private void resize(int newCapacity) {
// 새로 만들 배열
Object[] newArray = new Object[newCapacity];
// 새 배열에 기존에 있던 배열의 요소들을 모두 복사해준다.
for(int i = 1; i <= size; i++) {
newArray[i] = array[i];
}
/*
* 현재 배열은 GC 처리를 위해 null로 처리한 뒤,
* 새 배열을 연결해준다.
*/
this.array = null;
this.array = newArray;
}[heap에 데이터를 추가할 때 쓰이는 add 메소드]
public void add(E value) {
// 배열 용적이 꽉 차있을 경우 용적을 두 배로 늘려준다.
if(size + 1 == array.length) {
resize(array.length * 2);
}
siftUp(size + 1, value); // 가장 마지막에 추가 되는 위치와 넣을 값(타겟)을 넘겨줌
size++; // 정상적으로 재배치가 끝나면 사이즈를 증가
}
// 상향 선별
/**
* @param idx 추가할 노드의 인덱스
* @param target 재배치 할 노드
*/
private void siftUp(int idx, E target) {
// comparator가 존재할 경우 comparator 을 인자로 넘겨준다.
if(comparator != null) {
siftUpComparator(idx, target, comparator);
}
else {
siftUpComparable(idx, target);
}
}
// Comparator을 이용한 sift-up
@SuppressWarnings("unchecked")
private void siftUpComparator(int idx, E target, Comparator<? super E> comp) {
// root노드보다 클 때까지만 탐색한다.
while(idx > 1) {
int parent = getParent(idx); // 삽입노드의 부모노드 인덱스 구하기
Object parentVal = array[parent]; // 부모노드의 값
// 타겟 노드 값이 부모노드보다 크면 반복문 종료
if(comp.compare(target, (E) parentVal) >= 0) {
break;
}
/*
* 부모노드가 타겟노드보다 크므로
* 현재 삽입 될 위치에 부모노드 값으로 교체해주고
* 타겟 노드의 위치를 부모노드의 위치로 변경해준다.
*/
array[idx] = parentVal;
idx = parent;
}
// 최종적으로 삽입될 위치에 타겟 노드 값을 저장해준다.
array[idx] = target;
}
// 삽입 할 객체의 Comparable을 이용한 sift-up
@SuppressWarnings("unchecked")
private void siftUpComparable(int idx, E target) {
// 타겟노드가 비교 될 수 있도록 한 변수를 만든다.
Comparable<? super E> comp = (Comparable<? super E>) target;
while(idx > 1) {
int parent = getParent(idx);
Object parentVal = array[parent];
if(comp.compareTo((E)parentVal) >= 0) {
break;
}
array[idx] = parentVal;
idx = parent;
}
array[idx] = comp;
}[데이터 삭제시에 쓰이는 remove 메소드]
@SuppressWarnings("unchecked")
public E remove() {
if(array[1] == null) { // 만약 root가 비어있을경우 예외를 던지도록 함
throw new NoSuchElementException();
}
E result = (E) array[1]; // 삭제된 요소를 반환하기 위한 임시 변수
E target; // 타겟이 될 요소
if(size == 1) {
target = null;
}
else {
target = (E) array[size];
}
array[size] = null; // 타겟 노드를 비운다.
// 삭제할 노드의 인덱스와 이후 재배치 할 타겟 노드를 넘겨준다.
siftDown(1, target); // 루트 노드가 삭제되므로 1을 넘겨준다.
return result;
}
/**
* @param idx 삭제할 노드의 인덱스
* @param target 재배치 할 노드
*/
private void siftDown(int idx, E target) {
// comparator가 존재할 경우 comparator 을 인자로 넘겨준다.
if(comparator != null) {
siftDownComparator(idx, target, comparator);
}
else {
siftDownComparable(idx, target);
}
}
// Comparator을 이용한 sift-down
@SuppressWarnings("unchecked")
private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
array[idx] = null; // 삭제 할 인덱스의 노드를 삭제
size--;
int parent = idx; // 삭제노드부터 시작 할 부모를 가리키는 변수
int child; // 교환 될 자식을 가리키는 변수
// 왼쪽 자식 노드의 인덱스가 요소의 개수보다 작을 때 까지 반복
while((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent); // 오른쪽 자식 인덱스
Object childVal = array[child]; // 왼쪽 자식의 값 (교환 될 값)
/*
* 오른쪽 자식 인덱스가 size를 넘지 않으면서
* 왼쪽 자식이 오른쪽 자식보다 큰 경우
* 재배치 할 노드는 작은 자식과 비교해야하므로 child와 childVal을
* 오른쪽 자식으로 바꿔준다.
*/
if(right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
child = right;
childVal = array[child];
}
// 재배치 할 노드가 자식 노드보다 작을경우 반복문을 종료한다.
if(comp.compare(target ,(E) childVal) <= 0){
break;
}
/*
* 현재 부모 인덱스에 자식 노드 값을 대체해주고
* 부모 인덱스를 자식 인덱스로 교체
*/
array[parent] = childVal;
parent = child;
}
// 최종적으로 재배치 되는 위치에 타겟이 된 값을 넣어준다.
array[parent] = target;
/*
* 용적의 사이즈가 최소 용적보다는 크면서 요소의 개수가 전체 용적의 1/4일경우
* 용적을 반으로 줄임(단, 최소용적보단 커야함)
*/
if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
// Comparable을 이용한 sift-down
@SuppressWarnings("unchecked")
private void siftDownComparable(int idx, E target) {
Comparable<? super E> comp = (Comparable<? super E>) target;
array[idx] = null;
size--;
int parent = idx;
int child;
while((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent);
Object childVal = array[child];
if(right <= size && ((Comparable<? super E>)childVal).compareTo((E)array[right]) > 0) {
child = right;
childVal = array[child];
}
if(comp.compareTo((E) childVal) <= 0){
break;
}
array[parent] = childVal;
parent = child;
}
array[parent] = comp;
if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}[size, peek, isEmpty, toArray]
public int size() {
return this.size;
}
@SuppressWarnings("unchecked")
public E peek() {
if(array[1] == null) {
throw new NoSuchElementException();
}
return (E)array[1];
}
public boolean isEmpty() {
return size == 0;
}
public Object[] toArray() {
return Arrays.copyOf(array, size + 1);
}트리
트리란?
node와 edge를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조임.
값을 가진 node와 이 노드들을 연결해주는 edge로 이루어져 있음
모든 노드들은 0개 이상의 자식 노드를 가지며, 부모-자식 관계로 부름.
트리의 특징
- 트리에는 사이클이 존재할 수 없음
- 모든 노드는 자료형으로 표현이 가능함
- 루트에서 한 노드로 가는 경로는 유일함
- 노드의 개수가 n개면, 간선은 n-1개를 가짐
트리 순회 방식
1. 전위 순회 : 각 부모 노드를 순차적으로 먼저 방문하는 방식임
2. 중위 순회 : 왼쪽 하위 트리를 방문 후 부모 노드를 방문하는 방식임
3. 후위 순회 : 왼쪽 하위트리부터 하위를 모두 방문 후 부모 노드를 방문하는 방식임
4. 레벨 순회 : 부모 노드부터 계층별로 방문하는 방식임
이진 트리와 이진 탐색 트리
- 이진 트리 : 노드의 최대 자식 수가 2인 트리
- 이진 탐색 트리 : 이진 트리에 "왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다"는 추가 조건이 들어간 트리
이진 트리 종류
완전 이진 트리(complete binary tree)
모든 서브트리의 레벨이 같고, 모든 노드들이 레벨별로 왼쪽부터 채워져있는 경우
정 이진 트리(full binary tree)
자식 노드를 한 개도 가지고 있지 않거나, 자식이 있는 경우는 두 개의 자식을 갖는 경우 (모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리)
포화 이진 트리(pertect binary tree)
양쪽으로 빈 공간 없이 모든 노드가 두 개의 자식을 갖고, 레벨도 정확하게 떨어지는 트리 (모든 리프 노드이 레벨이 동일하고 모든 레벨이 가득 채워져 있음)
완벽한 피라미드 구조를 형성하고 있음
레벨이 n인 경우 노드의 개수는 2^n - 1개
균형 이진 트리
높이 균형이 맞춰진 이진트리
왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리
ex) AVL, Red-Black 트리
이진탐색트리
이진탐색트리의 목적
이진탐색의 장점과 연결리스트의 장점을 하나로 합침
- 이진 탐색 : 탐색에 소요되는 시간 복잡도는 O(logn), but 삽입, 삭제가 불가능
- 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간 복잡도가 O(n)
-> 효율적인 탐색 능력을 가지고 자료의 삽입 삭제도 가능하게 만들기 위해 둘을 합함
이진탐색트리의 특징
- 각 노드의 자식이 2개 이하
- 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼
- 중복된 노드가 없어야 함
- 중위순회를 통해 정렬된 순서를 읽을 수 있음
이진탐색트리의 연산
- 검색
- 찾고자 하는 값과 현재 루트 노드의 값 비교
- 타겟 값이 더 크다면 오른쪽 서브 트리로
- 타겟 값이 더 작다면 왼쪽 서브 트리로
- 위 로직을 재귀적으로 반복 수행하여, 루트 노드의 값이 타겟 테이터일 때까지 탐색
- 찾고자 하는 값과 현재 루트 노드의 값 비교
- 삽입
- 새로운 데이터가 들어갈 자리가 비어있으면 그대로 값을 대입
- 비어있지 않은 경우 해당 자리의 노드 값과 비교
- 삽입할 데이터보다 작다면 왼쪽 자식트리로 이동시킴
- 삽입할 데이터보다 크다면 오른쪽 자식 트리로 이동하면 됨
- 삭제
- 리프 노드를 삭제하는 경우
- 그냥 삭제
- 자식 노드가 하나인 노드를 삭제하는 경우
- 해당 자식 노드를 삭제할 노드의 위치로 끌어올림
- 자식 노드가 두 개인 노드를 삭제하는 경우
- 오른쪽 서브 트리의 min 값 or 왼쪽 서브 트리의 max 값중 하나를 삭제할 노드의 위치로 끌어올림
- 리프 노드를 삭제하는 경우
연산 시간 복잡도
- 삽입, 삭제, 탐색 모두 평균 O(logn), 최악 O(n) -> 한쪽으로 편향된 트리의 경우
- 삽입, 삭제, 탐색 시간 복잡도 트리의 깊이에 비례하기 때문
- 편향된 트리는 시간복잡도가 O(n)이므로 트리를 사용할 이유가 사라짐 -> 이를 바로 잡도록 도와주는 개선된 트리가 AVL Tree, Red-Black Tree
이진탐색트리 코드
public class binarySearchTree {
public class Node {
private int data;
private Node left;
private Node right;
public Node(int data) {
this.setData(data);
setLeft(null);
setRight(null);
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
public Node root;
public binarySearchTree() {
this.root = null;
}
//탐색 연산
public boolean find(int id){
Node current = root;
while(current!=null){
//현재 노드와 찾는 값이 같으면
if(current.getData()==id){
return true;
//찾는 값이 현재 노드보다 작으면
} else if(current.getData()>id){
current = current.getLeft();
//찾는 값이 현재 노드보다 크면
} else{
current = current.getRight();
}
}
return false;
}
//삭제 연산
public boolean delete(int id){
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.getData()!=id){
parent = current;
if(current.getData()>id){
isLeftChild = true;
current = current.getLeft();
}else{
isLeftChild = false;
current = current.getRight();
}
if(current==null){
return false;
}
}
//Case 1: 자식노드가 없는 경우
if(current.getLeft()==null && current.getRight()==null){
if(current==root){
root = null;
}
if(isLeftChild==true){
parent.setLeft(null);
}else{
parent.setRight(null);
}
}
//Case 2 : 하나의 자식을 갖는 경우
else if(current.getRight()==null){
if(current==root){
root = current.getLeft();
}else if(isLeftChild){
parent.setLeft(current.getLeft());
}else{
parent.setRight(current.getLeft());
}
} else if(current.getLeft()==null){
if(current==root){
root = current.getRight();
}else if(isLeftChild){
parent.setLeft(current.getRight());
}else{
parent.setRight(current.getRight());
}
}
//Case 3 : 두개의 자식을 갖는 경우
else if(current.getLeft()!=null && current.getRight()!=null){
// 오른쪽 서브트리의 최소값을 찾음
Node successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.setLeft(successor);
}else{
parent.setRight(successor);
}
successor.setLeft(current.getLeft());
}
return true;
}
public Node getSuccessor(Node deleleNode){
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.getRight();
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.getLeft();
}
if(successsor!=deleleNode.getRight()){
successsorParent.setLeft(successsor.getRight());
successsor.setRight(deleleNode.getRight());
}
return successsor;
}
//삽입 연산
public void insert(int id){
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id < current.getData()){
current = current.getLeft();
if(current==null){
parent.setLeft(newNode);
return;
}
}else{
current = current.getRight();
if(current==null){
parent.setRight(newNode);
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.getLeft());
System.out.print(" " + root.getData());
display(root.getRight());
}
}
public static void main(String[] args) {
binarySearchTree b = new binarySearchTree();
//트리에 노드를 삽입
b.insert(3);b.insert(8);
b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
System.out.println("트리삽입 결과 : ");
b.display(b.root);
System.out.println("");
System.out.println("이진트리에서 4를 탐색 : " + b.find(4));
System.out.println("이진트리에서 2를 삭제 : " + b.delete(2));
b.display(b.root);
System.out.println("\n이진트리에서 4를 삭제 : " + b.delete(4));
b.display(b.root);
System.out.println("\n이진트리에서 10을 삭제 : " + b.delete(10));
b.display(b.root);
}
}예상 면접 질문
- AVL 트리를 사용하는 이유에 대해 설명해주세요.
- 한쪽으로 치우친 편향 이진 트리가 되면 트리의 높이가 높아지고, 이에 따라 시간 복잡도가 커지기에 이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용합니다.
참고
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Heap.md
https://velog.io/@kangdev/%EA%B8%B0%EC%88%A0%EB%A9%B4%EC%A0%91%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Heap
https://st-lab.tistory.com/205
https://haenny.tistory.com/345
https://velog.io/@dlgosla/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-Binary-Tree-vzdhb2sp
https://2jinishappy.tistory.com/136
몸은 커졌어도, 머리는 그대로... 하지만 불가능을 모르는 명탐정 현아! 진실은 언제나 하나!