1 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

7

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

2 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

6 7

7

6

7

add(6)

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

3 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

6 7

add(5)

7

6

5 6 7

split(5/6/7)

6

5

7

6

5

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

4 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

6 7

add(5)

7

6

5 6 7

split(5/6/7)

6

5

7

6

5

rotateRight(7)

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

5 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

6 7

add(5)

7

6

5 6 7

split(5/6/7)

6

5

7

6

5

rotateRight(7)

6

5

7

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

6 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

6 7

add(5)

7

6

5 6 7

split(5/6/7)

6

5

7

6

5

rotateRight(7)

6

5

7

flip(6)

6

5

7

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

7 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(4)

6

5

7

6

5

7

6

5

7

4

6

4 5

7

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

8 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(3)

6

5

7

6

3 4 5

7

6

5

7

4

6

5

7

4

3

split(3/4/5)

4 6

3

7

5

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

9 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(3)

6

5

7

6

3 4 5

7

6

5

7

4

6

5

7

4

3

split(3/4/5)

4 6

3

7

5

rotateRight(5)

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

10 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(3)

6

5

7

6

3 4 5

7

6

5

7

4

6

5

7

4

3

split(3/4/5)

4 6

3

7

5

6

4

7

3

5

rotateRight(5)

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

11 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(3)

6

5

7

6

3 4 5

7

6

5

7

4

6

5

7

4

3

split(3/4/5)

4 6

3

7

5

6

4

7

3

5

rotateRight(5)

flip(4)

6

4

7

3

5

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

12 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(2)

6

4

7

3

5

4 6

3

7

5

4 6

2 3

7

5

6

4

7

3

5

2

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

13 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(1)

4 6

2 3

7

5

6

4

7

3

5

2

4 6

1 2 3

7

5

split(1/2/3)

2 4 6

7

5

1

3

split(2/4/6)

2

1

3

6

5

7

4

6

4

7

3

5

2

1

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

14 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(1)

4 6

2 3

7

5

6

4

7

3

5

2

4 6

1 2 3

7

5

split(1/2/3)

2 4 6

7

5

1

3

split(2/4/6)

2

1

3

6

5

7

4

6

4

7

3

5

2

1

rotateRight(3)

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

15 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(1)

4 6

2 3

7

5

6

4

7

3

5

2

4 6

1 2 3

7

5

split(1/2/3)

2 4 6

7

5

1

3

split(2/4/6)

2

1

3

6

5

7

4

6

4

7

3

5

2

1

rotateRight(3)

6

4

7

2

5

1

3

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

16 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

add(1)

4 6

2 3

7

5

6

4

7

3

5

2

4 6

1 2 3

7

5

split(1/2/3)

2 4 6

7

5

1

3

split(2/4/6)

2

1

3

6

5

7

4

6

4

7

3

5

2

1

rotateRight(3)

6

4

7

2

5

1

3

6

4

7

2

5

1

3

flip(2)

...

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

17 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

...

add(1)

4 6

2 3

7

5

6

4

7

3

5

2

4 6

1 2 3

7

5

split(1/2/3)

2 4 6

7

5

1

3

split(2/4/6)

2

1

3

6

5

7

4

6

4

7

2

5

1

3

rotateRight(6)

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

18 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

...

add(1)

4 6

2 3

7

5

6

4

7

3

5

2

4 6

1 2 3

7

5

split(1/2/3)

2 4 6

7

5

1

3

split(2/4/6)

2

1

3

6

5

7

4

6

4

7

2

5

1

3

rotateRight(6)

2

1

3

6

5

7

4

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.

19 of 19

LLRB / 2-3 Tree Insertion Demo

LLRB World

World 2-3

...

add(1)

4 6

2 3

7

5

6

4

7

3

5

2

4 6

1 2 3

7

5

split(1/2/3)

2 4 6

7

5

1

3

split(2/4/6)

2

1

3

6

5

7

4

6

4

7

2

5

1

3

rotateRight(6)

2

1

3

6

5

7

4

flip(4)

2

1

3

6

5

7

4

Rules:

Right red link → rotate left.
Two consecutive left links → rotate right.
Red left and red right → color flip.