5. 힙 트리 ( Heap Tree )

트리형 자료구조에서 최대값, 최소값을 빠르게 찾아내기 위해 고안된 자료구조이다.

단순한 규칙 하나를 가지고 있는데

부모의 값은 항상 자식들의 값보다 크거나 작아야 한다.

최소값을 구할 때는 부모의값이, 최대값을 구할 때는 자식의 값이 작아야한다.

(최소 힙, 최대 힙)

 

힙 트리의 삽입과정은 다음과 같다.

 

9가 삽입될 때, 해당 트리에서 최소힙을 구하는 과정

 

 

1, 최하위 노드를 삽입한다.

 

 

2, 부모노드와 비교하여 조건에 부합할 경우, 부모노드와 교환한다.

 

 

 

 

3, 위 과정을 반복한다.

 

 

 

삭제 과정은 루트 노드를 제거 후,

루트자리에 마지막노드를 삽입하고 자식노드들과 비교하는 형식으로 이루어진다.