使用地图和路径变量生成层次结构

Question

我有一个家庭 class 从 postgres 数据库中提取数据。 class 看起来像这样：

@Entity
public class Family(){
@Id
private long id;
private String firstName;
private String lastName;
private Long parentId;
private4 String familyPath;
private List<Family> children;

//getters and setters

在数据库中，我将它们之间的关系存储为 period-delimited 字符串。因此，例如，如果 Bob 是 Sue 的 child，则树列将如下所示："bob.sue"。此路径作为家族的一部分存储在 familyPath 变量中 object。

澄清 familyPath 是基于数据库中每一行的唯一 ID 的路径。所以路径可能看起来像“1.2.3”，其中最后一个数字是当前行。 “1.2.4”是另一个可能的路径。因此 ID 为 3 和 4 的行是 children of 2，等等

在我的代码中，我在数据库中查询数据中的所有家庭成员，所以我在数据库中有一组家庭成员。我的目标是使用这个初始的平面集生成一组所有家庭成员作为层次结构。所以，最后，如果我对 Bob 调用 getChildren，我会得到一个包含 Sue 和任何其他 children.

的列表

我的解决方案：

首先，我遍历我的家族列表，找到我称之为根成员的成员——那些处于家族路径顶层的成员——并将它们移除到一个单独的列表中。所以现在我有一份顶级家庭成员的名单，还有一份其他人的名单。

然后，对于顶级列表中的每个成员，我调用以下递归方法：

private Family familyTree(Family root, List<Family> members) {
    List<Family> children = new ArrayList<>();


    for (Family f : members) {
        if (isChildOf(f, root)) {
            children.add(familyTree(f, resources));
        }
    }
    root.setChildren(children);
    return root;
}


private boolean isChildOf(Family a, Family b) {
    String pCPath = a.getFamilyPath();
    String pPPath = b.getFamilyPath();

    return pCPath.indexOf('.') >= 0
            && pCPath.substring(0, pCPath.lastIndexOf('.')).equals(pPPath);
}

并将输出保存到列表中。这会生成所需的结果。

我的问题 但是，我感觉这种递归的方法开销很大(n^2)。我在想可能有一种更有效的方法可以使用集合、映射和 Family object 的 familyPath 变量来生成此层次结构，但我一直陷入多个迭代循环。有人有想法吗？

Answer 1

选项 1 - 单程

private Family familyTree(Family root, List<Family> members) {
    Map<Long, List<Family>> parentMap = new HashMap<>();

    // Assuming root is not contained in members
    root.children  = new ArrayList<>();
    parentMap.put(root.id, root.children);

    // Assign each member to a child list
    for (Family member : members) {

        // Put the family member in the right child list
        Long parentId = member.getParentId();
        List<Family> parentChildren = parentMap.get(parentId);
        if (parentChildren == null) {
            parentChildren = new ArrayList<>();
            parentMap.put(parentId, parentChildren);
        }
        parentChildren.add(member);

        // Get or create the child list of the family member
        List<Family> ownChildren = parentMap.get(member.id);
        if (ownChildren == null) {
            ownChildren = new ArrayList<>();
            parentMap.put(member.id, ownChildren);
        }
        member.children = ownChildren;
    }
    return root;
}

private Long getParentId() {
    // left as an exercise...
}

选项1.b - 单遍遍历所有成员，包括根

private List<Family> familyTree(List<Family> members) {
    List<Family> roots = new ArrayList<>();
    Map<Long, List<Family>> parentMap = new HashMap<>();

    // Assign each member to a child list
    for (Family member : members) {

        // Put the family member in the right child list
        Long parentId = member.getParentId();
        if (parentId == null) {
            // a root member
            roots.add(member);
        } else {
            // a non-root member
            List<Family> parentChildren = parentMap.get(parentId);
            if (parentChildren == null) {
                parentChildren = new ArrayList<>();
                parentMap.put(parentId, parentChildren);
            }
            parentChildren.add(member);
        }

        // Get or create the child list of the family member
        List<Family> ownChildren = parentMap.get(member.id);
        if (ownChildren == null) {
            ownChildren = new ArrayList<>();
            parentMap.put(member.id, ownChildren);
        }
        member.children = ownChildren;
    }
    return roots;
}

选项 2 - 添加对 parent

的引用

您的 Family class 应该具有 private Family parent 属性。然后，您将能够对每个家庭进行一次查询 "level"。即：

获得苏
获取 (1) 中的所有 children 人并将他们分配给正确的 parent
等等

选项 3 - 层次结构的嵌套集模型

可以修改数据库架构以在单个查询中检索整个 sub-trees。诀窍是给每个树节点一个 "left" 和一个 "right" 值。这些值为节点的 children.

的 "left" 和 "right" 值建立了一个范围

然后可以这样选择一棵完整的树：

SELECT child.id, ...
FROM family AS child, family AS parent
WHERE child.lft BETWEEN parent.lft AND parent.rgt
    AND parent.id = 111
ORDER BY child.lft;

还有许多其他层次操作可以使用此类架构轻松完成。有关详细信息，请参阅 this post 和 Joe Celko 在 SQL 中针对聪明人 的树和层次结构。

最后，您的模型只考虑每个家庭成员一个 parent，这看起来很奇怪。

使用地图和路径变量生成层次结构

Generating Hierarchy using Maps and path variable

java

database

recursion

hashmap

hierarchy

选项 1 - 单程

选项1.b - 单遍遍历所有成员，包括根

选项 2 - 添加对 parent

选项 3 - 层次结构的嵌套集模型