[자료구조] 이진 트리, 힙 이론, 힙 트리

 

글의 요약 설명 부분. 

 

목차

 

---

 

 

Binary Tree (이진 트리)

각 노드가 최대 2개의 자식 노드를 가지는 트리

• 왼쪽을 타고 가면 현재 값보다 작다.
• 오른쪽을 타고 가면 현재 값보다 크다.

그냥 무식하게 추가하면, 한쪽으로 기울어져서 균형이 깨진다.

트리 재배치를 통해 균형을 유지하는 것이 과제 (AVL, Red-Black)

 

---

 

힙 이론

힙(Heap)은 '힙 순서 속성(Heap Order Property)'을 따르는 완전 이진 트리이다. 완전 이진 트리는 최고 깊이를 제외한 모든 깊이의 노드가 완전히 채워진 이진 트리다.

 

'힙 순서 속성(Heap Order Property)'이란 '트리 내 모든 노드가 부모 노드보다 커야 한다'는 규칙이다.

 

※ 힙 이론(또는 힙 트리)에서 다루는 용어 힙(Heap)은 자유 저장소(Free Store)를 의미하는 그 힙이 아니다.

---

 

Heap Tree (힙 트리)

1. [부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 크다.

2. 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다.

 

배열을 이용해서 힙 구조를 바로 표현할 수 있다.

1. i번 노드의 왼쪽 자식은 [ (2 * i) + 1 ]번
2. i번 노드의 오른쪽 자식은 [ (2 * i) + 2 ]번
3. i번 노드의 부모는 [ (i - 1) / 2 ]번

ex. vector<int> heap(5);

 

 

힙 트리 구조의 유용성

• 최대값 꺼내기가 빠르다.
• 시간 복잡도가 낮다. 시간 복잡도가 ' log N '이다.

---

 

 

전체코드

마무리