[자료구조]2진 트리 / 힙 정렬

2진 트리(Binary Tree)

2진 트리는 트리 구조 중에서 가장 기초이면서 간단한 트리 구조입니다. 또한 실제 많이 사용하는 트리 이기도 합니다.

 

2진 트리는 모든 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조입니다. 이 두 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드라고 하며, 원래의 노드를 이들의 부모 노드라고 합니다. 

2진 트리는 2진 탐색 트리와 이진 힙의 구현에 흔히 쓰입니다.

-출처 (위키 : 2진 트리)

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

 

트리 용어

 

-노드(Node)

트리의 요소 하나하나를 나타내는 기본 원소를 의미합니다.

 

-브랜치(Branch)

노드와 노드를 연결하는 연결선을 의미합니다.

 

-차수(Order)

부모 노드가 가지는 자식 노드들 중 최대 개수를 의미하며 2진 트리에서는 최대 차수 2입니다.

 

-레벨(Level)

트리의 특정 깊이를 가지는 노드의 집합을 의미합니다.

 

-단말 노드(Terminal Node)

노드 중에서 자식 노드가 없는 노드를 의미합니다.

 

-루트(Root)

2진 트리를 구성하는 노드 중 가장 최상단에 존재하는 노드를 의미합니다.

 

-부모 노드(Parent Node)

자식 노드를 가지고 있는 노드를 의미합니다.

 

-자식 노드(Child Node)

부모 노드가 있는 노드를 의미하며 부모의 위치에서 왼쪽에 있으면 왼쪽 자식 노드, 오른쪽에 있으면 오른쪽 자식 노드라고 합니다.

 

-서브 트리(Sub Tree)

트리 안에 존재하는 트리를 의미합니다.

 

2진 트리의 종류

-포화 2진 트리(Full Binary Tree)

모든 레벨에서 노드들이 모두 채워져 있는 트리를 말합니다.

 

-완전 2진 트리(Complete Binary Tree)

마지막 레벨을 제외하고 노드가 모드 채워져 있으며(마지막 레벨도 다 채워져 있을 수 있음) 마지막 레벨도 노드들이 왼쪽부터 채워져 있는 트리를 말합니다.

 

-편향 2진 트리(Skewed Binary Tree)

2진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리를 말합니다.

 

 

 

힙(Heap)

완전 2진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조입니다.

 

-최대 힙(Max Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 크기를 가지는 관계

 

-최소 힙 (Min Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같은 크기를 가지는 관계

 

사진 출처 : http://alloc.tistory.com/7

 

힙 정렬(Heap Sort)

힙 자료구조를 이용한 정렬방식입니다.

 

힙에서 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 루트 노드의 원소를 삭제하여 반환합니다.

최대 힙에 대해서 원소의 개수만큼 삭제 연산을 수행하여 내림차순으로 정렬

최소 힙에 대해서 원소의 개수만큼 삭제 연산을 수행하여 오름차순으로 정렬

 

힙 정렬 수행방법

1. 정렬한 원소들을 입력하여 최대 힙 구성

2. 힙에 대하여 삭제 연산을 수행하여 얻은 원소를 마지막 자리에 배치

3. 나머지 원소에 대해서 다시 최대 힙으로 재구성

   원소의 개수만큼 2~3을 반복 수행

 

 

<Max Heap Code>

 

<Heap class>

힙 class 멤버입니다. 

addData() 함수는 힙에 데이터를 추가하는 함수입니다.

sort() 함수는 힙 정렬을 수행하는 함수입니다.

swapData() 함수는 두 데이터의 값을 바꾸는 함수입니다.

printData() 함수는 멤버 배열의 값을 출력해 주는 함수입니다.

 

<Heap addData>

힙(Heap)에 데이터를 추가하고 최대 힙을 구성하는 함수입니다.

함수로 뒤에 데이터를 추가하고 이 데이터를 부모 노드의 값과 비교하여 값이 크면 부모 노드의 값과 교환합니다. 

 

<Heap Sort>

최대 힙 삭제 연산을 수행하는 함수입니다.

맨 앞에 있는 노드의 값과 맨 마지막 노드의 값을 바꿉니다.

맨 마지막 노드의 값을 고정시키고 나머지 힙에 대해서 최대 힙을 다시 구성합니다.