Princeton Alogorithm COS226 Week
we already learnt red-black BST, and hash table.
is there a way we can do better?
yes, if we can avoid examining the entire key, as with string sorting.
image.png
Trie
image.png
image.png
image.png
image.png
JAVA implementation
image.png
image.png
popular interview question: design a data structure to perform efficient spell checking.
solution: build a 26-way trie(key = word, value = bit)
deletion in a trie
first, find the node corresponding to key and set value to null
second, if node has null value and null links, remove that node (and recur)
image.png
but the drawback of R-WAY trie is the memory
image.png
less memory trie
image.png
image.png
search hit
image.png
search miss
image.png
image.png
image.png
if we could combine the faster time of R-way Trie and less memory of Tenary search tree
image.png
TST vs Hashing
Hashing:
need to examine entire key
search hits and misses cost about the same
performance relies on hash function
does not support ordered symbol table operations
TSTs:
works only for strings (or digital keys)
only examines just enough key characters
search miss may involve only a few characters
supports ordered symbol table operations (plus others)
TST faster than hashing especially for search misses
ordered iteration
to iterate through all keys in sorted order:
do inorder traversal of trie;; add keys encountered to a queue.
maintain sequence of characters on path from root to node.
image.png
Longest prefix
image.png
add this implementation in extra credit
T9 texting
image.png
add this implementation in extra credit
Patricia trie(radix tree)
remove one-way branching; each node represents a sequence of characters;
image.png
add this implementation in extra credit
suffix tree
Patricia trie of suffixes of a string
image.png
QUIZ
Q1 Prefix free codes
image.png
insert the binary strings into a 2-way trie. then during insert check the path could not have the node which have value, and when it reach end, there should not exists more children in the node.
Q2 Boggle
image.png
same as project
Q3 Suffix trees
image.png
to be done in the future
course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226
