2-3-4 Дерево, генерируемое из списка цифр

Question

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

Answer 1

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

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

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

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