2-3-4 высота дерева не сбалансирована

Question

Я заметил, что высота дерева 2-3-4 может быть разной в зависимости от порядка вставки узлов.

например 1,2,3,4,5,6,7,8,9,10 даст дерево высоты 2

При вставке в этом порядке:

например, 1, 5, 10, 2, 3, 8, 9, 4, 7, 8 даст дерево высоты 1

Это нормальное свойство дерева 2-3-4? Вставка узлов в последовательности приведет к очень несбалансированному дереву в этом случае. Я думал 2-3-4 дерева должны быть сбалансированными деревьями?

Благодарю.

Answer 1

2-3-4 дерева действительно являются "сбалансированными" деревьями в том смысле, что высота дерева никогда не превышает некоторой фиксированной границы относительно количества узлов (которое, если в каждом узле ровно два значения, равно O(log n).)). Термин "сбалансированный" здесь должен противопоставляться "несбалансированному", который будет деревом, в котором высота "велика" относительно количества узлов. Например, это дерево сильно разбалансировано:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Я думаю, что вы предполагаете, что термин "сбалансированный" означает "максимально компактный", что не соответствует действительности. Абсолютно возможно иметь несколько разных порядков вставки в 2-3-4 дерева, чтобы получить деревья разной высоты, некоторые из которых будут иметь меньшую высоту, чем другие. Однако максимально возможная достижимая высота не слишком велика по сравнению с общим числом узлов в дереве, и поэтому 2-3-4 дерева действительно считаются сбалансированными деревьями.

Надеюсь это поможет!

Answer 2

сбалансированное дерево обычно означает, что его высота O(logn).

B-деревья vaild (включая 2-3-4 Tree) имеют следующие ограничения:

1. все некорневые узлы имеют как минимум [m/2] элементов.

2. все листья в одной высоте.

с этими двумя пределами доказано, что действительное B-дерево имеет высоту O(logn).

Answer 3

Я заметил, что высота дерева 2-3-4 может быть разной в зависимости от порядка вставки узлов.

Алгоритм вставки для 2-3-4 деревьев разделяет 4-узлы "на пути" к конечному узлу, поскольку они не могут взять другой элемент. Это позволяет выполнить вставку за один проход, и дерево остается сбалансированным.