开发者

What's the insert complexity of btree?

It seems when new node is inserted(whose complexity is O(logN)), the whole tree needs to be r开发者_如何学Pythone-balanced.

What's the complexity of re-balancing?


It's the height of the tree. It's not rebalanced in the sense of a binary tree. When you add a node, if that causes a split you insert a key into the node above. If that causes as split, then you do the same thing one level up, etc., until you get to the root. So the complexity is O(logN).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