Red Black Tree
RED BLACK TREE Properties Root is always black No red nodes are adjacent to each other Number of black nodes from any node to a NULL node is the same Insertion Algorithm N = new node P = N's parent U = N's uncle GP = N's grandparent 1 Do BST insertion 2 Mark N as red 3 If N is root, colour it black 4 If P is black, stop. 5 Else 6 IF if U is RED, 7 do recolouring (colour P and U as BLACK, and. GP as RED) 8 recursive recolouring by N = GP in the recolouring algorithm and so on 9 IF U is BLACK 10 do Rotation Rotation Cases 1. Left Left (N is P's left child, P is GP's left child) 2. Right Right (N is P's right child, P is GP's right child) 3. Left Right (N is P's right child, P is GP's left child) 4. Right Left (N is P's left child, P is GP's right child) Solving the Cases 1. LL: do right rotati...