Preliminary things
Difference between array and list
Array
- 每个元素都有一个index, 通过index来操作该元素的所有动作。
- Array 的大小是一开始就确定的,储存的个数不能超过这个最大限制。然而在实际当中,这个upper limit很少会被达到,但是分出去了就分出去了,不能拿来做别的事情,所以会造成内存的浪费
- 插入一个新元素会比较 expensive, 因为新元素之后的所有元素都需要移动。同理删除。
- Array allow both direct and sequential access to element
List
- 是有个有序的集合,由指针(链表)来确定位置的,根据不同的implementation, 可分为 linked list 和 dynamic array
- 每个元素(node), 包含数据同时还有指向下一个元素的指针
- 大小是动态的,可随时变的
- 插入和删除操作花费较少
- lists allow only sequential access. Therefore, cannot do binary search with linked lists.
- Extra memory space for a pointer is required with each element of the list.
A binary tree is made of nodes, where each node contains a “left” reference, a “right” reference, and a data element.
Runway Reservation System problem
- Airport with single (very busy) runway
- Have “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.
- Algorithm: Keep R as a sorted list
1
2
3
4
5
6
7
8
9init: 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)
If using sorted list:
Appending and sorting takes $Θ(nlg n)$ time. However, it is 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 the insertion point is found.
If using 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.
If using Unsorted list/array:
k minute check takes O(n) time.
If using Min-Heap:
It is possible to insert in $O(lg n)$ time. However, the k minute check will require $O(n)$ time since we need to compare both sides of the heap.
If using Dictionary or Python Set:
Insertion is $O(1)$ time. k minute check takes $Ω(n)$ time
Binary Search Trees (BST)
Properties:
- Each node x in the binary tree has a key $key(x)$.
- Nodes other than the root have a parent p(x).
- Nodes may have a left child left(x) and/or a right child right(x). These are pointers unlike in a heap
- For any node x, for all nodes y in the left subtree of x, $key(y) ≤ key(x)$. For all nodes y in the right subtree of x $key(y) ≥ key(x)$.
Operations:
- insert(val): Follow left and right pointers till you find the position (or see the value)
- find(val): Follow left and right pointers until you find it or hit NIL
- findmin(): Key is to just go left till you cannot go left anymore.
Complexity:
All operations are $O(h)$ where h is height of the BST.
Augmenting the BST Structure
When a data structure doesn’t support some of the operations that we need. Then we can often augment the data strucutre by adding a data member or two and an additional operation or two.
Rank(t): give the number of planes are scheduled to land at times ≤ t
Solution: by adding a subtree size memeber into the structure, like another key to the node