이진 검색 트리 - 바킹독 유튜브

정의와 성질

각 노드의 자식이 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

명제

가장 가격이 높은 보석부터 확인하며 해당 보석을 담을 수 있는 가방중 최대 무게가 가장 작은 가방을 이용해 보석을 담는게 이득이다.

귀류법1

가장 가격이 높은 보석 x를 해당 보석을 담을 수 있는 가방 중 최대 무게가 A보다 큰 가방 B를 이용해 보석을 담는 게 더 이득일 수 있는가?

귀류법2

가장 가격이 높은 보석 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)