Как преобразовать коллекцию категорий в древовидную структуру

Question

Я делаю селектор дерева, используя p: multiSelectListbox.У меня есть коллекция категорий, и я попытался преобразовать категории в структуру, поддерживаемую компонентами (категории не упорядочены).Вот мой бин категории:

public class Category {
    private String id;
    private String pid; //parentId
    private String name;
    private String value;

    //getter and setter
}

Это мой метод конвертации:

public List<SelectItem> tree(List<Category> categories) {
    Map<Category, SelectItem> map = new HashMap<>();

    for (Category node : categories) {
        //Check if current category is leaf node, if true new SelectItem, else new SelectItemGroup
        SelectItem item;
        if (categories.stream().noneMatch(n -> node.getId().equals(n.getPid()))) {
            item = new SelectItem(node.getValue(), node.getName());
        } else {
            item = new SelectItemGroup(node.getName());
        }
        map.put(node, item);
    }
    //the result return
    //items just add the root level, and child level add into it's parent level
    List<SelectItem> items = new ArrayList<>();

    categories.forEach(node -> {
        //get parent category of current's
        SelectItem item = map.get(categories.stream().filter(n -> n.getId().equals(node.getPid())).findFirst().orElse(null));

        //parent category is not exists, it's mean current category is root level
        if (item == null) {
            items.add(map.get(node)); //add root
        } else {
            SelectItemGroup parentGroup = (SelectItemGroup) item;
            SelectItem[] selectItems = parentGroup.getSelectItems();

            List<SelectItem> selectItemList = new ArrayList<>();
            if (selectItems != null) selectItemList.addAll(Arrays.asList(selectItems));
            //add current category into it's parent's children
            selectItemList.add(map.get(node));
            parentGroup.setSelectItems(selectItemList.toArray(new SelectItem[0]));
        }
    });

    return items;
}

Когда размер категории меньше 10000, он работает очень хорошо;если размер больше 20000, он становится очень медленным.Кто-нибудь знает более эффективный способ?

Answer 1

Эти коды будут иметь O (n ^ 2) временную сложность:

categories.forEach(node -> { //get parent category of current's SelectItem item = map.get(categories.stream().filter(n -> n.getId().equals(node.getPid())).findFirst().orElse(null))

Можно создать древовидную структуру из списка категорий в соответствии с отношением pid и id.с O (n) сложностью по времени, используя HashMap.Базовые идеи описаны ниже.

1. Пройдите по списку категорий и поместите отображение pid&id в HashMap, сложность времени: O(n).на карте у нас есть (pid:List of children ids) как Map.Entity.Теперь у нас уже есть древовидная структура.

2. Далее мы пройдемся по дереву, продемонстрированному с помощью хэш-карты, и получим результат.Именно это можно сделать либо рекурсивным способом, заданным @Ken Bekov, либо итерационным способом.Путевая проверка также занимает O(n) время.

Таким образом, сложность времени всего решения составляет O(n).Если n равно lagre, скажем 20000, оно должно быть намного быстрее, чем ваше исходное решение.