btree的插入复杂性是什么？

Question

看起来，插入新节点（其复杂度为O（logN））时，整棵树需要重新平衡。

重新平衡的复杂性是什么？

Answer 1

这是树的高度。它不是在二叉树意义上重新平衡的。当你添加一个节点时，如果这导致了一个分割，你可以在上面的节点中插入一个键。如果这样做导致分裂，那么你会在同一层面上做同样的事情，等等，直到你到达根部。所以复杂度是O（logN）。