time-complexity - 2-3棵树中插入和删除的时间复杂度

Question

为什么 2-3 树中的插入和删除操作总是具有 O(logn) 的复杂度，有数学证明吗？

Answer 1

• 当我们在 level 插入一个键时，在最坏的情况下，我们需要拆分 + 1节点（每个级别一个节点加上根节点）。
• 具有最大层数的2-3 tree包含键采用二叉树的形式，其中每个内部节点都有一个键和两个子节点。
• 在这样的树 = (2^(+1)) − 1中，最低层的数量是多少。
• 这意味着 + 1 = log( + 1)我们从中看到分裂是最坏的情况 log 。
• 因此，插入 a2-3 tree需要最糟糕的 时间。
• 同样，我们可以证明搜索和删除需要 时间。