Какова сложность вставки btree?

Question

Кажется, что когда вставляется новый узел (чья сложность O (logN)), нужно перебалансировать все дерево.

В чем сложность перебалансировки?

Answer 1

Это высота дерева.Он не перебалансирован в смысле бинарного дерева.Когда вы добавляете узел, если это вызывает разделение, вы вставляете ключ в узел выше.Если это вызывает разделение, то вы делаете то же самое на один уровень выше и т. Д., Пока не доберетесь до корня.Таким образом, сложность O (logN).