Увеличение элементов в структуре данных, которая следует шаблону Composite

Question

Я часто читал / слышал, что составной шаблон является хорошим решением для представления иерархических структур данных, таких как двоичные деревья, и это здорово объяснить этим шаблоном, потому что внутренние узлы - это composite объекты, а листья - leaf объекты. Я могу оценить, что, используя этот шаблон, легко посещать каждый элемент единообразно.

Однако я не уверен, что это лучший пример, если вы считаете, что дерево заполняется по требованию (каждый раз, когда выполняется метод insert), потому что мы должны преобразовать leaf в * 1007. * объект много раз (например, когда leaf должен добавить дочерний элемент). Чтобы преобразовать leaf объект, я представляю хитрый способ, подобный (вдохновлен become: от Smalltalk, я думаю):

aComposite = aLeaf.becomeComposite();
aComposite.addChild(newElement);
//destroy aLeaf (bad time performance) 

Подводя итог, является ли хорошим примером использование древовидной структуры для иллюстрации составного шаблона, если структура такого типа рождается обычно пустой, а затем необходимо добавлять / вставлять элементы?

Answer 1

GoF заявляет Намерение Композита следующим образом:

"Объединяет объекты в древовидные структуры , чтобы представлять иерархии части-целого. ..... обрабатывать отдельные элементыобъект и состав объектов одинаково "

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

Совершенно нормально строить дерево из ничего.Рассмотрим синтаксический анализатор арифметических выражений, создающий составное дерево «разбора».Синтаксический анализатор начнется с нуля и создаст конечные узлы для символов терминала (например, + - * / фигурные скобки, числа) и составные узлы, чтобы объединить терминалы для выполнения вычислений.Синтаксический анализатор создает дерево таким образом, что вызов метода define () на головном узле вызовет обход выражения для вычисления.

Я использую этот пример, чтобы показать, что дерево можно построить снизу, никогда не "преобразовывая"лист к составному объекту ".

Если ваше приложение строит дерево сверху вниз или постепенно, трудно понять, что это важно, потому что процесс сборки будет состоять из создания соответствующих узлов и вставки их способомэто имеет смысл для приложения.

Если преобразование конечных узлов в составные узлы проблематично в каком-либо конкретном приложении, то вам обязательно нужно найти способы минимизировать издержки в этой ситуации.но это только допустимая составная структура, когда дерево построено!