CPSC 461: Copyright © 2002 Katrin Becker 1998-2002 Last Modified November 14, 2002 03:25 PM

Hashing: Collision Resolution: Binary Tree Insertion [1]

Record Keys: 27, 18, 29, 28, 39, 13, 16, 41, 17, 19

Table Size = 11; Hash Function = hash(key) = key mod 11

Incrementing Function = i(key) = Quotient (Key / 11) mod 11

| Key |
0 |  |
1 |  |
2 |  |
3 |  |
4 |  |
5 | 27 | 1. 27 mod 11 = 5
6 |  |
7 | 18 | 2.18 mod 11 = 7; 3. 29 mod 11 = 7; collision so generate tree (pp1)
8 |  | i(29) = 2 so next loc is 9; put it there.
9 |  |
10 |  |

| Key |
0 |  |
1 |  |
2 |  |
3 |  |
4 |  |
5 | 27 |
6 | 28 | 4. 28 mod 11 = 6; insert; 5. 39 mod 11 = 6 - collision; build tree
7 | 18 | tree says move 28 to loc8 and insert 39 at loc6
8 |  |
9 | 29 |
10 |  |

| Key |
0 |  |
1 |  |
2 | 13 | 6. 13 mod 11 = 2; insert
3 |  |
4 |  |
5 | 27 | 7. 16 mod 11 = 5; collision; build tree; result of tree says move 39 to
6 | 39 | loc1 and insert 16 at loc6
7 | 18 |
8 | 28 |
9 | 29 |
10 |  |

| Key |
0 | 41 |
1 | 39 |
2 | 13 |
3 |  |
4 |  |
5 | 27 |
6 | 16 | 9. 17 mod 11 = 6; collision; generate tree; move 28 from loc8 to loc10
7 | 18 | and insert 17 at loc8
8 | 28 | 8. 41 mod 11 = 8; collision; i(41) = 3; gets inserted at loc0
9 | 29 |
10 |  |

| Key |
0 | 41 |
1 | 39 |
2 | 13 |
3 |  |
4 |  |
5 | 27 |
6 | 16 |
7 | 18 |
8 | 17 | 10. 19 mod 11 = 8; collision; build another tree; move 41 from loc0 to
9 | 29 | to loc3; move 29 from loc9 to loc0; insert 19 at loc9
10 | 28 |

| Key | After the move, final tree.
0 | 29 |
1 | 39 |
2 | 13 |
3 | 41 |
4 |  |
5 | 27 |
6 | 16 |
7 | 18 |
8 | 17 |
9 | 19 |
10 | 28 |

CPSC 461: Copyright © 2002 Katrin Becker 1998-2002 Last Modified November 14, 2002 03:25 PM