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

Question

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

Answer 1

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