Time complexity of insertion and removing in 2-3 trees

Question

Why do insertion and removing operations in 2-3 tree always have complexity of O(logn), is there a mathematical proof?

Answer 1

• When we insert a key at level 𝑘, in the worst case we need to split 𝑘 + 1 nodes (one at each of the 𝑘 levels plus the root).
• A 2-3 tree containing 𝑛 keys with the maximum number of levels takes the form of a binary tree where each internal node has one key and two children.
• In such a tree 𝑛 = (2^(𝑘+1)) − 1 where 𝑘 is the number of the lowest level.
• This implies that 𝑘 + 1 = log(𝑛 + 1) from which we see that the splits are in the worst case 𝑂 log 𝑛 .
• So insertion in a 2-3 tree takes at worst 𝑶 𝐥𝐨𝐠 𝒏 time.
• Similarly we can prove that searches and deletions take 𝑶 𝐥𝐨𝐠 𝒏 time.