4주차. Heap
4-1. 힙과 트리 소개
-
트리
-트리에 있는 각각의 요소는 '노드'라 불린다
-루트(root)와 자식(leaf)으로 이루어져 있다
-루트를 통해 트리 안으로 들어간다(연결리스트의 head처럼)
-서로 연결된 것들끼리 부모-자식(parent-child) 관계로 계층적 구조
-트리는 root로부터 이어진 선의 수에 따라 level로 나눠져 있다 (root는 level 0으로 계산되어 증가하므로 위 사진에서 노드 D,E,F,G는 level 2로 같은 level에 위치)
-level: 트리의 높이 -
추가로 알고 싶다면 이 사이트 참고:
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
생각해보기)-어떤 경우에 데이터를 트리 형태로 저장하는 것이 효과적일까요?
답: 계층적(비선형) 구조로 이루어져 있어 서로 연관된 형태(DBMS, 탐색, 검색, 디렉터리 구조 등)인 계층적 데이터를 다룰 때 사용하면 굿!
4-2. 힙:Tree levels
- 힙
-트리(최댓값 및 최솟값을 빠르게 찾고자 고안된 완전이진트리)를 기반으로 한 자료구조
+)완전 이진 트리란
각 노드가 최대 2개의 자식 노드를 갖는 트리 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다
-종류에 따라 두 개의 다른 규칙이 존재하며 목적에 따라 둘 중 하나를 선정
규칙)
MAX HEAP: parent > children ==> root:가장 큰 숫자
MIN HEAP: parent < children ==> root:가장 작은 숫자
ex)MAX HEAP에서 높이구하기(with 요소의 갯수)
결과:
요소의 갯수: n
level: 계층으로 루트로부터 간선의 갯수
height: 계층으로 루트로부터 최대 간선의 갯수
==> 트리에 있는 요소의 갯수로부터 트리의 높이를 계산할 수 있다!
생각해보기)-최대 힙, 최소 힙에서 최댓값과 최솟값은 각각 어디에 위치하나요?
4-3. 힙:추가와 제거
->heap에 데이터를 추가하거나 제거 시, heap의 규칙은 지켜야 한다
규칙)
-MAX HEAP이라면, parent노드의 값 > child노드의 값
-MIN HEAP이라면, parent노드의 값 < child노드의 값
- 추가[Add]
<실행방법>
- 비어있는 공간에 노드를 추가합니다
- parent노드 < child노드에 해당되는 경우, trickle up
*trickle up
-heap의 규칙에 위반되지 않도록 parent와 child이 서로 change(이 때, 추가된 데이터의 이동방향은 위)
ex) '27' 추가
trickle up 후 결과:
==>이를 통해 추가된 노드는 규칙에 위배되지 않는 적절한곳에 배정된다
- root 제거[Remove]
<실행방법>
1.root 제거
2.트리의 마지막 요소를 root로 대체
3.root에서 시작하여 trickle down
*trickle down
-heap의 규칙에 위반되지 않도록 parent와 child(children 중 가장 큰 값)이 서로 change(이 때, 추가된 데이터의 이동방향은 아래)
ex)
trickle down 이후:
==> heap에서 요소를 제거하려면 항상 root를 제거해야 한다
생각해보기)- 루트를 제거할 때, 트리의 마지막 요소를 루트 자리에 넣어주는 이유는 무엇인가요?
답: heap에서는 제거할 때, 최대값이 되는 노드를 먼저 제거한다. 이 때, MAXHEAP은 루트에 해당하므로 루트를 제거하며 루트가 제거될 때 아래 child가 되는 노드는 끊어진 2개의 트리가 되어 '완전 이진 트리'가 되지 못해 트리의 마지막 요소를 루트에 옮기고, 마지막 위치는 heap의 특성을 잃는다.
