ADT and Tries
CSE 332 (Section 1)
Original slides by: Louis Maliyam • Monty Nitschke
IceBreakers!!
Abstract Data Type
(ADT)
ADT Recap
By the end of the quarter, you will get a good sense of what data structure is being implemented under the hood in order to satisfy behaviors of an ADT
Problem 0
Discuss with your group and do as much as you can
Problem 0(a)
You’re designing a tool that checks code to verify that all opening brackets, braces, parentheses, have closing counterparts.
Problem 0(a)
You’re designing a tool that checks code to verify that all opening brackets, braces, parentheses, have closing counterparts.
- A stack allows us to process the most recent match first
-For 351 veterans, the Linked List solution presents cache locality issues, though both are asymptotically the same
Problem 0(b)
Disneyland has hired you to find a way to improve the processing efficiency of their long lines at attractions. There is no way to forecast how long the lines will be.
Problem 0(b)
Disneyland has hired you to find a way to improve the processing efficiency of their long lines at attractions. There is no way to forecast how long the lines will be.
-We would use a queue since we want the first person in line to ride first
-Linked list with only a front pointer is going to become very slow for a long line
-Can argue that the Linked List with both pointers is better since we won’t have to resize the array as the line length changes
Problem 0(c)
A sandwich shop wants to serve customers in the order that they arrived, but also wants to look ahead to know what people have ordered.
Problem 0(c)
A sandwich shop wants to serve customers in the order that they arrived, but also wants to look ahead to know what people have ordered.
-We would use a queue since we process in the order that customers arrive
-We would choose an Array since this would efficiently allow us to take a look at anybody's order. (Also, there's probably a maximum capacity of customers that can be physically in the shop, so we don’t even need to worry about resizing in the long term)
Hypothetical Situation
USPS wants a simple tool where people can type in a zip code and see the location it corresponds to.
What data structure would you use?
Tries
Trie (Pronounced like “try”)
A Data Structure representing the ADT set
The set ADT supports the following operations:
Adding to a Trie
add(“sap”):
s
s
a
s
a
p
Adding to a Trie
add(“sad”):
s
s
a
a
p
p
d
Adding to a Trie
add(“awls”):
s
s
s
s
s
a
a
a
a
a
a
a
a
p
p
p
p
w
w
w
l
l
d
d
d
d
Adding to a Trie
s
s
a
a
p
w
l
d
add(“a”):
s
s
a
a
p
w
l
d
Searching in Tries
Removing from a Trie: Lazy Deletion
remove(“awls”):
s
s
a
a
p
w
l
d
m
e
s
s
a
a
p
w
l
d
m
e
Removing from a Trie: Normal Deletion
remove(“awls”):
s
s
a
a
p
w
l
d
m
e
s
a
a
p
w
l
d
m
e
s
a
a
p
w
d
m
e
s
a
a
p
d
m
e
Observation
The nodes in the trie currently only store if the key is in or not�(boolean value)
We can make it store arbitrary value, and use trie as a map
This is what you will do in P1
Problem 1
Trie to Delete 0’s and 1’s (TA)
0
0
0
0
0
0
0
1
1
1
1
1
1
1
Trie to Delete 0’s and 1’s (TA)
0
0
0
0
0
0
0
1
1
1
1
1
1
1
Trie to Delete 0’s and 1’s (TA)
0
0
0
0
0
0
0
1
1
1
1
1
1
1
Trie to Delete 0’s and 1’s (TA)
0
0
0
0
0
0
0
1
1
1
1
1
1
1
(b) After part a, if we deleted all binary numbers of length 3, how many nodes would we have to delete?
Trie to Delete 0’s and 1’s (TA)
0
0
0
0
0
0
0
1
1
1
1
1
1
1
(b) After part a, if we deleted all binary numbers of length 3, how many nodes would we have to delete? Ans: 12 (delete all nodes representing strings of length 2 and length 3)
Trie to Delete 0’s and 1’s (TA)
0
0
0
0
0
0
0
1
1
1
1
1
1
1
(b) After part a, if we deleted all binary numbers of length 3, how many nodes would we have to delete? Ans: 12 (delete all nodes representing strings of length 2 and length 3)
Trie to Delete 0’s and 1’s (TA)
0
0
0
1
1
1
(b) After part a, if we deleted all binary numbers of length 3, how many nodes would we have to delete? Ans: 12 (delete all nodes representing strings of length 2 and length 3)
Trie to Delete 0’s and 1’s (TA)
0
1
(b) After part a, if we deleted all binary numbers of length 3, how many nodes would we have to delete? Ans: 12 (delete all nodes representing strings of length 2 and length 3)