MIT - Introduction to Algorithms
- Lecture 5. Binary Search Tree, BST Sort
이진 탐색 트리 Review
Copyright to MIT & Srini Devadas
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
아래 그림들은 위 URL에서 다운받은 note를 기반 pdf입니다.
Runway Reservation System
활주로 예약 시스템을 생각해보자
Airport with a single runway
단 한개의 활주로만을 사용이 가능하다고 생각
다음 착륙 예약을 위해 만들어짐, 착륙하고 나면 표식이 사라짐
연속적인 시간으로 표시하며 '착륙에 필요한 시간' t로 표기할 것
k분 동안 시간 착륙 계획이 없다면 t를 R 집합에 추가할 것
지금 우리는 k=3분으로 가정할 것
|R| = n일 때, 우리는 이 과정을 O(log n) time 시간에 끝내고 싶다.
cf) runway 1. 활주로
pend 1. 매달리다 2. 미해결인 채로 있다, 현안(懸案)인 채 있다 3. 의존하다
pending 1. (어떤 일이) 있을 때 까지; …을 기다리는 동안 2. 미결인, 계류 중인 3. 곧 있을
R(37=now, 41.2, 49, 56.3), k=3으로 집합을 설정
53 : OK
44 : not allowed(41.2+3 > 44)
20 : not allowed(past)
Unsorted list/array
정렬되지 않은 경우 O(n)의 시간만큼 걸릴 것
어디서부터 비교해야할지 모르기 때문에 전체 배열을 스캔해야만함 -> O(n)
Insert in O(1) without check
but check takes O(n) time
Sorted array
t라는 일정 시간의 값을 이진 탐색으로 설정 가능
배열의 중간 지점에서 숫자 확인 왼쪽, 오른쪽 확인
Find smallest i such that R[i] >= t in O(log n) time
Compare R[i] and R[i-1] against t in O(1) time
cf) insertion은 하나의 숫자를 넣으며 나머지들을 모두 shift해야함
Actual Insertion (shifting) -> O(n) time
Sorted list 포인터들로 이루어진 list
list에서는 이진 탐색이 불가능 index 2->n으로의 이동이 불가
임의 접근 또한 불가
하나는 잘 하지만 나머지는 못함
배열 : 여러개를 잘하지만 자리 이동이 별루임
Heap의 이 문제에서의 문제는 모든 요소들을 다 살펴봐야함
weak invariant
element that is <= k or >= k from t : O(n) time
이진 탐색 트리는 배열을 트리 구조로 시각화할 수 있다는 점에서 힙과 비슷
이진 탐색 트리는 트리
Sorted array가 가장 비슷한 수준으로 해결하려고 함
Fast insertion into a sorted array
확연한 차별화
have a pointer unlike a heap
힙과 다르게 루트를 제외한 노드에서는 3개의 포인터가 있어서 부모, 왼쪽, 오른쪽의 포인터를 가진다.
pointer : parent(x) , left(x), right(x)
Invariant
For all nodes x, if y is in the left subtree of x
key(y) <= key(x)
y is in the right subtree
key(y) >= key(x)
요약하면 key(left) key(x) key(right) 순서 순서대로 있음
14 17 20 30 40 순서로 들어감
이제 왜 적합한지 보이고 값을 삽입할 것임
자세한 이진 코드 그림은 4p 참조
Insert 49 : 49
Insert 79 : 49 79
Insert 46 : 46 49 79
Insert 41 : 41 46 49 79
Insert 42 (k=3) :
42 vs 49 in k min -> Ok
42 vs 46 in k min -> Ok
42 vs 41 in k min -> not allowed : Check & Failed
Insertion 45 (k=3) :
42 vs 49 in k min -> Ok
42 vs 45 in k min -> not allowed : Check & Failed
h : hightest of tree
Insertion with k minute check O(h) time
같은 값의 경우 포인터를 구별하기 위한 방법을 고안해야함 Multiset
ex) 46, 46의 경우 46a, 46b로 표기로 구별
트리가 균형이 맞지 않으면 문제가 되는가에 대한 질문 -> 나중에 강의를 들으면 알 것
h : 트리의 높이이기에 시간이 O(h)라고 했을 분 해결했다고 말한 것은 아님
(교수의 의도는 해결을 위한 방법이라기 보다 점진적인 방법론 설명을 위한 복선?인 듯)
그렇다면 이진 트리에서는 최솟값을 어떻게 찾는가
-> 단말 노드까지 왼쪽을 따라간다.
최대값은 단말 노드까지 오른쪽을 따라간다
시간 복잡도는? O(h)
find-min : go to the left till leaf : O(h) complexity
next-largest : O(h)
처음 제시한 조건은 아니지만 추가적인 작업을 요구했을 때 어떻게 트리를 확장할 것인가
단, O(h)은 유지할 것
Insert or delete modify "size" number
단말 노드의 rank number = 1
46:1, 64:1, 83:1
79:3(64,79,83 3개를 포함하므로)
49:5(본인을 포함한 하위 노드의 개수가 총 5개)
Insert 43의 경우 삽입 경로를 따라가야함 그리고 보게되는 노드들에 모두 +1
-> 49:6, 46:2, 43:1
Delete 79의 경우 83이 올라오고 64가 왼쪽에 subtree로 존재
t분 전에 착륙하게 될 것은 무엇인가 O(h)
1. Walk down tree to find desire time
2. Add in the nodes that are smaller
3. Add in the subtree size to the left
ex) <= 79, t=79
46 : 79보다 적으므로 add 1
오른쪽으로 움직임 (46 < 79)
왼쪽에 있는 서브티리 노드 개수를 더해줄 것임(오른쪽으로 이동했으므로 당연히 왼쪽은 다 작다라는 가정을 알기 때문)
add 2 (subtree 46)
79 <= 79이므로 79 확인 후 +1
79 왼쪽의 subtree 64에 +1
결과 : +1+2+1+1
우리는 문제를 완벽하게 문제를 풀지 못했다는 점
+
list 형태의 트리가 될 수 있다는 점
따라서 균형 이진 탐색 트리의 개념이 필요
-> 트리가 균형잡힌 구조로써 h가 O(log n)이 될 것
