Red Black Tree

Red-Black Tree

5 essentials :

·each node color is red or black .

·root color is black

·each leaf is black

·if parent is red color , then children are black .

·for each node ,the num of black nodes from this node to eachdecedents is same

For Insert :

1> Empty Tree

node.color = BLACK ;

2> Parent color is BLACK

do nothing

3>Parent color and uncle color are both RED

step 1:

parent.color = BLACK

uncle.color = BLACK

grantpa.color = RED

step 2:

if grantpaIS ROOT(grantpa.parent == NULL)

grantpa.color = BLACK

4>Parent color is RED and uncle color ISBLACK

4.1

parent LEFT ,new node LEFT(ST:SUB-TREE)

step 1:

parent.color = BLACK

grantPa.color = RED

step 2:

RIGHT-rotate (grantPa is center point)

4.2 parent LEFT,new node RIGHT

step 1:

Left-Route Sub-Tree

step 2:

Go to 4.1

4.3 parent RIGHT ,new nodeLEFT

step 1 :Right-rotate Sub-Tree

step 2: Goto 4.4

4.4 parentRIGHT ,new node RIGHT

step 1:

parent.color = BLACK

grantPa.color = RED

step 2: Left Rotate (grantPa is center point)

Red Black Delete :

Case 1. Delete Root

return

Case 2.Sibling.Color is Red

step 1:

S.Color= BLACK

P.Color= RED

step 2:

2.1 N Is Left Child

LEFTrotateSub-Tree (P Is center point )

Step 2.2: N Is right child

Right Rotate Sub Tree

Step 3: Go to Case 3

Case 3:

Sibling Is BLACK

Sibling left and rightchildren both BLACK

Parent is BLACK

step 1:

Set S.Color = RED

Step 2:

Go To Case 1(Parent Node)

Case 4 :Sibling color is BLACK, Sibling children are BLACK ,Parent Is RED

S.color = RED

P.color = BLACK

Case 5:

Sibling color Is BLACK

Case 5.1

Sibling LEFTChild -> RED

Sibling RIGHTChild -> BLACK

N is Parent LeftChild

Step 1:

S.color = RED

S.LEFT_Child.color = BLACK

Step 2: RIGHTRotate(S Is Center point)

step 3: Go TOCase 6(Node)

Case 5.2

Sibling LEFTChild BLACK

Sibling RIGHTChild RED

N is Parent RightChild

Step 1:

S.color = RED

S.RIGHT_Child.color = BLACK

Step 2: LEFT Rotate

Step 3: Go TO Case6(Node)

Case 6:

Case 6.1

Sibling RIGHTChild RED

Sibling LEFTChild BLACK

Node is Parent LeftChild

step 1:

s.color = parent.color

parent.color = BLACK

step 2:

s.right_Child.color = BLACK

LeftRotate(Center point is Parent)

Case 6.2:

Sibling RIGHTChild BLACK

Sibling LEFTChild RED

N is Parent RIGHTChild

step 1:

s.color = parent.color

parent.color = BLACK

step 2:

s.right_Child.color = BLACK

Left Rotate(Center point is Parent)