---
date: '2024-02-26'
description: assignment on left-leaning red-black trees, hash tables with separate chaining and linear probing, duplicate detection using hashing.
id: A6
modified: 2026-06-05 15:08:41 GMT-04:00
tags:
  - sfwr2c03
title: LLRB and hash tables
created: '2024-02-26'
published: '2024-02-26'
pageLayout: default
slug: thoughts/university/twenty-three-twenty-four/sfwr-2c03/a6/A6
permalink: https://aarnphm.xyz/thoughts/university/twenty-three-twenty-four/sfwr-2c03/a6/A6.md
generator:
  quartz: v4.6.0
  hostedProvider: Cloudflare
  baseUrl: aarnphm.xyz
full: https://aarnphm.xyz/llms-full.txt
---
## Problème 1.

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

> \[!question\] 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]$

```plaintext
B-3
```

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

```plaintext
B-3
  \
   R-42
```

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

```plaintext
  B-39
 /    \
R-3   R-42
```

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

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

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

```plaintext
  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

```plaintext
  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

```plaintext
  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

```plaintext
      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

```plaintext
      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

```plaintext
      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

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

> \[!question\] 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$

```plaintext
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

```plaintext
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$

```plaintext
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$

```plaintext
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$

```plaintext
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$

```plaintext
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

```plaintext
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$

```plaintext
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

```plaintext
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$

```plaintext
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

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

> \[!question\] 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$

```plaintext
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

```plaintext
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$

```plaintext
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$

```plaintext
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$

```plaintext
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$

```plaintext
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

```plaintext
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$

```plaintext
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

```plaintext
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

```plaintext
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

