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