Left Leaning Red Black Tree Question

SID Question

• SID: this is your TCD student number. It should be an 8-digit number.
• SID2: this is SID squared; it should be a 15-digit number.
• d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15: these are the fifteen digits of SID2, from left to right.
• u1, u2, u3, u4, u5, u6, u7, u8, u9, u10: these are the first 10 unique single-digit numbers of the di sequence, from left to right. If there are less than 10 unique numbers in your di sequence, you should complete the remaining ui sequence with single-digit numbers in ascending order. In the end, the ui sequence should not contain duplicate numbers.

SID Answer

SID: 23373999 SID2: $(23373999{)}^2=546,343,829,252,001$

Number	Value
d1	5
d2	4
d3	6
d4	3
d5	4
d6	3
d7	8
d8	2
d9	9
d10	2
d11	5
d12	2
d13	0
d14	0
d15	1

Number	Value
u1	5
u2	4
u3	6
u4	3
u5	8
u6	2
u7	9
u8	0
u9	1
u10	7

---

Tree Question

Give the logical representation of the Left Leaning Red-Black Tree obtained by inserting the sequence $u1,...,u10$ from Question 1 to the following Left Leaning Red-Black Tree:

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 9;

If one of the $u_i$ is already in the tree you should not insert it again. Therefore you will need to perform five insertions.

For every insertion you should show:

• The tree after inserting the key but before any tree transformations are applied.
• Which transformations should be applied, around which node, and in what order.
• The tree after each transformation.

Tree Answer

Inserting $u_1=5$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 9;

5;

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 9;

4 -- red --> 5;

Parent is black so we do nothing

Inserting $u_2=4$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 9;

4 -- red --> 5;

As per question, $4$ is already in the tree so we do nothing

Inserting $u_3=6$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 9;

4 -- red --> 5;

As per question, $6$ is already in the tree so we do nothing

Inserting $u_4=3$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 9;

4 -- red --> 5;

3;

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

Inserting $u_5=8$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

8;

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 8;
10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

Inserting $u_6=2$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 8;
10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

As per question $2$ is already in the graph so we can ignore it

Inserting $u_7=9$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 8;
10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

As per question $9$ is already in the graph so we can ignore it

Inserting $u_8=0$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 8;
10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

0;

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 8;
10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

1 -- red --> 0;

Inserting $u_9=1$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 8;
10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

1 -- red --> 0;

As per question, $1$ is already in the graph, so we can ignore it

Inserting $u_{1}0=7$

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 8;
10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

1 -- red --> 0;

7;

graph TD;

6 -- red --> 2;
6 -- black --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- red --> 8;
10 -- red --> 9;

4 -- red --> 3;
4 -- red --> 5;

1 -- red --> 0;
8 -- red --> 7;

Here, we have a violation of red → red at 8 → 7, so we look at red black tree rules.

Uncle is red $\therefore$ set uncle and parent to black and grandparent to red, then check for other violations.

graph TD;

6 -- red --> 2;
6 -- red --> 10;

2 -- black --> 1;
2 -- black --> 4;

10 -- black --> 8;
10 -- black --> 9;

4 -- red --> 3;
4 -- red --> 5;

1 -- red --> 0;
8 -- red --> 7;

No further violations occur, and all numbers are inserted, hence we are finished.