LLRB and hash tables

Problème 1.

Consider the sequence of values $S=[3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$

1.1

Draw a left-leaning red-black tree obtained by adding the values in S in sequence. Show each step.

Let the following format as node: [R|B]-<value> where [R|B] denotes whether the node is red or black, followed by its value.

The left-leaning red-black tree obtained by adding the values in S in sequence is as follows:

1. $S=[3]$

B-3

2. $S=[3, 42]$ New node become red, 42

B-3
  \
   R-42

3. $S=[3, 42, 39]$ New root 39, rotate color for 3, 42

  B-39
 /    \
R-3   R-42

4. $S=[3, 42, 39, 86]$ Add 86, rotate color for tree

  B-39
 /    \
R-3   R-42
        \
        R-86

5. $S=[3, 42, 39, 86, 49]$ Add 49, rotate color for tree 49, 42

  B-39
 /    \
R-3   R-49
      /  \
    R-42   R-86

6. $S=[3, 42, 39, 86, 49, 89]$ Add 89, rotate color for 42, 86

  B-39
 /    \
R-3   R-49
      /  \
    B-42  B-86
            \
           R-89

7. $S=[3, 42, 39, 86, 49, 89, 99]$ Add 99, rotate color for 86, 89

  B-39
 /    \
R-3   R-49
      /  \
    B-42  B-89
          /  \
        R-86 R-89

8. $S=[3, 42, 39, 86, 49, 89, 99, 20]$ Add 20, right of 3, red. Rotate color of 3

      B-39
     /    \
    B-3   R-49
     |    |   \
    R-20 B-42 B-89
              /  \
            R-86 R-89

9. $S=[3, 42, 39, 86, 49, 89, 99, 20, 88]$ Add 88, correct root of 49, balance tree to L-39. R-89

      B-49
     /    \
    R-39   R-89
    /  |    |   \
  B-3 R-42 B-86 B-99
   |        |
  R-20     R-88

10. $S=[3, 42, 39, 86, 49, 89, 99, 20, 88, 51]$ Add 51, left of 86

      B-49
     /    \
    R-39   R-89
    /  |    |   \
  B-3 R-42 B-86 B-99
   |       /  \
R-20     R-51 R-88

11. $S=[3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$ Add 64, 86 comes red, 64 becomes right of 51, rotate color 51, 88, 86

      B-49
     /    \
    R-39   R-89
    /  |    |   \
  B-3 R-42 R-86 B-99
   |       /  \
R-20     B-51 B-88
          |
         R-64

1.2

Consider the hash function $h(x) = (x+7) \text{ mod } 13$ a hash-table of 13 table entries that uses hashing with separate chaining. Draw the hash-table obtained by adding the values in $S$ in sequence. Show each step.

The hash-table obtained by adding the values in $S$ in sequence is as follows:

1. $S=[3]$ $h(3) = 10 \text{ mod } 13 = 10$

0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10: 3
11:
12:

2. $S=[3, 42]$ $h(42) = 49 \text{ mod } 13 = 10$ Collision with 3, chaining with 3

0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10: 3 -> 42
11:
12:

3. $S=[3, 42, 39]$ $h(39) = 46 \text{ mod } 13 = 7$

0:
1:
2:
3:
4:
5:
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:

4. $S = [3, 42, 39, 86]$ $h(86) = 93 \text{ mod } 13 = 2$

0:
1:
2: 86
3:
4:
5:
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:

5. $S = [3, 42, 39, 86, 49]$ $h(49) = 56 \text{ mod } 13 = 4$

0:
1:
2: 86
3:
4: 49
5:
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:

6. $S = [3, 42, 39, 86, 49, 89]$ $h(89) = 96 \text{ mod } 13 = 5$

0:
1:
2: 86
3:
4: 49
5: 89
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:

7. $S = [3, 42, 39, 86, 49, 89, 99]$ $h(99) = 106 \text{ mod } 13 = 2$ Collide with 86, chaining with 86

0:
1:
2: 86 -> 99
3:
4: 49
5: 89
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:

8. $S = [3, 42, 39, 86, 49, 89, 99, 20]$ $h(20) = 27 \text{ mod } 13 = 1$

0:
1: 27
2: 86 -> 99
3:
4: 49
5: 89
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:

9. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88]$ $h(88) = 95 \text{ mod } 13 = 4$ Collide with 49, chaining with 49

0:
1: 27
2: 86 -> 99
3:
4: 49 -> 88
5: 89
6:
7: 39
8:
9:
10: 3 -> 42
11:
12:

10. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51]$ $h(51) = 58 \text{ mod } 13 = 6$

