delete

TREE-DELETE(T,n)
	if war = True
		z = TREE-SUCCESSOR(n)
	else
		z = TREE-PREDECESSOR(n)

	// case 1 z jest liściem
	// case 2 z ma jedno dziecko
	// case 3 z ma dwoje dzieci

	if z.left = NIL OR z.right = NIL
		y = z //case 1 2
	else
		y = TREE-SUCCESSOR(z) //case 3
	if y.left ≠ NIL
		x = y.left
	else
		x = y.right
	if x ≠ NIL
		x.p = y.p //case 2 3
	if y.p = NIL
		T.root = x
	else
		if y = y.p.left
			y.p.left = x
		else
			y.p.right = x
	if y ≠ z //case 3
		z.key = y.key

	delete y