```plaintext
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

<div class="ps-root" data-inline-macros=""><span type="button" class="clipboard-button ps-clipboard" aria-label="Copy pseudocode to clipboard"><svg width="16" height="16" viewBox="0 0 16 16" class="copy-icon"><use href="#github-copy"></use></svg><svg width="16" height="16" viewBox="0 0 16 16" class="check-icon"><use href="#github-check" fill-rule="evenodd" fill="rgb(63, 185, 80)"></use></svg></span><span class="ps-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><annotation encoding="application/x-tex">"\\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}"</annotation></semantics></math></span>
<div class="ps-algorithm with-caption">
<p class="ps-line" style="text-indent:-0.6em;padding-left:0.6em;">
<span class="ps-keyword">Algorithm 30 </span>BuildLLRBTree(<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>L</mi><mo separator="true">,</mo><mtext>start</mtext><mo separator="true">,</mo><mtext>end</mtext></mrow><annotation encoding="application/x-tex">L, \text{start}, \text{end}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mord mathnormal">L</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord text"><span class="mord">start</span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord text"><span class="mord">end</span></span></span></span></span>)</p>
<div class="ps-algorithmic with-linenum">
<div class="ps-block" style="margin-left:1.2em;">
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">1:</span><span class="ps-keyword">if </span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext>start</mtext><mo>></mo><mtext>end</mtext></mrow><annotation encoding="application/x-tex">\text{start} > \text{end}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6542em;vertical-align:-0.0391em;"></span><span class="mord text"><span class="mord">start</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">></span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord text"><span class="mord">end</span></span></span></span></span><span class="ps-keyword"> then</span></p>
<div class="ps-block" style="margin-left:0.6em;">
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-0.75em;">2:</span><span class="ps-keyword">return </span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi><mi>U</mi><mi>L</mi><mi>L</mi></mrow><annotation encoding="application/x-tex">NULL</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.109em;">N</span><span class="mord mathnormal" style="margin-right:0.109em;">U</span><span class="mord mathnormal">LL</span></span></span></span></p>
</div>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">3:</span><span class="ps-keyword">end if</span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">4:</span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext>mid</mtext><mo>←</mo><mo stretchy="false">(</mo><mi>s</mi><mi>t</mi><mi>a</mi><mi>r</mi><mi>t</mi><mo>+</mo><mi>e</mi><mi>n</mi><mi>d</mi><mo stretchy="false">)</mo><mi mathvariant="normal">/</mi><mn>2</mn></mrow><annotation encoding="application/x-tex">\text{mid} \gets (start + end) / 2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord text"><span class="mord">mid</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">←</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">s</span><span class="mord mathnormal">t</span><span class="mord mathnormal">a</span><span class="mord mathnormal" style="margin-right:0.0278em;">r</span><span class="mord mathnormal">t</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">e</span><span class="mord mathnormal">n</span><span class="mord mathnormal">d</span><span class="mclose">)</span><span class="mord">/2</span></span></span></span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">5:</span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext>left</mtext><mo>←</mo><mi>B</mi><mi>u</mi><mi>i</mi><mi>l</mi><mi>d</mi><mi>L</mi><mi>L</mi><mi>R</mi><mi>B</mi><mi>T</mi><mi>r</mi><mi>e</mi><mi>e</mi><mo stretchy="false">(</mo><mi>L</mi><mo separator="true">,</mo><mi>s</mi><mi>t</mi><mi>a</mi><mi>r</mi><mi>t</mi><mo separator="true">,</mo><mi>m</mi><mi>i</mi><mi>d</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\text{left} \gets BuildLLRBTree(L, start, mid-1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord text"><span class="mord">left</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">←</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.0502em;">B</span><span class="mord mathnormal">u</span><span class="mord mathnormal">i</span><span class="mord mathnormal" style="margin-right:0.0197em;">l</span><span class="mord mathnormal">d</span><span class="mord mathnormal">LL</span><span class="mord mathnormal" style="margin-right:0.0077em;">R</span><span class="mord mathnormal" style="margin-right:0.0502em;">B</span><span class="mord mathnormal" style="margin-right:0.1389em;">T</span><span class="mord mathnormal" style="margin-right:0.0278em;">r</span><span class="mord mathnormal">ee</span><span class="mopen">(</span><span class="mord mathnormal">L</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">s</span><span class="mord mathnormal">t</span><span class="mord mathnormal">a</span><span class="mord mathnormal" style="margin-right:0.0278em;">r</span><span class="mord mathnormal">t</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">mi</span><span class="mord mathnormal">d</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span></span></span></span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">6:</span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext>right</mtext><mo>←</mo><mi>B</mi><mi>u</mi><mi>i</mi><mi>l</mi><mi>d</mi><mi>L</mi><mi>L</mi><mi>R</mi><mi>B</mi><mi>T</mi><mi>r</mi><mi>e</mi><mi>e</mi><mo stretchy="false">(</mo><mi>L</mi><mo separator="true">,</mo><mi>m</mi><mi>i</mi><mi>d</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><mi>e</mi><mi>n</mi><mi>d</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\text{right} \gets BuildLLRBTree(L, mid+1, end)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mord text"><span class="mord">right</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">←</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.0502em;">B</span><span class="mord mathnormal">u</span><span class="mord mathnormal">i</span><span class="mord mathnormal" style="margin-right:0.0197em;">l</span><span class="mord mathnormal">d</span><span class="mord mathnormal">LL</span><span class="mord mathnormal" style="margin-right:0.0077em;">R</span><span class="mord mathnormal" style="margin-right:0.0502em;">B</span><span class="mord mathnormal" style="margin-right:0.1389em;">T</span><span class="mord mathnormal" style="margin-right:0.0278em;">r</span><span class="mord mathnormal">ee</span><span class="mopen">(</span><span class="mord mathnormal">L</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">mi</span><span class="mord mathnormal">d</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">e</span><span class="mord mathnormal">n</span><span class="mord mathnormal">d</span><span class="mclose">)</span></span></span></span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">7:</span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext>node</mtext><mo>←</mo></mrow><annotation encoding="application/x-tex">\text{node} \gets</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord text"><span class="mord">node</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">←</span></span></span></span> new Node(<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>L</mi><mo stretchy="false">[</mo><mi>m</mi><mi>i</mi><mi>d</mi><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">L[mid]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">L</span><span class="mopen">[</span><span class="mord mathnormal">mi</span><span class="mord mathnormal">d</span><span class="mclose">]</span></span></span></span>)</p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">8:</span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext>node.left</mtext><mo>←</mo><mi>l</mi><mi>e</mi><mi>f</mi><mi>t</mi></mrow><annotation encoding="application/x-tex">\text{node.left} \gets left</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord text"><span class="mord">node.left</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">←</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mord mathnormal" style="margin-right:0.0197em;">l</span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.1076em;">f</span><span class="mord mathnormal">t</span></span></span></span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">9:</span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext>node.right</mtext><mo>←</mo><mi>r</mi><mi>i</mi><mi>g</mi><mi>h</mi><mi>t</mi></mrow><annotation encoding="application/x-tex">\text{node.right} \gets right</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mord text"><span class="mord">node.right</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">←</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mord mathnormal" style="margin-right:0.0278em;">r</span><span class="mord mathnormal">i</span><span class="mord mathnormal" style="margin-right:0.0359em;">g</span><span class="mord mathnormal">h</span><span class="mord mathnormal">t</span></span></span></span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">10:</span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext>node.color</mtext><mo>←</mo><mtext>BLACK</mtext></mrow><annotation encoding="application/x-tex">\text{node.color} \gets \text{BLACK}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord text"><span class="mord">node.color</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">←</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord text"><span class="mord">BLACK</span></span></span></span></span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">11:</span><span class="ps-keyword">return </span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mi>o</mi><mi>d</mi><mi>e</mi></mrow><annotation encoding="application/x-tex">node</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal">n</span><span class="mord mathnormal">o</span><span class="mord mathnormal">d</span><span class="mord mathnormal">e</span></span></span></span></p>
</div>
</div>
</div>
</div>

## 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_

<div class="ps-root" data-inline-macros=""><span type="button" class="clipboard-button ps-clipboard" aria-label="Copy pseudocode to clipboard"><svg width="16" height="16" viewBox="0 0 16 16" class="copy-icon"><use href="#github-copy"></use></svg><svg width="16" height="16" viewBox="0 0 16 16" class="check-icon"><use href="#github-check" fill-rule="evenodd" fill="rgb(63, 185, 80)"></use></svg></span><span class="ps-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><annotation encoding="application/x-tex">"\\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}"</annotation></semantics></math></span>
<div class="ps-algorithm with-caption">
<p class="ps-line" style="text-indent:-0.6em;padding-left:0.6em;">
<span class="ps-keyword">Algorithm 31 </span>Check for Duplicates Using Hashing</p>
<div class="ps-algorithmic with-linenum">
<p class="ps-line" style="text-indent:-0.6em;padding-left:0.6em;">
<span class="ps-keyword">Require: </span>A set of strings <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.0576em;">S</span></span></span></span></p>
<p class="ps-line" style="text-indent:-0.6em;padding-left:0.6em;">
<span class="ps-keyword">Ensure: </span>True if there are duplicates in <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.0576em;">S</span></span></span></span>, False otherwise</p>
<div class="ps-block" style="margin-left:1.2em;">
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">1:</span>Initialize an empty hash table <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.0813em;">H</span></span></span></span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">2:</span><span class="ps-keyword">for </span>each string <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>s</mi><mo>∈</mo><mi>S</mi></mrow><annotation encoding="application/x-tex">s \in S</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mord mathnormal">s</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.0576em;">S</span></span></span></span><span class="ps-keyword"> do</span></p>
<div class="ps-block" style="margin-left:0.6em;">
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-0.75em;">3:</span>Compute <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>h</mi><mo stretchy="false">(</mo><mi>s</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">h(s)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord mathnormal">s</span><span class="mclose">)</span></span></span></span> using the hash function</p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-0.75em;">4:</span><span class="ps-keyword">if </span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>h</mi><mo stretchy="false">(</mo><mi>s</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">h(s)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord mathnormal">s</span><span class="mclose">)</span></span></span></span> is in <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.0813em;">H</span></span></span></span><span class="ps-keyword"> then</span></p>
<div class="ps-block" style="margin-left:0.6em;">
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-1.5em;">5:</span><span class="ps-keyword">for </span>each string <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>s</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo>∈</mo><mi>H</mi><mo stretchy="false">[</mo><mi>h</mi><mo stretchy="false">(</mo><mi>s</mi><mo stretchy="false">)</mo><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">s' \in H[h(s)]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.791em;vertical-align:-0.0391em;"></span><span class="mord"><span class="mord mathnormal">s</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.7519em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">′</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.0813em;">H</span><span class="mopen">[</span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord mathnormal">s</span><span class="mclose">)]</span></span></span></span><span class="ps-keyword"> do</span></p>
<div class="ps-block" style="margin-left:0.6em;">
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-2.25em;">6:</span><span class="ps-keyword">if </span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>s</mi><mo>=</mo><msup><mi>s</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup></mrow><annotation encoding="application/x-tex">s = s'</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">s</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.7519em;"></span><span class="mord"><span class="mord mathnormal">s</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.7519em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">′</span></span></span></span></span></span></span></span></span></span></span></span><span class="ps-keyword"> then</span></p>
<div class="ps-block" style="margin-left:0.6em;">
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-3em;">7:</span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-3em;">8:</span><span class="ps-keyword">return </span>True</p>
</div>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-2.25em;">9:</span><span class="ps-keyword">end if</span></p>
</div>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-1.5em;">10:</span><span class="ps-keyword">end for</span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-1.5em;">11:</span>Append <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">s</span></span></span></span> to <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>H</mi><mo stretchy="false">[</mo><mi>h</mi><mo stretchy="false">(</mo><mi>s</mi><mo stretchy="false">)</mo><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">H[h(s)]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.0813em;">H</span><span class="mopen">[</span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord mathnormal">s</span><span class="mclose">)]</span></span></span></span></p>
</div>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-0.75em;">12:</span><span class="ps-keyword">else</span></p>
<div class="ps-block" style="margin-left:0.6em;">
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-1.5em;">13:</span>Insert <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">s</span></span></span></span> into <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.0813em;">H</span></span></span></span> at <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>h</mi><mo stretchy="false">(</mo><mi>s</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">h(s)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord mathnormal">s</span><span class="mclose">)</span></span></span></span></p>
</div>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:-0.75em;">14:</span><span class="ps-keyword">end if</span></p>
</div>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">15:</span><span class="ps-keyword">end for</span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">16:</span></p>
<p class="ps-line ps-code">
<span class="ps-linenum" style="left:0em;">17:</span><span class="ps-keyword">return </span>False</p>
</div>
</div>
</div>
</div>