Временная сложность вставки и удаления в 2-3 дерева

Question

Почему операции вставки и удаления в дереве 2-3 всегда имеют сложность O (logn), есть ли математическое доказательство?

Answer 1

• Когда мы вставляем ключ на уровне ?, в худшем случае нам нужно разделить ? + 1 узлы (по одному на каждом из ? уровней плюс корень).
• 2-3 tree, содержащий ? ключей с максимальным количеством уровней, принимает форму двоичного дерева, в котором каждый внутренний узел имеет один ключ и двух дочерних элементов.
• В таком дереве ? = (2^(?+1)) − 1, где ?является номером самого низкого уровня.
• Это означает, что ? + 1 = log(? + 1), из которого мы видим, что расщепления в худшем случае ? log ?.
• Таким образом, вставка в 2-3 tree занимаетв худшем случае ? ??? ? время.
• Аналогичным образом мы можем доказать, что поиск и удаление занимают ? ??? ? время.