rbt_delete_doc.py

def delete(tree, key):
	remove_node = find(tree, key)
	if remove_node is None:
		raise KeyError
	remove_color = remove_node.color
	replace_node = None
	rl, rr, tl = remove_node.left, remove_node.right, tree.leaf
	if rl == tl and rr == tl:
		replace_node = tree.leaf
		transplant(tree, remove_node, tree.leaf)
		if remove_color == "black":
			remove_color = replace_node.color
			replace_node.color = "black"
	elif rl == tl and rr != tl:
		replace_node = rr
		transplant(tree, remove_node, replace_node)
		if remove_color == "black":
			remove_color = replace_node.color
			replace_node.color = "black"
	elif rl != tl and rr == tl:
		replace_node = rl
		transplant(tree, remove_node, replace_node)
		if remove_color == "black":
			remove_color = replace_node.color
			replace_node.color = "black"
	else:
		next_node = find_next(tree, remove_node)
		remove_color = next_node.color
		
		if next_node.right is not None:
			replace_node = next_node.right
			transplant(tree, next_node, replace_node)
			transplant(tree, next_node.right, remove_node.right)
			next_node.right = remove_node.right
			if next_node.right is not None:
				next_node.right.parent = next_node
		else:
			tree.leaf.parent = next_node.parent
		transplant(tree, remove_node, next_node)
		transplant(tree, next_node.left, remove_node.left)
		next_node.color = remove_node.color
	if remove_color == BLACK:
		fix_tree_after_delete(tree, replace_node)