rols.txt

1 -> if tree empty . create new node as root nod with color BLACK ;

2 -> if tree not empty . create new nod as leaf node with color RED ;

3 -> if parent of new node is BLACK exit ;

4 -> if parent of new node is RED then check the color parent sibling :
	
	a ) if color is BLACK or __NIL_ then : do rotations && recoloring .

	b ) if color is RED then : recoloring && check for parents of parent of new node .


ROLS :

	=> root == BLACK .

	=> no adjacent RED nodes .

	=> every path should have same number of BLACK nodes .

ROTATIONS :
	
	=> L && R :
			[X]                         [Y]
		       /   \         L             /   \
		      A    [Y]       =>         [X]    C
                          /   \      R         /   \ 
                         B     C     <=       A     B

		- X.right = Y.left .
		
		- IF ( Y.left != __NIL_ ) : Y.left.parent = X .
		
		- Y.parent = X.parent .
		
 		- IF ( X.parent == __NIL_ ) : __head_ = Y .
		
		- ELIF ( X == X.parent.left ) : X.parent.left = Y .
			
		- ELSE : X.parent.right = Y .
		
		- Y.left = X
	
		- X.parent = Y

	=> LR && RL :

		
		[X]                         [X]                            [Y]
               /   \            R          /   \              L           /   \
              A     [Z]         =>        A     [Y]           =>       [X]     [Z]                 
	           /   \                       /   \                  /   \   /   \
                 [Y]    B                     C     [Z]              A     C D     B
                /   \                              /   \
               C     D                            D     B

DELETION :

	Step 1 : perform BST deletion

	Step 2 : while ( is there DB ) do this :
		
		- case 1 : if node is RED just delete it .

		
		- case 2 : if root is DB just remove the DB .


		- case 3 : if DB sibling is BLACK && both its children are BLACK .
			
			- remove DB .

			- Add BLACK to its parents .

				-> if parent is BLACK it becomes DB .
				
				-> if parent is RED it becomes BLACK .

			- Make sibling RED .


		- case 4 : if DB sibling is RED .

			- swap colors of parent and its sibling .

			- rotate parent in DB direction .

		
		- case 5 : DB sibling is BLACK && far child of sibling is BLACK && the near one is RED .

			- swap colors of DB sibling && sibling child who is near to DB .

			- rotate sibling in oppesite direction to DB .

			- apply case 6 .

		
		- case 6 : DB sibling is BLACK && far child is RED .

			- swap colors of parent && sibling .

			- rotate parent in DB direction .

			- remove DB .

			- change color of RED child to BLACK .