IT 지식/CS 기초
비선형 자료구조 2진 트리
Security Engineer
2024. 8. 17. 00:12
2진 트리(Heap)
- 자료당 두 개의 위치정보(링크)를 이용해 셋을 하나로 묶는다.
- 맨 꼭대기를 기준으로 왼쪽에는 작은 숫자, 오른쪽에는 큰 숫자 카드가 있다고 가정한다.
- 생각해볼 문제: 여기에 5번이 있는지 알고 싶다 몇 번 비교하면 찾을 수 있을까? → 3회
- 2진 트리 = Heap(힙) → 정보를 빠르게 나열하기가 굉장히 좋다.
파이썬 코드로 Heap 구현하기
- Heap(힙)은 최대/최소값을 찾는데 최적화된 자료구조
- 힙은 기본적으로 완전 이진 트리 = 무조건 왼쪽 자식 노드부터 데이터 삽입
- 힙은 데이터의 중복을 허용
- push → heappush (값 넣기)
- pop → heappop (값 빼기)
최대 힙(Max Heap)
- 최대 힙은 루트 노드가 가장 큰 값을 가지고, 부모 노드가 항상 자식 노드보다 값이 크거나 같다.
최소 힙(Min Heap)
- 최소 힙은 루트 노드가 가장 작은 값을 가지고, 부모 노드가 항상 자식 노드보다 값이 작거나 같다.
- 파이썬에서는 최소 힙이 기본 힙이다.
< 입력>
import heapq as h # heapq 모듈 불러오고 h로 사용
tree = [] # tree 변수에 빈 리스트 대입
h.heappush(tree,2) # tree에 heappush로 2 추가
h.heappush(tree,4) # tree에 heappush로 4 추가
h.heappush(tree,5) # tree에 heappush로 5 추가
h.heappush(tree,8) # tree에 heappush로 8 추가
h.heappush(tree,7) # tree에 heappush로 7 추가
h.heappush(tree,6) # tree에 heappush로 6 추가
print(tree) # tree 출력
h.heappush(tree,1) # tree에 heappush로 1 추가
print(tree) # tree 출력
h.heappop(tree) # tree에 heappop으로 값 빼기
print(tree) # tree 출력
< 출력 >
[2, 4, 5, 8, 7, 6]
[1, 4, 2, 8, 7, 6, 5]
[2, 4, 5, 8, 7, 6]
힙 삽입
1) 1을 최소 힙([2,4,5,8,7,6])에 삽입 시, 힙은 완전 이진 트리이므로 삽입 시에도 이를 유지해 완전 이진 트리를 만족하는 자리에 1 값이 삽입된다.
2) 1은 값이 5인 부모노드보다 값이 작으므로 최소 힙의 성질을 만족하기 위해 부모 노드와 자리를 바꾼다.
3) 1은 값이 2인 부모 노드보다 값이 작으므로 최소 힙의 성질을 만족하기 위해 부모 노드와 자리를 바꾼다.
힙 삭제
- 최소 힙에서의 삭제는 값이 제일 작은 노드 = 루트 노드의 삭제를 의미한다.
1) 1 값을 가진 노드를 삭제한다.
2) 루트 노드가 비게 되어, 이를 마지막 노드가 채운다.
3) 자식 노드 값이 더 작으므로 값을 교환해주기 위해 더 작은 값을 구한다. 2가 4보다 더 작으므로 2의 값을 가진 노드와 루트 노드의 자리를 바꾼다.
4) 최소 힙을 만족해 삭제가 종료된다.
참고