CSE 373 Section 4
AVL, Hashing, MT1 Review
MicroTeach: AVL Trees
Review: BST
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.
Balanced when the difference in height between sub trees is no greater than 1 for every node.
What exactly does balanced mean?
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.
Question 1: 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
AVL Rotation Walkthrough
General Approach
Rotation Strategies
�
Nice Rotation Animation
Problem 2B
insert(6)
Problem 2B
6
insert(6)
Problem 2B
6
insert(6)
Problem 2B
6
insert(43)
Problem 2B
6
insert(43)
43
Problem 2B
6
insert(43)
43
Problem 2B
6
insert(7)
43
Problem 2B
6
insert(7)
43
7
Problem 2B
6
insert(7)��Kink!
43
7
Problem 2B
6
insert(7)��Kink!��Step 1...
7
43
Problem 2B
6
insert(7)��Kink!��Step 2...
7
43
Problem 2B
6
insert(7)
7
43
Problem 2B
6
insert(42)
7
43
Problem 2B
6
insert(42)��
7
43
42
Problem 2B
6
insert(42)��
7
43
42
Problem 2B
6
insert(59)��
7
43
42
Problem 2B
6
insert(59)��
7
43
42
59
Problem 2B
6
insert(59)��
7
43
42
59
Problem 2B
6
insert(63)��
7
43
42
59
Problem 2B
6
insert(63)��
7
43
42
59
63
Problem 2B
6
insert(63)��
7
43
42
59
63
Problem 2B
6
insert(63)
Straight!��
7
43
42
59
63
Problem 2B
6
insert(63)
Straight!��
7
43
42
59
63
Problem 2B
6
insert(63)
��
7
43
42
59
63
Problem 2B
6
insert(11)
7
43
42
59
63
Problem 2B
6
insert(11)
7
43
42
59
63
11
Problem 2B
6
insert(11)
7
43
42
59
63
11
Problem 2B
6
insert(21)
7
43
42
59
63
11
Problem 2B
6
insert(21)
7
43
42
59
63
11
21
Problem 2B
6
insert(21)��
7
43
42
59
63
11
21
Problem 2B
6
insert(21)��Kink!
7
43
42
59
63
11
21
Problem 2B
6
insert(21)��Kink!
Step 1...
7
43
42
59
63
21
11
Problem 2B
6
insert(21)��Kink!
Step 2...
7
43
21
59
63
11
42
Problem 2B
6
insert(21)��
7
43
21
59
63
11
42
Problem 2B
6
insert(56)��
7
43
21
59
63
11
42
Problem 2B
6
insert(56)�
7
43
21
59
63
11
42
56
Problem 2B
6
insert(56)�
7
43
21
59
63
11
42
56
Problem 2B
6
insert(54)�
7
43
21
59
63
11
42
56
Problem 2B
6
insert(54)�
7
43
21
59
63
11
42
56
54
Problem 2B
6
insert(54)�
7
43
21
59
63
11
42
56
54
Problem 2B
6
insert(27)�
7
43
21
59
63
11
42
56
54
Problem 2B
6
insert(27)�
7
43
21
59
63
11
42
56
54
27
Problem 2B
6
insert(27)�
7
43
21
59
63
11
42
56
54
27
Problem 2B
6
insert(27)
Straight!�
7
43
21
59
63
11
42
56
54
27
Problem 2B
6
insert(27)
Straight!�
7
43
21
59
63
11
42
56
54
27
Problem 2B
6
insert(27)
7
43
21
59
63
11
42
56
54
27
Problem 2B
6
insert(20)
�
7
43
21
59
63
11
42
56
54
27
Problem 2B
6
insert(20)
�
7
43
21
59
63
11
42
56
54
27
20
Problem 2B
6
insert(20)
�
7
43
21
59
63
11
42
56
54
27
20
Problem 2B
6
insert(36)
�
7
43
21
59
63
11
42
56
54
27
20
Problem 2B
6
insert(36)
�
7
43
21
59
63
11
42
56
54
27
20
36
Problem 2B
6
insert(36)
�
7
43
21
59
63
11
42
56
54
27
20
36
Problem 2B
6
insert(36)
�Kink!
�
7
43
21
59
63
11
42
56
54
27
20
36
Problem 2B
6
insert(36)
�Kink!��Step 1..
�
7
43
21
59
63
11
42
56
54
36
20
27
Problem 2B
6
insert(36)
�Kink!��Step 2..
�
7
43
21
59
63
11
36
56
54
27
20
42
Problem 2B
6
�
7
43
21
59
63
11
36
56
54
27
20
42
Problem 2B
6
�
7
43
21
59
63
11
36
56
54
27
20
42
Questions?
MicroTeach: Hashing Intro
Hash Tables
One way to implement the dictionary ADT.
(Your ArrayMap from Project 2 is another, by the way!)
Stores item with key x in array index (or “bucket”) h(x).�(The choice of h(x)is important for many reasons.)��
Collisions?
One approach: Separate chaining uses Linked Lists to handle collisions.
0
1
3124
4583
20382827
553256591
553256592
snack
...
...
potato
rotato
totato
dog
cat
...
...
Using Mod (Compression)
We use the modulus of the hashcode when it exceeds the number of buckets.
0
1
2
3
4
5
6
7
8
9
Q: If we use the 10 buckets below, where should our six items go?�
A: Put in bucket = h(x) % 10
potato
rotato
totato
snack
0
1
3124
4583
20382827
553256591
553256592
snack
...
...
potato
rotato
totato
dog
cat
...
...
cat
dog
Hash Function Quality
Observation: The more h(x)evenly distributes the keys, the faster get is! (Why?)
0
1
2
3
4
5
6
7
8
9
potato
rotato
totato
snack
0
1
3124
4583
20382827
553256591
553256592
snack
...
...
potato
rotato
totato
dog
cat
...
...
cat
dog
#5) Hash table Insertion
Problem 5a: Hash table Insertion
| | | | | | | | | | | |
Problem 5a: Hash table Insertion
Input: 0
h(x) = 4x
First go through hash function: 0 * 4 = 0
0 % (array.length) => 0 % 12
=> Item inserted at Index 0
0 | | | | | | | | | | | |
Problem 5a: Hash table Insertion
Input: 4
h(x) = 4x
First go through hash function: 4 * 4 = 16
16 % (array.length) => 16 % 12
=> Item inserted at Index 4
0 | | |
| 4 | | | | | | | |
Problem 5a: Hash table Insertion
Input: 7
h(x) = 4x
First go through hash function: 7 * 4 = 28
28 % (array.length) => 28 % 12 = 4
=> Item inserted at Index 4
0 | | |
| 7 -> 4 | | | | | | | |
Problem 5a: Hash table Insertion
Input: 1
h(x) = 4x
First go through hash function: 1 * 4 = 4
4 % (array.length) => 4 % 12 = 4
=> Item inserted at Index 4
0 | | |
| 1 -> 7 -> 4 | | | |
| | | |
Problem 5a: Hash table Insertion
Input: 2
h(x) = 4x
First go through hash function: 2 * 4 = 8
8 % (array.length) => 8 % 12 = 8
=> Item inserted at Index 8
0 | | |
| 1 -> 7 -> 4 | | | | 2 | | | |
0 1 2 3 4 5 6 7 8 9 10 11
Problem 5a: Hash table Insertion
Input: 3
h(x) = 4x
First go through hash function: 3 * 4 = 12
12 % (array.length) => 12 % 12 = 0
=> Item inserted at Index 0
3 -> 0 | | |
| 1 -> 7 -> 4 | | | | | | | |
0 1 2 3 4 5 6 7 8 9 10 11
Problem 5a: Hash table Insertion
Input: 6
h(x) = 4x
First go through hash function: 6 * 4 = 24
24 % (array.length) => 24 % 12 = 0
=> Item inserted at Index 0
6 -> 3 -> 0 | | |
| 1 -> 7 -> 4 | | | | 2 | | | |
0 1 2 3 4 5 6 7 8 9 10 11
Problem 5a: Hash table Insertion
Input: 11
h(x) = 4x
First go through hash function: 11 * 4 = 44
44 % (array.length) => 44 % 12 = 8
=> Item inserted at Index 0
6 -> 3 -> 0 | | |
| 1 -> 7 -> 4 | | | | 11 -> 2 | | | |
0 1 2 3 4 5 6 7 8 9 10 11
Problem 5a: Hash table Insertion
Input: 16
h(x) = 4x
First go through hash function: 16 * 4 = 64
64 % (array.length) => 64 % 12 = 4
=> Item inserted at Index 0
6 -.> 3 -> 0 | | |
| 16 -> 1 -> 7 -> 4 | | | | 2 | | | |
0 1 2 3 4 5 6 7 8 9 10 11
Problem 5a: Hash table Insertion
Now repeat….
Problem 5d: Hash Table With Separate Chaining
Remeber you use hash function with key not with value!
Problem 5d: Hash Table With Separate Chaining
Input: (1,a)
Hash function: h(x) = x
h(1) = 1
1 % 10 = 1
| (1,a) | | | | | | | | |
0 1 2 3 4 5 6 7 8 9
Problem 5d: Hash Table With Separate Chaining
Input: (4,b)
Hash function: h(x) = x
h(4) = 4
4 % 10 = 4
| (1,a) | | | (4,b) | | | | | |
Problem 5d: Hash Table With Separate Chaining
Input: (2,c)
Hash function: h(x) = x
h(2) = 2
2 % 10 = 2
| (1,a) | (2,c) | | (4,b) | | | | | |
Problem 5d: Hash Table With Separate Chaining
Input: (17,d)
Hash function: h(x) = x
h(17) = 17
17 % 10 = 7
| (1,a) | (2,c) | | (4,b) | | | (17, d) | | |
Problem 5d: Hash Table With Separate Chaining
Input: (12,e)
Hash function: h(x) = x
h(12) = 12
12 % 10 = 2
| (1,a) | (2,c)
(12,e) | | (4,b) | | | (17, d) | | |
Problem 5d: Hash Table With Separate Chaining
Input: (9,e)
Hash function: h(x) = x
h(9) = 9
9 % 10 = 9
| (1,a) | (2,c)
(12,e) | | (4,b) | | | (17, d) | | (9,e) |
Problem 5d: Hash Table With Separate Chaining
Input: (19,f)
Hash function: h(x) = x
h(19) = 19
19 % 10 = 9
| (1,a) | (2,c)
(12,e) | | (4,b) | | | (17, d) | | (9,e) (19,f) |
Problem 5d: Hash Table With Separate Chaining
Input: (4,g)
Hash function: h(x) = x
h(4) = 4
4 % 10 = 4
| (1,a) | (2,c)
(12,e) | | (4,g) | | | (17, d) | | (9,e) (19,f) |
Since the key already exists, we update its value!
Problem 5d: Hash Table With Separate Chaining
Input: (8,c)
Hash function: h(x) = x
h(8) = 8
8 % 10 = 8
| (1,a) | (2,c)
(12,e) | | (4,g) | | | (17, d) | (8,c) | (9,e) (19,f) |
Problem 5d: Hash Table With Separate Chaining
Input: (12,f)
Hash function: h(x) = x
h(12) = 12
12 % 10 = 2
| (1,a) | (2,c)
(12,f) | | (4,g) | | | (17, d) | (8,c) | (9,e) (19,f) |
Problem 5d: Hash Table With Separate Chaining
#6a Evaluating Hash Functions
Problem 6a: Evaluating Hash Functions
Problem 6a: Evaluating Hash Functions
h(x) = 4x
0 1 2 3 4 5 6 7 8 9 10 11
Issue with the hash function:
Keys will initially only be hashed to at most one of three spots
Collisions are very likely, decreasing performance!
0
6
93
1
7
94
2
8
95
Problem 6a: Evaluating Hash Functions
h(x) = 4x
0 1 2 3 4 5 6 7 8 9 10 11
Issue with the resize:
12 13 14 15 16 17 18 19 20 21 22 23
We still only map to a fourth of the available indices!
Problem 6a: Evaluating Hash Functions
Possible Fixes?
Prime numbers will almost always improve our hashing!
Challenge Problem
Implement Binary Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized
with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Implement Binary Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized
with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Constraints:
Implement Binary Tree Iterator Solution
Understanding Constraints
We can perhaps use stack which is Last In First Out and it can satisfy the average O(1) time by popping each item. One can also use the list and remove and return the last element in the list.
Implement Binary Tree Iterator Solution
we start this off by adding the left sub-tree nodes to our stack. Iterating through the left
subtree and then the right subtree, we will be able to traverse maintaining desirable order.
In class design questions, we need to consider how we can maximize the use of constructors. We know that we need to traverse the left subtrees of root before traversing any other path of the tree. Therefore, we can simply process the left subtree tree into the queue first.
Implement Binary Tree Iterator Solution
Code Solution:
https://docs.google.com/document/d/1G-MmAn3a2_JIlSq4rlC974wCsXMMakKXcJSlOKkZBVE/edit?usp=sharing