0:
1: 27
2: 86 -> 99
3:
4: 49 -> 88
5: 89
6: 51
7: 39
8:
9:
10: 3 -> 42
11:
12:

11. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$ $h(64) = 71 \text{ mod } 13 = 6$ Collide with 51, chaining with 51

0:
1: 27
2: 86 -> 99
3:
4: 49 -> 88
5: 89
6: 51 -> 64
7: 39
8:
9:
10: 3 -> 42
11:
12:

1.3

Consider the hash function $h(x) = (x+7) \text{ mod } 13$ a hash-table of 13 table entries that uses hashing with linear probing. Draw the hash-table obtained by adding the values in $S$ in sequence. Show each step.

1. $S=[3]$ $h(3) = 10 \text{ mod } 13 = 10$

0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10: 3
11:
12:

2. $S=[3, 42]$ $h(42) = 49 \text{ mod } 13 = 10$ Collision with 3, increment index to 11

0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10: 3
11: 42
12:

3. $S=[3, 42, 39]$ $h(39) = 46 \text{ mod } 13 = 7$

0:
1:
2:
3:
4:
5:
6:
7: 39
8:
9:
10: 3
11: 42
12:

4. $S = [3, 42, 39, 86]$ $h(86) = 93 \text{ mod } 13 = 2$

0:
1:
2: 86
3:
4:
5:
6:
7: 39
8:
9:
10: 3
11: 42
12:

5. $S = [3, 42, 39, 86, 49]$ $h(49) = 56 \text{ mod } 13 = 4$

0:
1:
2: 86
3:
4: 49
5:
6:
7: 39
8:
9:
10: 3
11: 42
12:

6. $S = [3, 42, 39, 86, 49, 89]$ $h(89) = 96 \text{ mod } 13 = 5$

0:
1:
2: 86
3:
4: 49
5: 89
6:
7: 39
8:
9:
10: 3
11: 42
12:

7. $S = [3, 42, 39, 86, 49, 89, 99]$ $h(99) = 106 \text{ mod } 13 = 2$ Collide with 86, increment index to 3

0:
1:
2: 86
3: 99
4: 49
5: 89
6:
7: 39
8:
9:
10: 3
11: 42
12:

8. $S = [3, 42, 39, 86, 49, 89, 99, 20]$ $h(20) = 27 \text{ mod } 13 = 1$

0:
1: 27
2: 86
3: 99
4: 49
5: 89
6:
7: 39
8:
9:
10: 3
11: 42
12:

9. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88]$ $h(88) = 95 \text{ mod } 13 = 4$ Collide with 49, index to 5 at 5, collide with 89, index to 6

0:
1: 27
2: 86
3: 99
4: 49
5: 89
6: 88
7: 39
8:
9:
10: 3
11: 42
12:

10. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51]$ $h(51) = 58 \text{ mod } 13 = 6$ Collide with 88, index to 7 at 7, collide with 39, index to 8

0:
1: 27
2: 86
3: 99
4: 49
5: 89
6: 88
7: 39
8: 51
9:
10: 3
11: 42
12:

11. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$ $h(64) = 71 \text{ mod } 13 = 6$ Collide with 88, index to 7 at 7, collide with 39, index to 8 at 8, collide with 51, index to 9

0:
1: 27
2: 86
3: 99
4: 49
5: 89
6: 88
7: 39
8: 51
9: 64
10: 3
11: 42
12:

Problème 2.

Consider a list $L$ of $N$ sorted values. Show how to construct a valid left-leaning red-black tree holding the values in $L$ in $\Theta(N)$

Solution

The following depicts the pseudocode implementation of the program

$"\\begin{algorithm}\n\\caption{BuildLLRBTree($L, \\text{start}, \\text{end}$)}\n\\begin{algorithmic}\n\\IF{$\\text{start} > \\text{end}$}\n \\RETURN $NULL$\n\\ENDIF\n\\STATE $\\text{mid} \\gets (start + end) / 2$\n\\STATE $\\text{left} \\gets BuildLLRBTree(L, start, mid-1)$\n\\STATE $\\text{right} \\gets BuildLLRBTree(L, mid+1, end)$\n\\STATE $\\text{node} \\gets$ new Node($L[mid]$)\n\\STATE $\\text{node.left} \\gets left$\n\\STATE $\\text{node.right} \\gets right$\n\\STATE $\\text{node.color} \\gets \\text{BLACK}$\n\\RETURN $node$\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 30 BuildLLRBTree($L, \text{start}, \text{end}$)

1:if $\text{start} > \text{end}$ then

2:return $NULL$

3:end if

4:$\text{mid} \gets (start + end) / 2$

5:$\text{left} \gets BuildLLRBTree(L, start, mid-1)$

6:$\text{right} \gets BuildLLRBTree(L, mid+1, end)$

7:$\text{node} \gets$ new Node($L[mid]$)

8:$\text{node.left} \gets left$

9:$\text{node.right} \gets right$

10:$\text{node.color} \gets \text{BLACK}$

11:return $node$

Problème 3.

Consider a set of strings $S$. We want to figure out whether $S$ has duplicates efficiently. We do not want to do so by sorting $S$ and then checking for duplicates: comparing strings can be a lot of work (e.g., they might differ in only a single character). Assume that you have a hash function $h$ that can compute a suitable hash code for any string $s \in S$ in $\mathcal{O}(|s|)$. Show how one can use hashing to find whether $S$ has duplicates without performing many comparisons between strings. Your algorithm should have an expected runtime of $\mathcal{O}(|S|)$ in which $|S| = \sum_{s \in S}|s|$ represents the total length of all strings in $S$.

Solution

$"\\begin{algorithm}\n\\caption{Check for Duplicates Using Hashing}\n\\begin{algorithmic}\n\\Require A set of strings $S$\n\\Ensure True if there are duplicates in $S$, False otherwise\n\\State Initialize an empty hash table $H$\n\\For{each string $s \\in S$}\n \\State Compute $h(s)$ using the hash function\n \\If{$h(s)$ is in $H$}\n \\For{each string $s' \\in H[h(s)]$}\n \\If{$s = s'$}\n \\State \\Return True\n \\EndIf\n \\EndFor\n \\State Append $s$ to $H[h(s)]$\n \\Else\n \\State Insert $s$ into $H$ at $h(s)$\n \\EndIf\n\\EndFor\n\\State \\Return False\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 31 Check for Duplicates Using Hashing

Require: A set of strings $S$

Ensure: True if there are duplicates in $S$, False otherwise

1:Initialize an empty hash table $H$

2:for each string $s \in S$ do

3:Compute $h(s)$ using the hash function

4:if $h(s)$ is in $H$ then

5:for each string $s' \in H[h(s)]$ do

6:if $s = s'$ then

7:

8:return True

9:end if

10:end for

11:Append $s$ to $H[h(s)]$

12:else

13:Insert $s$ into $H$ at $h(s)$

14:end if

15:end for

16:

17:return False