TOPIC: Red-Black Trees

B.Sc(HONS) IV Sem �Computer Science

​

PREPARED BY: Dr. Sandip Dey

Department of Computer Science

Date: 17th March, 2022

​

Red-Black Trees

• Definition: A red-black tree is a binary search tree (BST), in which the following properties hold.
• Every node is either red or black.
• Each NULL pointer is called a black node.
• If a node is red, then both of its children are black, i.e., there are no two consecutive red nodes.
• The paths from the root to any leaf have the same number of black nodes.
• the root is black.

​

2

3

Definition: The black-height of a node, x, in a red-black tree is the number of black nodes on any path to a leaf, not counting x.

The height of red-black tree

Black-Height of the root = 2

4

5

Height-balanced trees

Balancedness property is maintained in the Red-Black tree as given by.

​

- Each path from the root to a leaf contains the same number of black nodes

7

3

18

10

22

26

11

8

bh =2

bh =2

bh =1

bh =1

bh =1

bh =1

bh =1

Rotation

​

A rotation is an operation in a search tree that conserve in-order traversal key ordering.

6

Bottom-Up Rebalancing Approach for Red-Black Trees

The thought for insertion in a red-black tree is to insert like in a binary search tree. Thereafter, the color properties are reestablish through a sequence of recoloring and rotations

The rules are as follows:

1. If other is red, color current and other black and upper red.

2. If current = upper->left

a. If current->right->color is black,

Perform a right rotation around upper and color upper->right red.

b. If current->right->color is red,

Perform a left rotation around current followed by a right rotation around upper, and color upper->right and upper->left black and upper red.

3. If current = upper->right

a. If current->left->color is black,

perform a left rotation around upper and color upper->left red.

b. If current->left->color is red,

Perform a right rotation around current followed by a left rotation around upper, and color upper->right and upper->left black and upper red.

7

Lets discuss 3 cases for insertion operation

​

​

Case 1: Recolor (uncle is red)

​

P

G

U

P

G

U

8

Case 2:

Double Rotate: X around P then X around G.

Recolor G and X

X

P

G

U

S

X

P

G

S

U

9

Case 3:

Single Rotate P around G

Recolor P and G

X

P

G

U

S

P

X

G

S

U

10

Analysis of Insertion

​

• A red-black tree has O(log n) height
• Search for insertion location takes O(log n) time because we visit O(log n) nodes
• Addition to the node takes O(1) time
• Rotation or recoloring takes O(log n) time because we perform

* O(log n) recoloring, each taking O(1) time, and

* at most one rotation taking O(1) time

- Thus, an insertion in a red-black tree takes O(log n) time

11

Delete a node from a red-black tree.

​

• If the node is red?�Not a problem – no RB properties violated�
• If the node is black?�deleting it will change the black-height along some path.

12

There are some cases for deletion

P

S

U

V

Case A:

- V’s sibling, S, is Red

Rotate S around P and recolor S & P

​

delete

13

P

S

V

P

S

V

Rotate S around P

P

V

S

Recolor S & P

​

14

P

S

U

V

Case B:

- V’s sibling, S, is black and has two black children.

Recolor S to be Red

delete

Red or Black and don’t care

15

P

S

V

P

S

V

Recolor S to be Red

​

16

P

S

U

V

Case C:

- S is black

S’s RIGHT child is RED (Left child either color)

Rotate S around P

Swap colors of S and P, and color S’s Right child Black

delete

17

P

S

V

P

S

V

Rotate S around P

P

S

V

Recolor: Swap colors of S and P, and color S’s Right child Black

18

P

S

U

V

delete

Case D:

- S is Black, S’s right child is Black and S’s left child is Red

i) Rotate S’s left child around S

ii) Swap color of S and S’s left child

19

P

S

V

P

S

V

Rotate S’s left child around S

P

S

V

Recolor: Swap color of S and S’s left child

20

Analysis of deletion

​

• A red-black tree has O(log n) height
• Search for deletion location takes O(log n) time
• The swapping and deletion is O(1).
• Each rotation or recoloring is O(1).
• Thus, the deletion in a red-black tree takes O(log n) time

21