컴퓨터의 힙(Heap)

때는 대학생, 한참 이력서를 넣고 있던 시절, 전화면접이 있었다.

전화 면접관 : 질문 중 하나가 자료구조의 힙에 대해 설명해 보시겠어요?
나 : ?????? 힙은 메모리를 말하는게 아닌가요???????
전화 면접관 : .......(침묵)
나 : ................. (속으로 울고있음)

면접 이후, 자료구조 힙에 대해 공부하였고, 현재 자료구조 서적에서 다시금 보이길래 메모리의 힙과 자료구조 힙에 대한 설명을 담는다.

메모리 힙(Heap)

프로그램이 실행되면 아래 그림과 같이 4개의 메모리 영역을 가지게 된다.

이중 Heap 영역은 사용자가 동적할당을 할 경우 메모리에 저장된다.

C언어에서는 malloc, java에서는 new 키워드로 Heap 영역에 메모리를 할당할 수 있다. 

Heap 메모리의 해제는 C에서는 free 함수로 해제하며, java에서는 JVM에서 가비지 컬렉터가 지우는 시점에 해제된다.

자료구조의 힙(Heap)

힙은 완전 이진 트리이다. 최소 값 혹은 최대 값을 찾아내는 연산에 적합하다.

힙에는 최소 힙과 최대 힙이 있다. 최대 힙은 루트노드로 갈수록 값이 커지며, 최소 힙은 루트노드로 갈수록 값이 작아진다. ( 아래 그림 참조)

일반 이진 트리를 구현할때는 연결 리스트(링크드 리스트)를 많이 사용하는데, 힙은 배열로 구현하는 것이 원칙처럼 여겨진다. 이유는, 힙에서 데이터를 추가하면, 노드를 연결하고 데이터 값에 따른 노드의 위치조정을 해야한다. 반면 배열로 구현할 경우, 배열의 인덱스를 통해 훨씬 쉽게 구현이 되기 때문이다.

힙에서 데이터 추가 과정에 대해 상세히 설명하려면.. ppt로 그림을 여러번 그려야 되기 때문에 과감히 생략하고.. 다른 블로그를 찾아주세염 ㅎ.ㅎ........

이진 트리란

자료구조를 공부한지 꽤 지났다. 책을 다시 펴보니 선형 리스트(리스트, 스택, 큐)는 잘 이해하고 있는데 항상 비선형 리스트(트리, 그래프)는 뭔가 새롭다.

트리에 대해 공부해보자.

Q. 트리란?

- 계층적 관계를 표현하는 자료구조이다.

Q. 이진 트리란?

- 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

- 나뉘어진 두 서브 트리 모두 이진 트리여야 한다.

위 그림은 이진 트리를 보여주는데, 트리에서 사용되는 용어들을 살펴보자

1. 노드 : 트리의 구성요소에 해당하는 A~E까지의 각 요소

2. 간선 : 노드와 노드를 연결하는 연결선

3. 루트 노드 : 트리 구조 최상단에 있는 A 노드

4. 단말노드 : 아래에 다른 노드가 없는 H, E, F, G 노드
5. 차수 : 한 노드에 연결된 서브 노드의 개수, 이진 트리의 차수는 2 이하.

6. 레벨 : 트리에서 각 층별로 숫자를 매김, A는 0레벨, B,C는 1레벨

7. 높이 : 트리의 최고 레벨을 의미한다. H는 레벨3에 속하므로 위 트리의 높이는 3이다.

8. 포화 이진 트리 : 트리의 모든 레벨이 꽉 차 있는 트리 (아래 그림 참조)

9. 완전 이진트리 : 포화 이진 트리는 아니지만 빈틈 없이 노드가 채워진 이진트리 (아래 그림참조)

트리에 저장된 모든 데이터를 출력해야 한다고 가정하자. 우선, 트리의 모든 노드를 방문해야 하는데, 이를 순회라고 한다.

트리를 순회하는 방법에는 아래와 같이 4가지가 있다.

전위 순회 : 루트노드를 먼저 방문한다.

중위 순회 : 루트노드를 중간에 방문한다.

후위 순회 : 루트노드를 마지막에 방문한다.
단계 순회 : 루트노드부터 왼쪽 노드와 오른쪽 노드를 차례대로 방문한다.

핵심은 루트 노드의 방문 순서이다. 글보다는 그림이 이해가 편하다.

전위 순회 방법 ( A-> B-> C)
- 루트노트를 먼저 방문하고 왼쪽부터 오른쪽 순으로 순회한다.

중위 순회 방법 (B-> A-> C)
- 왼쪽 노드를 먼저 방문 후, 루트노드를 방문한뒤 오른쪽으로 순회한다.

후위 순회 방법 (B-> C-> A)
- 왼쪽부터 오른쪽으로, 루트노드를 가장 마지막에 방문한다.

단계 순회 방법 (A-> B-> C)

- 루트노드부터 왼쪽과 오른쪽으로 단계적으로 순회하는 방법

전위 순회와 단계 순회의 결과가 같아보이지만, 트리의 레벨을 한 단계 높인 순회 예시를 들면 이해할 것이라 믿는다.

전위 순회 방법 : A-> B-> D-> E-> C-> F-> G

단계 순회 방법 : A-> B-> C-> D-> E-> F-> G