BST(Binary Search Tree)
BST 특징
이진트리의 일종으로, 효율적인 탐색을 위한 저장 방법이다.
1) 항상 왼쪽의 노드가 오른쪽의 노드의 값보다 작다.
주의할 점은, 힙과 달리 상/하에서의 값은 절대적이지 않다는 것이다. 따라서 가장 오른쪽 아래의 수가 항상 트리에서 가장 큰 수임이 보장된다.
이러한 특징은 균형 잡힌 트리가 아닐 경우, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 되어 탐색 시간이 O(N) 으로 증가한다.
BST를 사용해야 하는 경우
항상 크기 순대로 정렬이 되어있으므로, 탐색시 유리하다(O(LogN))
하지만 삽입, 삭제의 경우에도 O(LogN)의 성능을 가지므로 BST가 아닌 힙을 사용하는것이 좋다.
Heap
힙의 특징
1) 상/하위 관계(depth 별로)가 보장된다.
max-heap은 상위에 있는 노드가 하위에 있는 노드보다 크면 되며, 같은 level을 가진 좌우 노드끼리는 아무런 관계가 존재하지 않는다.
2) 반드시 완전 이진 트리이어야 한다.
3) 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 힙 구조여야 한다.
🔖 힙에서의 노드별 공식
노드 번호가 m이라고 가정
1. 부모 노드의 번호 :m//2
2. 왼쪽 자식의 번호 :2*m
3. 오른쪽 자식의 번호 :2*m + 1
힙을 사용해야 하는 경우
삽입/삭제 연산시 사용한다. 항상 배열의 끝에서 삽입과 삭제연산이 일어나므로 O(1)의 성능을 가지며, 이는 BST의 OlogN 시간보다 빠르기 때문이다.
특히, Root노드가 가장 우선순위가 높기 때문에 빠른 속도로 가장 작은 값을 추출하거나 가장 큰 값을 추출해야 하는 경우 사용한다.
파이썬으로 힙 구현
class Maxheap:
def __init__(self):
self.data = []
def insert(self, item):
self.data.append(item) # 맨 끝에 원소 추가
i = len(self.data) - 1 # 0번 인덱스 제외
while i > 1: # 각 원소를 부모 노드와 비교 하면서 최대 힙의 성질에 맞도록 교환
if self.data[i] > self.data[i//2]: # 자신의 부모 노드 보다 크다면 부모 노드와 교환
self.data[i], self.data[i//2] = self.data[i//2], self.data[i]
i //= 2 # 현재 위치를 부모 위치로 변경
else:
break # 자신의 부모 노드 보다 작다면 교환할 필요가 없음
def remove_max(self): # pop 연산
if len(self.data) > 1: # 힙에 루트 제외 원소가 남아 있다면
self.data[1], self.data[-1] = self.data[-1], self.data[1] # 루트와 맨 끝에 있는 노드 끼리 자리 교환
data = self.data.pop(-1) # 힙에서 가장 큰 원소를 빼내기 + 제거
self.max_heapify(1) # root 노드에 위치한 값을 아래로 내리 면서 적절한 위치로 이동 시킴
else:
data = None
return data
def max_heapify(self, i): # 힙 정렬
left = i * 2
right = (i * 2) + 1
smallest = i # 이후 교환할 위치
if left < len(self.data) and self.data[i] < self.data[left]:
smallest = left # 왼쪽 자식의 위치와 교환 위해 임시 저장
if right < len(self.data) and self.data[i] > self.data[right]:
smallest = right # 오른쪽 자식의 위치와 교환 위해 임시 저장
if smallest != i:
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
self.max_heapify(smallest) # 재귀적 호출을 이용해 최대 힙의 성질을 만족할 때까지 트리를 정리참고자료
https://hyoeun-log.tistory.com/entry/자료구조-Heap과-BST의-차이점
https://m.blog.naver.com/leeinje66/221622360256
