After several hours of frustration, I finally realized that the definition of two-three trees aren't standard (my lecture notes, this video, this other video, and Wikipedia) are different. My lecture notes, for example, maintains that keys are stored only in the leaves, while most other implementations store values in the inner nodes as well. The core idea (that max height is still $\log n$) is the same, though. What irritates me even further is that the Wikipedia article doesn't even have a deletion algorithm!

Question: What is the 'most usually used' definition of two-three trees? Pointing to a lecture note is fine, as long as its 'commonly taught'.

Edit: The difference between the two videos:

  • In the second one, we do require that a single node with two child nodes hold only 1 value.
  • In the first one, we do.
  • $\begingroup$ In particular, it feels very 'follow your gut'. In fact, even GeekForGeeks does not have an implementation of it. Am I missing something? Is this just supposed to be an idea (kind of like Turing Machines, not actually implemented)? $\endgroup$ Jun 24, 2022 at 22:24
  • $\begingroup$ The difference in In the second one, we do require that … In the first one, we do. must be escaping me. $\endgroup$
    – greybeard
    Jun 25, 2022 at 20:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.