Chapter 4, 5
10 points
1) Draw a red-black tree for the following values inserted in this order. Illustrate each operation that occurs: k w o s y t p r
10 points
2) Draw a red-black tree for the following values inserted in this order. Illustrate each operation that occurs: 30 20 11 28 16 13 55 52 26 50 87
10 points
3) Draw a 2-3-4 B-tree that corresponds to your red-black tree in problem #2.
Use a tablesize of 13 for these hashing questions:
10 points
4) Given the input {3823, 8806, 8783, 2850, 3593, 8479, 1941, 4290, 8818, 7413} and a hash function h(x) = x mod 13, show the resulting separate chaining table.
10 points
5) Repeat #4 using open addressing with linear probing.
10 points
6) Repeat #4 using open addressing with quadratic probing.
10 points
7) Repeat #4 using open addressing with double hashing where the second hash function is 11 - (x mod 11).
10 points
8) Suppose these names have the following hash values. Insert them into the extendible hash table shown below. Each leaf can only hold 4 entries. Note that the first two names have already been inserted. Illustrate each operation that occurs.
Bob 0100
Sue 1000
Tim 1110
Ron 0010
Ann 1010
Jan 1101
Ben 0001
Don 0101
Tom 1111
Sam 1011
---------------
| 0 | 1 |
---------------
/ \
---------- ---------- | (1) | | (1) |
| Bob 0100 | | Sue 1000 |
| | | |
| | | |
| | | | ---------- ----------
10 points
9) Using Cuckoo hashing, hash the following keys using the (h1,h2) pairs shown.
A: 2,0
B: 0,0
C: 4,1
D: 0,1
E: 2,3
10 points
10) Using Hopscotch hashing with a max hop of 4, hash the following keys.
A: 6
B: 7
C: 9
D: 7
E: 6
F: 7
G: 8
Submit to eLearning: hw5.doc (.doc can be .txt, .jpg, etc.)
