[자바로 구현하고 배우는 자료구조] 4. 힙(Heap) & 트리(Tree) (1)

---

 

4-1. 힙과 트리 소개

트리에서 원 안의 트리 요소를 노드라 하고, 노드와 노드를 잇는 선을 edge라 한다. root는 트리의 시작부분, leaf/leaves는 트리의 마지막 부분이다. 각각 A 노드는 B, C노드의 부모가 되고, B, C노드는 A노드의 자식이 된다. 같은 부모 노드를 갖는 B, C노드는 서로 형제 노드이다. 루트 노드의 레벨은 0이고, 자식노드로 내려갈 수록 1씩 추가된다.

 

4-2. 힙:Tree levels

  트리라고 부르는 구조는 사실 힙이고, 힙은 어떤 종류의 힙인가에 따라 두 가지 규칙이 존재한다. 첫 번째 규칙은 부모 노드가 자식노드보다 무조건 크다는 것이다. 이 경우, MaxHeap이라 부르며 루트 노드의 크기가 트리의 노드 중 가장 크다. 두 번째 규칙은 부모 노드가 자식노드보다 무조건 작다는 것이다. 이 경우, MinHeap이라 부르며 루트 노드의 크기가 트리의 노드 중 가장 작다.

n은 루트 노드부터 해당 레벨의 마지막 노드까지 노드의 갯수를 구한 것이다. n으로 구한 계산식과 트리의 level, 높이이 동일하다. 구체적인 노드의 갯수를 알 수 없어도 해당 식을 이용하면 알 수 있다. 

4-3. 힙:추가와 제거

 힙에 새로운 노드를 추가할 때는 추가 가능한 가장 마지막 공간에 노드를 추가한 다음 부모노드와 크기를 비교한다. 만약 부모노드보다 크다면 위치를 바꾸고 다시 크기를 비교한다.

 힙에서 무언가 제거할 때는 루트를 제거한 뒤, 가장 마지막 노드를 루트 자리에 넣는다. 그리고 자식노드와 크기를 비교한 뒤 위치를 바꾸고 다시 자식노드와 크기를 비교한다.