CSE 373 SU23 Section 4
Trees
Agenda
Announcements
Mon (7/10) | Tues (7/11) | Wed (7/12) | Thurs (7/13) | Fri (7/14) | Sat (7/15) |
| | EX2 due @ 11:59 pm | | EX2 late due @ 11:59 pm |
|
Mon (7/17) | Tues (7/18) | Wed (7/19) | Thurs (7/20) | Fri (7/21) | Sat (7/22) |
| | EX3 due @ 11:59 pm | | P2 due @ 11:59 pm EX3 late due @ 11:59 pm | |
MicroTeach: AVL Trees
Review: Binary Search Trees
Binary Search Trees (BSTs) are sorted trees, where each node has a left and right child
BST Invariants
But, a problem...
Normal BSTs can become unbalanced.��So find is slow.
What exactly does balanced mean?
For every node, compare the heights of its two sub trees.
The tree is balanced when the difference in height between sub trees is no greater than 1 for every node.
Note: Balanced tree with n items has height of O(log(n)).
Solution: AVL Trees
These special BSTS remain balanced no matter what order items are inserted in.��They do this by rebalancing themselves using rotations each time an item gets inserted.
Don’t forget to check out the AVL rotation walkthrough too!
Question 1A-C: Valid BST/AVL
Problem 1A
6
Valid BST?
7
43
2
Problem 1A
Valid BST?
No!
6
7
43
2
Problem 1A
Valid AVL?
6
7
43
2
Problem 1A
Valid AVL?
No!
(Must be BST to be AVL!)
6
7
43
2
Problem 1B
Valid BST?
6
7
43
42
59
63
11
21
Problem 1B
Valid BST?
Yes!
6
7
43
42
59
63
11
21
Problem 1B
Valid AVL?
6
7
43
42
59
63
11
21
Problem 1B
Valid AVL?
No!
42 violates
Balance condition.
6
7
43
42
59
63
11
21
Problem 1C
Valid BST?
6
7
43
21
59
63
11
42
Problem 1C
Valid BST?
Yes!
6
7
43
21
59
63
11
42
Problem 1C
Valid AVL?
6
7
43
21
59
63
11
42
Problem 1C
Valid AVL?��Yes!
6
7
43
21
59
63
11
42
Problem 5A-C: AVL Big-O
5A: BigO
Write down a tight big-O for each of the following. Unless otherwise noted, give a bound in the worst case
(a) Insert and find in a BST
� �
5A: Big O
(a) Insert and find in a BST.
Worst Case: Linked List like Tree (Degenerate Tree)
Insert: Inserting biggest/smallest item at the bottom of the tree = O(n)
Find: Finding Biggest/smallest item in the skewed binary tree = O(n)
5B: Big O
Write down a tight big-O for each of the following. Unless otherwise noted, give a bound in the worst case
� �
(b) Insert and find in AVL Tree
�
5B: Big O
(a) Insert and find in AVL Tree
Let’s think about worst case: Insert/find at the bottom of our tree
Insert: Balanced tree has a height of log(N) = O(log n)
Find: Balanced tree has a height of log(N) = O(log n)
5C: Big O
Write down a tight big-O for each of the following. Unless otherwise noted, give a bound in the worst case
� �
(c) Finding the minimum value in an AVL tree containing
N elements
�
5C: Big O
(c) Finding the minimum value in an AVL tree containing N elements
Find: AVL tree is balanced.
Find value by starting from root and traverse to the left most branch = O(log n)
� �
Problem 6A-C: Analyzing Dictionary Implementations
Problem 6a)
a) What are the constraints on the data types you can store in an AVL Tree?
Keys needs to be comparable!�
Since AVL trees maintain their keys in sorted order, we have to be able to compare keys to decide whether to go left or right at each node.
Note that there are no restrictions on our value’s data type since AVL trees order data by keys, not values.
Problem 6b)
b) When is using an AVL tree preferred over a hash table?
*Caveat: In practice, you avoid this worst case scenario by
having a good hash function.
One Example: Better worst case for get()! AVL trees guarantee O(log n) at all times. A hash table in the worst case, where every key is added to the same bucket, takes O(n) time.
Problem 6c)
c) When is using a BST preferred over an AVL tree?
MicroTeach: Tries
Trie (Pronounced like “try”)
A Data Structure that represents the dictionary or set ADT
In order for a Trie to implement one of those ADTs, it needs the following functionalities:
Adding to a Trie
s
add(“sap”)
s
a
s
a
p
Adding to a Trie
add(“sad”)
s
a
p
s
a
p
d
Adding to a Trie
add(“awls”)
s
a
p
d
a
s
a
p
d
a
w
s
a
p
d
a
w
l
s
a
p
d
a
w
l
s
Adding to a Trie
add(“a”)
s
a
p
d
a
w
l
s
s
a
p
d
a
w
l
s
Searching in Tries
Removing from a Trie: Lazy Deletion
remove(“awls”)
s
a
p
d
a
w
l
s
m
e
s
a
p
d
a
w
l
s
m
e
Removing from a Trie: Normal Deletion
remove(“awls”)
s
a
p
d
a
w
l
s
m
e
s
a
p
d
a
w
l
m
e
s
a
p
d
a
w
m
e
s
a
p
d
a
m
e
Trie Problem 1: Trie to Delete 0’s and 1’s?
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? 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? 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? 12 (delete all nodes representing strings of length 2 and length 3)
Problem 2a-c): Call Me Maybe
Problem 2a)
a) Suppose you want to transfer someone’s phone book to a data structure so that you can access all the phone numbers with a particular area code efficiently. What data structure would you use? How would you implement it? There are a few answers here.
Problem 2b)
b) What is the (in-practice) time complexity of your solution?
Problem 2c)
c) What is the space complexity?
Problem 3): Let’s Trie to be Old School
Problem 3)
Problem 3)