Scott Huddleston and Kurt Mehlhorn's 1982 paper "A New Data Structure for Representing Sorted Lists" addresses this question. http://people.mpi-inf.mpg.de/~meh

Scott Huddleston and Kurt Mehlhorn's 1982 paper "A New Data Structure for Representing Sorted Lists" addresses this question. http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlhorn-ActaInformatica.pdf http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlho... The answer is that each modification costs O(1) amortized time when you have a 4. It even gives a little anecdote in the acknowledgements on the last page: "On October 29, 1979, Mehlhorn presented the results of [4] in Zurich. Ed McCreight was in the audience and asked, 'Is a similar result true for 2-3 trees?' The counterexample shown in Fig. 3 was described. He then asked, 'How about 10-50 trees?'" (Ed McCreight co-invented the B-tree) ([4] is Blum, N., Mehlhorn, K.: On the average number of rebalancing steps in weight-balanced trees. Theor. Comput. Sci. 11, 303-320 (1980)) However, you don't actually have to understand all of this to get the gist of why 2-3 trees don't have constant-amortized-time modifications. You can see that from a simple little experiment on binary numbers. Imagine that you had to implement binary arithmetic on your own. The first thing you implement is a binary counter with only increment. It starts at 0, you can add 1 as many times as you like. That's it. Note that a counter with n bits may require n bit flips to increment 11111...1. However, by assigning a binary number a potential of the number of 1 bits, you can see that incrementing takes O(1) amortized bit flips using the physicist's method. This doesn't work when you can also subtract one from your counter, since subtracting one can turn a lot of 0s into 1s. Adding one again turns them back, and you're back where you started, having spent no potential yet requiring a bunch of bit flips in each operation. However, if you allow each digit to be 0, 1, or 2, you can assign a positive potential to the 0 and 2 digits and zero potential to the 1 bits to show that both increment and decrement use O(1) amortized bit flips. The same thing happens with 2-3 trees vs. 2-3-4 trees. I believe 2-3 trees have amortized O(1) insert if deletion is not permitted, but 2-3-4 trees permit both. Number systems have some deep connections to data structure design like this. One place you can read more is in Okasaki's book, "Purely Functional Data Structures", through plenty of free resources exist on the topic as well - Amr Elmasry tends to publish about it a lot. Once you get it, you start to see the pattern in many other places.