2-3-4 Генерирование дерева из списка чисел

Question

У меня есть список номеров 50,40,60,30,70. Предположим, я хотел бы вставить их в пустое дерево 2-3-4. Какое из этих чисел будет родительским корнем дерева и почему? Это порядок вставки, насколько велик номер? Я хотел бы иметь возможность рисовать 234 дерева, когда я даю список чисел. Я не могу этого сделать, потому что я не знаю, какой из них использовать в качестве родительского корня для начала. Просто, какой фактор указывает родительский корень этого дерева.

Answer 1

В сбалансированной древовидной структуре данных корневой элемент обычно будет содержать значение, близкое к медиане элементов, которые были добавлены к нему. Однако, поскольку дерево, как правило, не будет идеально сбалансировано, у вас может не быть точной медианы в корне. Точная структура дерева может зависеть от порядка добавления значений к нему.

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

root -> <50>
       /    \
  <30,40>  <60,70>

Но если вы добавите элементы в другом порядке, у вас может быть 40 или 60 в корне и 50 в одном из листовых узлов.