在给定一组节点的树中查找顶部记录

Question

对于这样的树，我希望从给定的节点列表中进行选择，只选择顶部节点，丢弃那些已经包含在父节点中的节点。例子树

• 世界
  • 美洲
    • 北美美国
      • 阿拉巴马州
        • 纽约*布鲁克林
          • 皇后区*
      加拿大*
  • 欧洲*德国
    意大利*
    • 法国巴黎*

给定列表:纽约、皇后区、加拿大、欧洲、意大利、巴黎

期望输出为:New-York, Canada, Europe.

(皇后被丢弃，因为它在纽约;意大利被丢弃，因为它在欧洲;巴黎被丢弃，因为它也在欧洲，等等)

我的树物理上是在一个oracle表树记录id, parent_id

在这种情况下应用的最优算法是什么?避免不必要的DB调用。

Answer 1

如果列表中的值的数量相对于表中的值的数量较小，那么您可以从与列表值对应的记录开始，然后在树中向上走，直到到达根或到达列表中的另一个值。只保留那些向上搜索在根处停止的结果。

我假设id和parent_id字段是国家的名称(或者它们可以是唯一的数字，国家的名称在第三个字段中)。我还假设存在一条记录，其中id等于'World'，对应的parent_id为NULL。

那么你可以在Oracle数据库上用一个SQL查询来完成:

SELECT id
FROM (
SELECT     CONNECT_BY_ROOT id id,
parent_id
FROM       tbl
START WITH id IN ('New-York', 'Queens', 'Canada', 'Europe', 'Italy', 'Paris')
CONNECT BY PRIOR parent_id = id 
AND id NOT IN ('New-York', 'Queens', 'Canada', 'Europe', 'Italy', 'Paris')
) 
WHERE parent_id IS NULL;

该列表在查询中出现两次，一次表示从哪个记录开始，一次表示向上遍历应该在何时终止。

最后的WHERE子句确保来自列表的路径到达根，并且不会在列表中的另一个值处中止。

上面的查询返回您所描述的树的结果:

Canada
Europe
Queens

查看在SQL Fiddle上运行

Answer 2

显然，最坏的情况是你必须遍历整个树，例如，如果你的搜索目标都不在树中，或者它们恰好是你访问的最后N个叶子。

因此，任何树遍历算法都可以工作，只要您找到一个目标值，就停止搜索在该节点上扎根的子树。这将避免不必要地搜索子树，因为子树除了根树之外不能有任何其他顶级项。在您的示例中，遍历可能如下所示:

世界，北美，美国，阿拉巴马州，纽约(这是一个匹配;返回并返回到树的某个地方，直到有一个未访问的子节点)，加拿大(这是一个匹配;返回并返回到树的某个地方，直到有一个未访问的孩子)，欧洲(这是一个匹配;返回并返回树，直到有一个未访问的子节点)。