각 노드의 자식이 2개 이하인 트리를 이진 트리라고 한다.
왼쪽 서브 트리의 모든 값은 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진트리를 이진 검색트리라고 한다.
이진검색트리를 활용하면 insert, erase, find, update를 모두 O(logN)에 처리할 수 있다.
원소가 크기 순으로 정렬되어 있다.
삽입은 루트부터 시작해서 작으면 왼쪽 크면 오른쪽으로 이동하는 것을 반복해서 위치를 찾을 수 있다.
삭제가 문제인데 자식노드가 달려있는 부모 노드를 그냥 삭제하면 트리의 구조가 망가지게 된다. 따라서 부모노드보다 큰 수 중 제일 작은 수를 찾아서 자리를 교체해주면 된다. (큰수중 제일 작은 수를 찾는 방법은 오른쪽 자식 노드에서 제일 왼쪽 아래 노드를 찾으면 된다!)
위에서 제시한 시간복잡도는 트리의 구조가 잘 만들어졌을 때에 적용되고 편향된 트리가 만들어진다면 그건 연결리스트에 삽입 삭제 수정을 하는 것과 다를 바 없기 때문에 이진검색트리를 사용하는 이유가 없어진다.
트리의 균형이 유지될 수 있도록 위 문제점을 개선한 것이 자가 균형 트리이다 AVL, red black 트리가 있다.
boj-7662
import heapq
import sys
def pop_from_heap(heap:list, exists:list) -> None:
if heap:
exists[heap[0][1]] = False
heapq.heappop(heap)
def pop_delete_number(heap:list, exists:list) -> None:
while heap and not exists[heap[0][1]]:
heapq.heappop(heap)
def get_left_max_min_value() -> None:
max_heap = []
min_heap = []
K = int(input())
exists = [False] * K
for i in range(K):
operator, number = input().split()
number = int(number)
if operator == "I":
heapq.heappush(max_heap, (-number, i))
heapq.heappush(min_heap, (number, i))
exists[i] = True
if operator == "D":
if number == -1:
pop_delete_number(heap=min_heap, exists=exists)
pop_from_heap(heap=min_heap, exists=exists)
else:
pop_delete_number(heap=max_heap, exists=exists)
pop_from_heap(heap=max_heap, exists=exists)
pop_delete_number(heap=min_heap, exists=exists)
pop_delete_number(heap=max_heap, exists=exists)
if max_heap and min_heap:
print(-max_heap[0][0], min_heap[0][0])
else: print("EMPTY")
if __name__ == '__main__':
sys.stdin = open('', 'r')
T = int(input())
for _ in range(T):
max_min_value = get_left_max_min_value()
boj-1202
가장 가격이 높은 보석부터 확인하며 해당 보석을 담을 수 있는 가방중 최대 무게가 가장 작은 가방을 이용해 보석을 담는게 이득이다.
가장 가격이 높은 보석 x를 해당 보석을 담을 수 있는 가방 중 최대 무게가 A보다 큰 가방 B를 이용해 보석을 담는 게 더 이득일 수 있는가?
가장 가격이 높은 보석 x를 해당 보석을 담을 수 있는 가방 중 최대 무게가 가장 작은 A가 존재하는데도 불구하고 가방에 넣지 않는 게 더 이득일 수 있는가?
import heapq
import sys
# input = sys.stdin.readline
N, K = map(int, input().split())
jewels = []
for _ in range(N):
weight, value = map(int, input().split())
heapq.heappush(jewels, [weight, value])
bags = []
for _ in range(K):
bag_capacity = int(input())
heapq.heappush(bags, bag_capacity)
answer = 0
capable_jewel = []
for _ in range(K):
bag_capacity = heapq.heappop(bags)
while jewels and bag_capacity >= jewels[0][0]:
[weight, value] = heapq.heappop(jewels)
heapq.heappush(capable_jewel, -value)
if capable_jewel:
answer -= heapq.heappop(capable_jewel)
elif not jewels:
break
print(answer)