Recall that in a $2-3-4$ tree, whenever we insert a new key we immediately split $($on our way down the tree$)$ any node we see that is full $($has $3$ keys in it$).$ In the worst case, every node that we see is full and has to be split, so the number of splits that we do in a single operation can be $(logn).$ Prove that the amortized number of splits is only $O(1).$

Hint: Using a piggy bank at every node which stores a token if the node is full $($or equivalently, a potential function which is equal to the number of full nodes$)$ does not work. Why not? Can you modify the banks$/$potential functions?

Note: this does not mean that the amortized running time of an insert is $O(1)($since this is not true$)$; it just means that the amortized number of splits is $O(1).$ So think of "cost" not as "time", but as "number of splits". Since we didn't talk about them in class, feel free to assume there are no delete operations.