## Description

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.

1

5

8

3

5

3

4

0

4

3

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.)