[低端筆記] MIT算法導論 5. Binary Search Trees, BST Sort

MIT的算法導論公開課有兩種版本, 我選較新版的
MIT 6.006 Introduction to Algorithms, Fall 2011

官方筆記

Binary search trees, BST sort (PDF - 1.2MB)

Runway Reservation System

• Airport with a single (very busy) runway
• "Reservations" for future landings
• Reserve req specify "requested landing time" t
• Add t to the set if no other landings are scheduled within k minutes either way
• Remove from set R after the plane lands

|R| = n
O(lg n) time

#Example

Runway Reservation System Example

Let R denote the reserved landing times: R = (41,46,49,56) and k = 3
降落請求:
44 not allowed (46 < 47)
53 OK
20 not allowed (現在為37)

#各資料結構比較

Unsorted list/array:
插入花O(1),但未檢查
而檢查花O(n)

Sorted array:
找到符合R[i] < t 的最小 i  //O(lg n)
比較R[i] 和 R[i-1]  //O(1)
插入(後移)  //O(n)

Heap:
the element that is ≥ or ≤ k from t  //O(n)
除了插入還要跟其他element比較, 所以為O(n)

Binary Search Trees (BST)

• node x
• key(x)
• pointer
• parent(x)
• left(x)
• right(x)

Binary Search Trees (BST)

∀y ∈ x的左子樹, key(y) ≤ key(x)
∀y ∈ x的右子樹, key(y) ≥ key(x)

#Example

建BST樹

insertion w/ check: O(h), h為樹高

#operation

• findmin()
• 最左側節點
• O(h)
• next-larger(x)
• Finding the next larger element
• O(h)

新條件(Runway Reservation System)

Rank(t): 在 ≤ t 時總共有多少飛機降落

示意圖

1. Walk down the tree to find the desired time
2. Add in nodes that are smaller
3. Add in subtree sizes to the left

複雜度: O(h)

t=79執行結果