Как создать дерево из большого, сортированного списка словарей?

Question

[avigmati]

Есть такого вида список:

[
    {
        "link": "Computers/",
        "parent": None
    },
    {
        "link": "Computers/Internet/",
        "parent": "Computers/"
    },
    {
        "link": "Computers/Internet/Avatars/",
        "parent": "Computers/Internet/"
    },
...
    {
        "link": "Computers/Internet/Forums/",
        "parent": "Computers/Internet/"
    },
...
]

Его нужно преобразовать в древовидную структуру, такого вида:

{
        "link": "Computers/",
        "parent": None,
        "children": [
            {
                "link": "Computers/Internet/",
                "parent": "Computers/",
                "children": [
                    {
                        "link": "Computers/Internet/Avatars/",
                        "parent": "Computers/Internet/",
                        "children": [...]
                    },
                    {
                        "link": "Computers/Internet/Forums/",
                        "parent": "Computers/Internet/",
                        "children": [...]
                    }
                ]
            },
        ]
    }

Так как вложенность исходного списка большая то, рекурсией не получается - выдает: "Maximum recursion depth exceeded". Пробовал выставить значение:

import sys
sys.setrecursionlimit(100000)

Тогда интерпретатор вовсе вылетает с ошибкой.
Подскажите пожалуйста решение?

Comments

[Roman K]

Решением бы хоть поделился. Ну и, любую рекурсию можно заменить циклом.

Answer 1

[angru]

накидал на бумажке, работоспособность не проверял. сложность O(n), при условии, что массив отсортирован.

def transform(data):
    temp = {}

    for raw_item in data:
        item = {
            'link': raw_item['link'],
            'parent': raw_item['parent'],
            'children': [],
        }

        temp[item['link']] = item

        if not item['parent']:
            parent = item
        else:
            temp[item['parent']]['children'].append(item)

    return parent

if __name__ == '__main__':
    res = transform(sorted(data, key=lambda x: x['link']))

Answer 2

[Deadkenny]

Без рекурсии:
1. Cначала отсортировать по количеству предков.
2. Потом для каждого элемента списка(для каждого его последнего листка) искать потомков, найденных засовываем во внутрь предка(в дерево) и удаляем из списка.
3. Затем проверяем есть ли элементы с предками - одиночки, если есть, то опять к пункту 2.

Сложность тут будет наверное O(n*n)

Comments

[avigmati]

что то туплю, можно псевдокод хотя бы?