Scribd
Upload
11 views3 pages

Red-Black Tree Insertions Explained

The document shows the step-by-step insertion of keys 1 through 10 into an initially empty red-black tree. With each insertion, the tree is rebalanced if needed to maintain the red-black tree properties. The final tree after all 10 keys have been inserted is a complete binary search tree with black height of 2.

Uploaded by

Ani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views3 pages

Red-Black Tree Insertions Explained

The document shows the step-by-step insertion of keys 1 through 10 into an initially empty red-black tree. With each insertion, the tree is rebalanced if needed to maintain the red-black tree properties. The final tree after all 10 keys have been inserted is a complete binary search tree with black height of 2.

Uploaded by

Ani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Insertions into a Red-Black Tree

Insertions: Inserting the 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 keys into an initially empty


RB-tree.

a) 1, 2
1

b) 3 2
1

1 3
2

c) 4
2 2

1 3 1 3

4 4

2
2

d) 5 1 4
1 3
3 5
4

5
Insertions into a Red-Black Tree – (2)

e) 6

2 2

1 4 1 4

3 5 3 5

6 6

f) 7
2 2

1 4 1 4

5 3 6
3
6 5 7

g) 8

2 4

1 4
2 6
3 6
1 3 5 7
5 7
8
8

2
Armen Kostanyan
Insertions into a Red-Black Tree – (3)

h) 9
4 4

6 2 6
2

7 1 3 5 8
1 3 5

8 7 9

i) 10

4 4

6 2 6
2

1 3 5 8 1 3 5 8

7 9 7 9

10 10

3
Armen Kostanyan

You might also like