0
$\begingroup$

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.
Improve this question
$\endgroup$
2
  • $\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$
    – AyamGorengPedes
    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

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.