코르시카's Blog

■ 이진 탐색트리 1) 정의 : > Linked list - O(1) 삽입 / 삭제 - O(N) 탐색 복잡도 > Binary Search - 자료구조가 sorting되어있는 상태에서 시행 - O(logN) 탐색 복잡도 ※ 위 두개의 장점을 합친 방식으로 자료구조를 짠 것이 '이진 탐색 트리' 2) 이진탐색 트리 특징 (a) 각 노드의 자식이 2개 이하 (b) 완전이진트리 구조는 아님!! - 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 같거나 큼 (c) 중복노드 많은 경우 - 다른 자료구조 사용하는 것이 효율적 (d) 평균시간복잡도 O(log(N)) 편향 트리인 경우 O(N)에 가까워 짐 → 트리가 왼쪽 / 오른쪽으로 쏠려있는 경우 3) 트리 변경의 3가지 case 자식이 없는 leaf ..

■ Heap 1) 정의 : 연관된 데이터에서 최대값 / 최소값을 빠르게 찾기 위해 고안된 "완전 이진 트리" ※ 완전이진트리 : 노드 삽입시 최하단 왼쪽 노드부터 차례로 삽입하는 트리 2) 사용 이유 : - array( and python list)에서 배열 길이만큼 index searching시간 소요 O(N) - heap에 데이터를 넣으면 O(log N) 평균시간이 걸림 - 최대 최소를 빠르게 찾아야 하는 경우 유용 ( PS 문제에 최소/최대 이용하여 문제 빠르게 해결하는 경우 있었음 ) 3) 종류 (1) min heap - 정의 : (a) 각 노드의 값은 해당 노드의 자식 값보다 작음 (b) 완전 이진트리 형태를 가짐 - python 기본 heapq library 경우 min heap으로 구성 ■ ..