2-3树插入和删除的时间复杂度
2-3树插入和删除的时间复杂度
提问于 2018-05-19 18:21:35
为什么2-3树中的插入和删除操作总是具有O(logn)的复杂性，有数学证明吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-05-19 19:29:19
- 当我们在级别插入一个键时，在最坏的情况下，我们需要拆分
+ 1节点(每个级别一个加上根)。 - 包含最大级别数的键的
2-3 tree采用二叉树的形式，其中每个内部节点都有一个键和两个子节点。 - 在这样的树中，
= (2^(+1)) − 1是最低级别的数目。 - 这意味着我们从其中看到的
+ 1 = log( + 1)在最坏的情况下是log。 - 所以在
2-3 tree中插入最坏的时间。 - 同样，我们可以证明搜索和删除需要时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50428242
复制相关文章
相似问题
腾讯云开发者
