     /// - Note: You need to discard your existing handles into the tree after you call this method.
     /// - SeeAlso: `removeAndReturnSuccessor`
     /// - Complexity: O(log(count))
-    public mutating func remove(handle: Handle) {
-        _remove(handle, successor: nil)
+    public mutating func remove(handle: Handle) -> Payload {
+        return _remove(handle, successor: nil).1
     }
 
     /// Remove a node, keeping track of its successor.
     /// - Returns: The handle of `successor` after the removal.
-    private mutating func _remove(handle: Handle, successor: Handle?) -> Handle? {
+    private mutating func _remove(handle: Handle, successor: Handle?) -> (Handle?, Payload) {
         assert(handle != successor)
         // Fixme: Removing from a red-black tree is one ugly algorithm.
         let node = self[handle]

        return Config.compare(key, to: self[handle].head, reducedPrefix: reduction)
    }


    public mutating func insert(key: Key, payload: Payload) -> Handle {
        func insertionSlotOf(key: Key) -> Slot {

            self[handle].payload = n.payload
            // Note that the above doesn't change root, leftmost, rightmost.
            // The reduction will be updated on the way up.
            let handle = _remove(next, keeping: handle)
            return (handle, node.payload)
        }
        else {
            let handle = _remove(handle, keeping: successor)
            return (handle, node.payload)
        }
    }

