маcсив-дерево

[leofit]

Уважаемые программисты!
Прошу совета в реализации алгоритма, из за которого уже голова кругом идет )

Имеется массив вида

[
    {'id':1, 'parent_id':0, 'title':'...'},
    {'id':2, 'parent_id':1, 'title':'...'},
    {'id':3, 'parent_id':2, 'title':'...'},
    {'id':4, 'parent_id':1, 'title':'...'},   
    {'id':5, 'parent_id':0, 'title':'...'},
    {'id':6, 'parent_id':5, 'title':'...'},
    {'id':7, 'parent_id':6, 'title':'...'},
    {'id':8, 'parent_id':7, 'title':'...'},
    {'id':9, 'parent_id':0, 'title':'...'}
]

Надо проделать на массивом некую операцию, что бы на выходе получить

[
    {
      'id':1, 
      'parent_id':0, 
      'title':'...',
      sub : [
          {
             'id':2, 
             'parent_id':1, 
             'title':'...',
             sub : [
                 {'id':3, 'parent_id':2, 'title':'...'}
             ]
          },
          {'id':4, 'parent_id':1, 'title':'...'}
      ]
     },
     {
          'id':5, 
          'parent_id':0, 
          'title':'...',
          sub: [
             {
               'id':6, 
               'parent_id':5, 
               'title':'...',
               sub: [
                   {
                       'id':7, 
                       'parent_id':6, 
                       'title':'...',
                        sub: [
                             {
                                 'id':8, 
                                 'parent_id':7, 
                                 'title':'...'
                              }
                        ]    
                   }
               ]
            }
          ]
      },
      {'id':9, 'parent_id':0, 'title':'...'}
]

Ну то есть есть корневые элементы, у них могут быть дети, у детей дети и т.п. до бесконечности, и все это должно быть в массиве (именно в массиве, к сожалению) в соответствии с иерархией родителей-детей (у каждого ребенка только один родитель).

Я делал рекурсивно, но замкнулся на том, что не знаю как вложить массив в массив рекурсивно таким образом )
Производительность роли не играет, как и язык программирования, подойдут и несколько шаговые решения (например собирать в XML-строку которую потом переводить в массив). Нужен просто алгоритм, или статьи на эту тему, или может быть кто то решал уже подобную задачу? Может быть каким то образом оптимизировать исходный массив (данные лежат в базе в примерно таком виде), или на уровне SQL-запроса такое решить можно? Буду рад любому совету!

[dark256]

Объявляем массив PARENT_IDS
Линейно перебираем в цикле по i ваши строки или, допустим объекты obj.

Пишем

PARENT_IDS[ obj [i].parent_id ] += obj [i].id+","

На выходе получаем массив ссылок:

PARENT_IDS[ 0 ] = "1,5,7,9"
PARENT_IDS[ 1 ] = "2,5"

Далее по полученным данным в двух циклах строим ваше дерево. В общих чертах. Похоже?

[leofit]

Весьма! ) Спасибо!