Delete node at key (also return the deleted node value)

O(n) in worst case, average is O(h) with h: tree height

var tree = new BinTreeMap[Int, String]
tree[1] = "n1"
assert tree.max == "n1"
tree[3] = "n3"
assert tree.max == "n3"
tree.delete(3)
assert tree.max == "n1"

Property definitions

trees $ BinTreeMap :: delete
	# Delete node at `key` (also return the deleted node value)
	# O(n) in worst case, average is O(h) with h: tree height
	#
	#     var tree = new BinTreeMap[Int, String]
	#     tree[1] = "n1"
	#     assert tree.max == "n1"
	#     tree[3] = "n3"
	#     assert tree.max == "n3"
	#     tree.delete(3)
	#     assert tree.max == "n1"
	fun delete(key: K): nullable E do
		assert is_empty: root != null
		len -= 1
		var node = search_down(root.as(not null), key)
		if node == null then return null
		if node.left == null then
			transplant(node, node.right)
		else if node.right == null then
			transplant(node, node.left)
		else
			var min = min_from(node.right.as(not null))
			if min.parent != node then
				transplant(min, min.right)
				min.right = node.right
				min.right.parent = min
			end
			transplant(node, min)
			min.left = node.left
			min.left.parent = min
		end
		if first_node == node then
			first_node = null
		end
		if last_node == node then
			last_node = node.prev
			last_node.next = null
		else
			node.prev.next = node.next
			node.next.prev = node.prev
		end
		return node.value
	end
lib/trees/bintree.nit:194,2--235,4

trees $ RBTreeMap :: delete
	# TODO implement RBTree::delete
	redef fun delete(key) is abstract
lib/trees/rbtree.nit:118,2--119,34