2016-06-13 8 views
-2

Почему наилучшее время выполнения для удаления из дерева 2-4 (logn), а не O (1)?Что такое время выполнения удаления 2-4 дерева

+0

Почему вы не проводите предварительные исследования? Почему вы бросаете здесь вопросы, которые ужасно звучат как «пожалуйста, сделайте мою домашнюю работу»? – GhostCat

+0

Почему * будет * это O (1)? (Я не говорю, что ты сумасшедший, думая, что это может быть. Но если вы хотите, чтобы люди объясняли, почему ваши рассуждения идут не так, вы должны объяснить, каковы ваши рассуждения на самом деле!) – ruakh

ответ

1

Подумайте об этом таким образом, если вы удалите из корневого узла дерева 2-4, вам придется выполнить свопы O (log n), а также операции плавких предохранителей и отбрасывания, чтобы удовлетворить структурные и упорядочивающие свойства дерева 2-4. Это тот же случай, если вы удалили из нелистового узла. Теперь, если вы удаляете из листового узла, это все равно операция O (log n), так как вам нужно пройти в нижней части дерева 2-4, чтобы удалить из листа, что является операцией O (log n).

Удача учиться на экзамене профессора Zoom's

+0

Ваш умный куки. – restores