Indeed, if the cost of the subtree delete-and-move operation had even linear dependence on the size of the subtree being moved, I think this entire proposal would be infeasible. Making this operation sublinear in the size of the subtree requires us to be very careful about the structure of the trie. Various potential structures were discussed in this thread but I’m not sure any work for this purpose - any information about the trie index in leaf nodes will not work, since then it will have to be changed when the subtree is moved.
A binary trie structure that would permit an \tilde{O}(1) subtree delete-and-move operation would be
tree_depth
left_child_hash
right_child_hash
extension_bits_to_left_child
extension_bits_to_right_child
Unlike other proposals, the prefix of the node (that is, the bit string which is the common prefix of all leaf indices of the node) is not present here. This allows the subtree nodes to be agnostic about their location in the tree so that they can be moved without touching them in the database.