Почему не может 2-3 дерева "разрешить" степень 1

Question

Вопрос, с которым я боролся... Почему реализация 2-3 деревьев не позволяет узлам иметь степень 1?

Я подумал, что это может быть связано с O(log (n)), который он (как член семейства B-деревьев) хочет сохранить, если разрешить степень 1, мы можем получить такое дерево:

1
 \
  2
   \
    3
     \
      4
       \
        5

например, а затем некоторые операции примут O(n) вместо O(log (n)), но я не вижу, где в этом ответе я ссылался на 2-3 дерева и почему он не может допустить степень 1...:-/

Спасибо!;-)

Answer 1

У вас уже есть правильный ответ, но, возможно, вы хотите сказать это так:

Варианты B-дерева поддерживают все листья на одной глубине (высота дерева), и операции обычно занимают время, пропорциональное этой высоте.

Поскольку внутренние узлы должны иметь как минимум 2 дочерних элемента, каждый уровень содержит как минимум вдвое больше узлов, чем родительский уровень, а высота дерева равна O(log N).

Если бы внутренним узлам было разрешено содержать менее 2 дочерних элементов, высота могла бы превышать O (log N), а операции занимали бы больше времени, чем логарифмическое время.