[TIL] 자료구조 - TrickleUp 함수

※ TrickleUp 함수

- 완전이진트리 이기 때문에 노드의 위치는 다음과 같은 성질을 가진다

 

children: 2 * parent + 1 혹은 2 * parent + 2

parent: floor((child-1)/2)

 

위와 같은 성질을 이용하여 노드 추가 과정을 코드로 작성하면 다음과 같다

 

int lastposition; // 어디까지 요소를 넣었는지 기록하기 위함
E[] array = (E[]) new Object[size];
public void add(E obj){
	array[++lastposition] = obj; // 1. 노드 추가
    trickleup(lastposition); // 2. trickle up
}
public void swap(int from, int to){
	E tmp = array[from];
    array[from] = array[to];
    array[to] = tmp;
}
public void trickleup(int position){
	if(position == 0)
    	return;
    int parent = (int) Math.floor((position-1)/2)
    if (((Comparable<E>) array[position]).compareTo(array.parent)>0){
    	swap(position, parent);
        trickleup(parent);
    }
}