btree的插入複雜性是什麼？

Question

看起來，插入新節點（其複雜度爲O（logN））時，整棵樹需要重新平衡。

重新平衡的複雜性是什麼？

Answer 1

這是樹的高度。它不是在二叉樹意義上重新平衡的。當你添加一個節點時，如果這導致了一個分割，你可以在上面的節點中插入一個鍵。如果這樣做導致分裂，那麼你會在同一層面上做同樣的事情，等等，直到你到達根部。所以複雜度是O（logN）。