4

我有一个由数十种节点类型组成的树结构（每种类型的节点都继承自一个NodeBase类）。

我想在树上执行搜索以返回对特定节点的引用。例如，假设有Company一棵树，其中包含Department其他类型的节点中的节点。Department节点由节点组成Employee。假设员工必须属于某个部门，并且可以恰好属于一个部门。

目前，它被设计成每个节点都有一个类型为 的子节点列表NodeBase。一棵树可以变得非常大，有时有数十万个节点。很少使用插入/删除操作，而对于这些大树，搜索操作不应该花费“太长时间”。

假设我想获得一个员工节点的引用，该节点的employee ID字段等于我提供的某个字符串。我不知道员工在哪个部门，所以我必须搜索所有节点，希望找到匹配项。并非所有节点都有employee ID字段；例如，部门没有它们。

鉴于这种树形结构设计，我不确定实现搜索功能的最佳方式是什么。

首先可能有更好的方法来设计数据的存储方式（例如：使用数据库？），但目前我被树困住了。

4

3 回答 3

2

数据结构是您组织数据的方式，而组织数据的方式取决于您实际使用这些信息的方式。

树是回答“获取节点 X 的所有后代”等问题的正确数据结构，但不能帮助您解决“找到属性 X 设置为 Y 的对象”的问题（至少不是你的树：您当然可以在内部使用树来保持排序索引，我稍后会解释）。

所以我认为解决这个问题的最好方法是使用两个独立的数据结构来组织数据：一个由NodeBase对象组成的树来反映 之间的层次关系NodeBase's，以及一个排序索引来使搜索具有良好的性能。但是，这将引入一个同步问题，因为当添加/删除节点时，您必须使两个数据结构保持同步。如果它发生的频率不是太高，或者只是搜索性能很关键，那么这可能是正确的方法。

于 2013-06-13T20:21:07.353 回答
1

假设您的树是DAG（有向无环树），例如使用 DFS 或 BFS。这是一个简单的 BFS：

public NodeBase findEmployee (NodeBase root, Integer employeeId) {
    Queue<NodeBase> q= new LinkedList<NodeBase>();
    q.add(root);
    while (!q.isEmpty()) {
        NodeBase node= q.poll();
        if (node instanceof Employee) {
            if (((Employee)node).getId().equals(employeeId))
                return node;
        }
        for (NodeBase child : node.getChildren())
            q.add(child);
        }
    }
}

编辑：访客模式

或者正如Brabster建议的那样，您可以使用访问者模式。ANodeBase应该实现一个accept(IVisitor visitor)方法：

public class NodeBase {
    //your code
    public void accept(IVisitor visitor) {
        visitor.visit(this); 
        for (NodeBase node : getChildren()) {
            node.accept(visitor);
        }
    }
}

IVisitor 只是一个接口：

public interface IVisitor {
     public void visit(NodeBase node);
}

您需要一个适当的实现来进行搜索：

public class SearchVisitor implements IVisitor {

     private Integer searchId;

     public SearchVisitor(Integer searchId) {
          this.searchId= searchId;
     }

     @Override
     public void visit(NodeBase node) {
         if (node instanceof Employee) {
             if (((Employee)node).getId().equals(searchId)) {
                  System.out.println("Found the node " + node.toString() + "!");
             }
         }
     }
}

现在，您只需简单地调用它：

NodeBase root= getRoot();
root.accept(new SearchVisitor(getSearchId()));
于 2013-06-13T20:17:05.413 回答
1

看起来这个问题有两个部分——类层次结构的分解和搜索算法的实现。

在 Java 世界中，分解问题有两种可能的解决方案：

  • 面向对象的分解，具有局部性质，以及
  • instanceof使用和进行类型检查分解type casting。

函数式语言（包括 Scala）提供模式匹配，这确实是实现类型检查分解的更好方法。

由于需要使用元素（节点）可以具有不同类型的数据结构（树），因此分解的性质绝对不是局部的。因此，第二种方法确实是唯一的选择。

搜索本身可以使用例如二叉搜索树算法来实现。这样的树需要根据您的数据构建，其中放置某个节点的决定应取决于实际的搜索标准。基本上，这意味着您需要拥有与不同搜索条件一样多的树，这实质上是一种构建索引的方法。数据库引擎使用比二叉搜索树更复杂的结构。比如红黑树，但思路很相似。

顺便说一句，二叉搜索树将具有同质性。例如，如果搜索与Employeeby相关Department，则搜索树将仅包含与Employee实例关联的节点。这消除了分解问题。

于 2013-06-13T20:25:20.477 回答