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"
# 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