Obviously binary trees are great because of $O(\log_2 n)$ search, inserts, and deletes in best case.

To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, splay trees, etc.

If we use a $k$-ary tree, we can get $O(\log_k n)$ searches, inserts, and deletes in best case. Similarly we can "maximize" the occurrences by using self-balancing trees.

I know these are asymptotically of the same order, i.e. $O(\log n)$, but the constant could be huge in practice.

The huge reason I can think of is that by using larger $k$'s, you lose the ability to make a decision based on one comparison.

What are other reasons larger $k$ $k$-ary trees aren't used in practice?


1 Answer 1


BTrees are used in practice - file systems, database with $k$ for example equal 1024 or 4096, so it seems to be bigger than binary.

Probably you have not encountered need yet.
For example ternary tree with comparing >, =, < gives theoretical improve $O(log_3 n)$, but self balancing trees in basic form do not accept duplicates, so there is more overhead and not strictly practical.
But bigger ones, yes, they give boost and you use it right now (on the computer).


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.