在具有许多不同类型节点的树结构中实现搜索功能

Question

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

我想在树上执行搜索，以返回对特定节点的引用。例如，假设有一棵公司树，其中包含除其他类型节点外的部门节点。部门节点包含员工节点。假定员工必须是部门的一部分，并且可以在一个部门中。

目前，设计如下：每个节点都有一个子节点列表，类型为NodeBase。树可能会变得很大，在某些情况下可能会有数十万个节点。插入/删除操作很少使用，而对于这些大树，搜索操作不应该花费“太长时间”。

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

考虑到这个树结构的设计方式，我不确定实现搜索功能的最佳方法。

可能有更好的方法来设计数据的存储方式（例如：使用数据库？），但目前我卡在了一棵树上。

- MxLDevs

---

第一个问题是：相对于插入/删除，搜索功能有多重要？你会进行大量的搜索和少量的修改吗？如果是这种情况，并且你需要更快地得到结果，那么你可以封装几个树来按每个条件进行排序。 - SJuan76

请记住，过早地进行优化是所有问题的根源，占全部问题的90.15％。只有在必要时才需要复杂化它。 - SJuan76

一些树可能有数十万个节点，因此实现快速搜索的方法将非常有用。插入/删除很少使用。需要注意的一点是，节点相当受限制（例如：只有“公司”节点才会有“部门”子节点），因此如果我需要搜索部门，我不需要搜索超出部门本身的范围。也许这将有助于决定哪种实现方式更好。 - MxLDevs

我认为公司的例子是误导性的：它仍然存在与员工相同的问题，只是由于约束条件需要搜索更少的父节点。如果您的程序只需要搜索公司，则可能会有所帮助；否则，我认为为不同类型的节点拥有单独的注册表是实现良好搜索性能的最佳方式，特别是因为对主树的更新不频繁。 - Raffaele

我认为这意味着你要为N种类型的节点保留N个单独的排序索引；当节点/子树被添加/删除到树中时，你必须修改树代码以更新这些索引。搜索是在排序后的索引上进行的 - 这也是我在答案中写的内容。 - Raffaele

Answer 1

数据结构是组织数据的方式，而你组织数据的方式取决于你如何使用这些信息。

树是回答问题“获取节点X的所有后代”正确的数据结构，但无法解决“找到属性X设置为Y的对象”这个问题（至少不是你的树：你可以在内部使用树来保持排序索引，正如我后面所解释的那样）。

因此，我认为解决这个问题的最好方法是使用两个单独的数据结构来组织数据：由NodeBase对象构成的树反映了NodeBase之间的分层关系，而排序的索引则可提供良好的查询性能。但这会引入同步问题，因为当添加/删除节点时，你必须使两个数据结构保持同步。如果这种情况并不太频繁，或者搜索性能非常重要，那么这可能是正确的方法。

- Raffaele

Answer 2

假设你的树是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建议的那样，您可以使用访问者模式。一个NodeBase应该实现一个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()));

- darijan

---

可能的改进：使用类似于 NodeBase.find(NodeFinder callback, Class<T> type) 的东西，允许每个节点使用 callback 调用自己，如果返回 false，则调用具有正确类型的每个子节点上的回调的 NodeBase.find。与返回 null 如果未找到对象相比，最好拥有某种单例 NotAMatch 实例的 NodeBase，以避免 NullPointerExceptions，但我以前没有实现过这样的东西，所以我不确定是否有必要。 - JAB

另外，也许你可以利用多核处理器，通过每次对find()的调用启动一个新线程，并为结果创建一个池，然后只需获取第一个正确的结果。但这样做会产生太多的开销吗？ - JAB

除非你所考虑的开销大小与我所想的不同，否则开销不应该成为问题。 - MxLDevs

Answer 3

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

在Java世界中，解决“分解问题”的方法有两种：

1. 面向对象的分解，具有局部性质；

2. 使用 instanceof 和类型转换进行类型检查的分解。

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

由于需要处理一个数据结构（树），其中元素（节点）的类型可能不同，因此分解的本质绝对不是局部的。因此，第二种方法确实是唯一的选择。 搜索本身可以使用二叉搜索树算法实现。这样的树需要由您的数据构建，其中将某个节点放置在哪里的决策应该取决于实际的搜索标准。基本上，这意味着您需要有与不同搜索条件一样多的树，这本质上是构建索引的一种方式。数据库引擎使用比二叉搜索树更复杂的结构。例如，red-black trees，但思想非常相似。

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

- 01es