완전 이진트리(Complete Binary Tree)와 힙(Heap)의 쉬운 설명!!

자료구조(data structure)에서 트리구조와 힙은 굉장히 중요한 개념이기 때문에 개념에 대한 명확한 이해와 인덱스 속성을 잘 알아야 코딩하는데 큰 도움이 된다.

이번 글에서는 힙과 완전 이진 탐색 트리가 어떻게 값들을 구성하는지 설명해 보겠다.

 

이진트리(Binary Tree)

이진 트리

이진 트리는  노드로 구성되어 있는 트리 구조로 동그란 마크로 되어 있는 부분이 노드들이고 노드들은 서로 포인터로 연결되어 있다. 이는 계층 구조로 표현한 형태인데, 각각의 노드에는 키(instance)가 존재한다.

리스트를 공부하다보면 나오는 노드에 개념과 동일하다고 보아도 무방하다.

노드 들을 살펴보면 위에 있는 노드는 부모 노드라고 하며 아래 있는 노드들을 자식 노드들이라고 한다. 이진트리는 자식 노드의 개수가 2개인 구조로 되어 있다.

위 그림에서 A 노드는 Root 노드라고 한다. 즉, 최상위에 있는 노드 하나를 가리킨다.

D, H , J, G는 Leaf 노드로써 더 이상 자식이 없는 노드를 나타낸다. 

 

완전 이진 트리(Complete Binary Tree)

완전 이진 트리는 이진트리 구조로 되어 있는 것은 당연한 속성이며 Leaf 노드를 제외한 모든 부모 노드가 자식 노드를 2개씩 가지고 있는 것을 완전 이진트리구조라고 한다.

완전 이진 트리

완전 이진 트리의 인덱스 접근 방법

완전 이진 트리는 구조상 각각의 층(레벨)마다 들어갈 수 있는 노드의 개수가 정해져 있다.

루트 노드 개수 : 1, 다음 레벨 : 2, 그다음 레벨: 4, ....

즉, 각 레벨은 2^n의 개수의 노드들이 들어갈 수 있다. 또한 자식 노드의 인덱스를 가지고 부모 노드의 인덱스를 알 수 있는 데 방법을 위에 그림을 가지고 쉽게 예를 들겠다.

완전 이진트리는 벡터, 배열 같은 순차 열로 저장할 수 있는데, 

A(0) - B(1) - C(2) - D(3) - E(4) - F(5) - G(6) - H(7) - I(8) 이런 순서를 가지고 있다. 

예 )

F(5)의 부모 노드인 C(2) 노드를 접근 하기 위해서 어떤 규칙이 있을까?(괄호 안은 노드의 인덱스를 나타낸다.)

바로 (n-1)/2 로 계산한 정수가 바로 부모 노드의 인덱스 값이다. 확인을 해보자.

(5-1)/2 = 2 이다. 이를 통해 H의 부모 노드는 C라는 것을 알 수 있다.

 

힙(Heap)

힙은 완전 이진트리이고, 자식 노드들이 특정한 성질을 가지고 정렬되어 있는 구조이다. 부모 노드가 자식 노드들보다 크다면 최대 힙(Max Heap)구조라고 하고, 부모 노드가 자식 노드들보다 작다면 최소 힙(Min Heap)구조라고 한다.

최대 힙 구조

※ 여기서 한 부모 노드의 자식 노드는 무조건 정렬될 필요는 없다. 위에 그림에서 24,20이 순서가 바뀌어도 상관없다. 또한 20과 25가 바뀐 형태의 힙도 최대 힙이라고 할 수 있다.

 

C++에서 힙을 생성하는 방법과 priority_queue 컨테이너와의 차이를 다음 글에서 정리하여 설명해 보겠다.