Princeton Alogorithm COS226 Week

symbol tables is a key-value pair abstraction.
we can insert a value with specified key. or give a key then search for the corresponding value.

below list a lot of symbol table applications

image.png

below is the symbol table api

image.png

method get() return null if key not present.
method put() overwrites old value with new value
best practice is use immutable types for symbol table keys

there are mulitiple key type.
if keys are comparable, use compareTo() to check key are same
if keys are any generic type, use equals() to test key, use hashcode() to scramble key

implementing equals for user-defined types

image.png image.png

how to implement a Symbol table

we can maintain a unordered linked list of key-value pair
but the time complexity for search and insert is both O (n)
if we use an ordered array, we can use binary search.
which could make search as log n, but insert still is O (n)

Ordered symbol table api

image.png

now to handle above problems, we need to use a new data structure.
binary search tree, simple called BST
BST is a binary tree in symmetric order
current node is larger than all keys in its left subtree, smaller than all keys in its right subtree

image.png

how search

if less, go left; if greater, go right; if equal, search hit.

how insert

if less, go left; if greater, go right; if null, insert

image.png

how to find min/max

go left until left child is null; go right until right child is null

floor and ceiling

image.png image.png

subtree count

image.png

rank

image.png

deletion

image.png

but hibbard deletion will not symmetric, trees not random -> sqrt(n) per op.

image.png

QUIZ

Q1

image.png

NaN == NaN, but not equals
0.0 equals -0.0, but not ==

Q2

image.png

two solution, first we can use inorder to check every element is in sorted order.
another is to pass a range into recursive function, in every function, we need to check the node is in the range, and dfs its left subtree with new range and same with right subtree.

Q3

image.png

there is an algorithm named morris.
the key thing is when we need iterate with left path, we need to add a link to its parent for backtracking.
when we at a node, we need to make it left child with rightmost child' right link to the parent. why because in inorder iteration, when we finished iterate this node, we need to go back to this place.
then we need to remove link and go right.
if we succefully add the link we need to go left. and do same thing.

so the basic plan is:

1. check this node's left child, if null, visit it, then go right
2. if not null, try add left child right most node right link to this node
3. if add success, go left
4. if add fail mean remove success(mean all the left subtree done), visit this node, then go right.

basic plan for AddOrRemoveLinkToParent

1. find the left's right most child
2. check it's right link == parent.
3. if == parent, remove link then return add is false.
4. if != parent, add link then return add is true

Q4

image.png

use symbol table of symobol table
<user , <website, times>>

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226