Lecture 5 : Scheduling and Binary Search Trees

• Runway reservation system (Definition, How to solve with lists)
• Binary Search Trees (Operations)

Runway Reservation System

- Airport with single (very busy) runway (Boston 6 -> 1)

- "Reservations" for future landings

- When plane lands, it is removed from set of pending events

- Reserve req specify "requested landing time" t

- Add t to the set if no other landings are scheduled within k minutes either way. Assume that k can vary.

  (else error, don't schedule)

Let R denote the reserved landing times: R = (41, 46, 49, 56) and k = 3

 

Algoritm 

Keep R as a sorted list.

 

init: R = []
req(t): if t < now: return "error"
for i in range (len(R)):
	if abs(t-R[i]) < k: return "error"
R.append(t)
R = sorted(R)
land: t = R[0]
if (t != now) return error
R = R[1: ]					(drop R[0] from R)

 

Can we do better?

• Sorted list: Appending and sorting takes Θ(n lg n) time. However, it tis possible to insert new time/plane rather than append and sort but insertion takes Θ(n) time. A k minute check can be done in O(1) once in the insertion point is found.
• Sorted array: It is possible to do binary search to find place to insert in O(lg n) time. Using binary search, we find the smallest i such that R[i] ≥ t, i.e., the next larger element. We then compare R[i] and R[i-1] against t. Actual insertion however requires shifting elements which requires Θ(n) time.
• Unsorted list/array: k minute check takes O(n) time.
• Min-Heap: It it possible to insert in O(lg n) time. However, the k minute check will require O(n) time.
• Dictionary or Python Set: Insertion is O(1) time. k minute check takes Ω(n) time.

What if times are in whole minutes?

Large array indexed by time does the trick. This will not work for arbitrary precision time or verifying width slots for landing.

Key Lesson: Need fast insertion into sorted list.

 

Binary Search Trees (이진 탐색 트리)

 

컴퓨터 과학에서 이진 탐색 트리(BTS: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.

 

-각 노드에 값이 있다.

-값들은 전순서가 있다.

-노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

-노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.

-좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

 

이진 탐색 트리에서의 검색

이진 탐색 트리에서 키 x를 가진 노드를 검색하고자 할 때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다.

검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다.

=> 불일치하고 검색하고자 하는 값이 루트노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다.

=> 불일치하고 검색하고자 하는 값이 루트노드의 값과 같거나 큰 경우 오른쪽 서브트리에서 재귀적으로 검색한다.

 

삽입

- 삽입을 하기 전, 검색을 수행한다.

- 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

 

 

삭제

 

삭제하려는 노드의 자식 수에 따라

 

- 자식노드가 없는 노드(잎 노드) 삭제: 해당 노드를 단순히 삭제한다.

- 자식노드가 1개인 노드 삭제: 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다.

- 자식노드가 2개인 노드 삭제: 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽 서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 거브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.

 

복잡도