TIL 정리_81

힙, 트리

트리 노드의 제일 위를 트리의 root라고 한다
자식이 딸려 있지 않은 부분은 leaves이다 
탐색할때는 뿌리를 통해서 접근한다
간선 edge 두 노드를 연결하는 선 간선의 수에 따라 level을 나눈다
트리의 각각의 요소 : 노드 

 

 

트리의 자료구조
Heap 
규칙
1 부모 노드가 자식 노드보다 크다
-> 최대 힙 MAX HEAP 
2 부모 노드가 자식 노드보다 작다 
-> 최소 힙 Min HEAP 

둘 중 어느 방법을 사용해도 무관하다 
가장 큰 숫자가 뿌리에 있게 하려면 최대 힙, 
가장 작은 숫자로부터 시작하려면 최소 힙을 사용하면 된다 

 

 

트리에서의 높이 
루트에서 가장 먼 잎까지 가는데 거치게 되는 간선의 개수이다

최대 힙에서 노드의 개수 n, level, height,  log_2(n+1) -1log
​2(n+1)−1  
log_2(n+1) -1log2(n+1)−1 은 height와 일치하므로, 

트리에 요소가 몇 개 있는지 알면 트리의 높이를 계산할 수 있다

 

부모노드가 항상 자식노드보다 큰 최대 힙의 경우
27이라는 숫자를 추가 할 때 맨 끝에 추가하면 자식 노드가 부모 노드의 값보다 커질때가 있다
이때 자신과 부모의 값을 서로 바꿔주면 된다
10 - 27 -18
10 - 18 - 27  두 노드를 바꿔야 한다

 

 

add
어떤 노드를 추가하기 위해서는 
새로운 노드를 사용가능한 위치에 추가한 다음 //비어있는 공간에 노드를 추가
이를 알맞은 위치로 올려주어야 한다 -> 추가한 요소를 부모노드와 비교하여 바꾼다  

 

 

Trickle 함수 
Heaps 
레벨 순서 순회 트리의 노드에 숫자를 붙이고 부모와 자식관의 관계를 본다
child : 2 * parent + 1
2 * parent + 2
parent : floor ((child-1)/2)

배열을 만들어서 규칙을 활용하면 코드로 쉽게 구현이 가능하다 
-> 레벨 순서에 맞춰 배열을 채운다

이진 힙을 구현한 코드 
아래의 전역변수가 필요하다
int lastposition; //배열에 몇 개의 요소가 들어있는지 확인
E[] array = (E[]) new Object[size]; 

힙에 요소를 추가 -> 사용가능한 다음 위치에 추가해야 한다

TrickleUp 함수
사용가능한 위치에 요소를 추가하고 부모 노드와 비교하여 
루트에 도달할 때까지 순서를 바꾸는 것을 말한다

코드 

 

int lastposition;
E[] array = (E[]) new Object[size]; 
public void add(E obj) {
array[++lastposition] = obj; //lastposition의 값을 증가시킨다
trickleUp(lastposition); //부모 노드보다 크다면 위치 변경
}

public void trickleUp(int position) {
if(position == 0) return; //루트에 도착하면 현재 위치가 0이 된다 
int parent = (int) Math.floor((position-1)/2);
if(((comparable<E>)array[position]).compareTo(array.parent)>0) {
swap(position, parent);
trickleUp(parent); 

-> 더이상 비교가 일어나지 않을때까지 크기를 비교한 후 멈춘다 

 

**두 배열의 위치를 바꾸는 간단한 방법 

 

public void swap(int from, int to) {
E  tmp = array[from;
array[from] = array[to];
array[to] = tmp;
}