힙 트리란 무엇일까(Max, Min Heap Tree)

Q. 힙 트리의 정의는 어떻게 되어있을까?

 

Max Heap Tree의 경우, 모든 부모노드는 자식 노드보다 커야 한다. 따라서, 루트 노드는 모든 노드들보다 큰 상황이다. 반정렬상태를 유지한다고 표현하기도 한다. 

 

힙 트리는 또한 항상 Complete Binary Tree 형태를 이룬다. Binary의 의미는 자식 노드가 2개임을 의미한다. Complete는 트리의 높이가 H일 때, 전체 자식 노드의 개수는 2^(H - 1)보다 같거나 크고, 2^H - 1보다 같거나 작은 것을 의미한다. 

 

따라서 어떤 탐색이든 O(logH)만에 가능하다고 표현하기도 한다.

 

 

 

Q. 힙 트리는 어떻게 구현할까?

 

어떤 부모노드의 인덱스가 i라고 하면, 왼쪽 자식 노드는 2 * i, 오른쪽 자식 노드는 2 * i + 1라고 표현할 수 있다. 만약에 전체 노드의 크기가 N라면, 배열의 크기는 N이면 된다.

 

트리에 필요한 삽입, 삭제 두 가지를 구현하면 된다. 

 

힙트리에서 삭제란 루트 노드를 지우는 것을 의미한다. 배열에서 인덱스가 0을 가르키는 값을 얻으면 된다. 가장 마지막 인덱스를 가지고 있는 노드와 교체하고, 마지막 노드 인덱스를 자식 노드보다 작게끔 이동시켜주면 된다.

 

삽입은 가장 마지막 인덱스에 값을 넣고, 부모 노드와 비교하면서 자리를 찾으면 된다.