I just studied about this 2-4 tree which is a self-balanced tree. Various sources and textbook often mentioned that the insertion, deleting and searching of this tree is $O(\lg n)$.

However, none of them explain the detailed reasons for that run-time complexity. Neither of them also explains them mathematically for the reason behind that run-time complexity.

Therefore, I would like to ask how do i basically show that the run time complexity to process a 2-4 with n keys is $O(\lg n)$?

  • $\begingroup$ The basic idea is that the depth of a 2-4 tree is $O(\log n)$. $\endgroup$ – Yuval Filmus Aug 6 '17 at 6:42

The tree is height-balanced, therefore the height of the tree is $O(\log n)$. So any insertion has to travel at most $O(\log n)$ steps deep into the tree to find the proper insertion place. Then it also takes another $O(\log n)$ steps the rebalance the tree. The same idea can be applied to searching and deleting in the tree.

The $O(\log n)$ height bound may be difficult to see in a 2-3-4 tree, so I will offer an alternative way to come to this realization. Any 2-3-4 tree is isometric to a proper Red-Black tree. That is to say, "they are equivalent data structures. In other words, for every 2–3–4 tree, there exists at least one red–black tree with data elements in the same order." A Red-Black tree is a balanced binary search tree whose height is more clearly bounded by $O(\log n)$ and so are all of its operations.

  • $\begingroup$ Thanks for the additional information. Never heard of the red-black tree before. Now there's another additional tree for me to know more about 2-4 trees. $\endgroup$ – Teo Chuen Wei Bryan Aug 6 '17 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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