寻找存储两棵层级树并高效处理节点对赋值规则的数据结构

问题背景 #

我需要存储两棵层级树（分别记为first_tree和second_tree），核心目标是判断两棵树所有叶节点对的连接是否已被覆盖，并支持高效查询叶节点对的属性值。

两棵树的层级结构为：根节点是州名（如Florida、California），子节点是城市，城市的子节点是下属区域。需要为每一对叶节点（即下属区域）分配一个属性值，可表示为函数 f: (leaf_node_first_tree × leaf_node_second_tree) → R。

由于叶节点对数量可能极大，且无法获取所有节点对的信息，我希望通过父节点层级的信息泛化属性值，为此制定了按优先级排序的赋值规则：

1. 从 State=Florida 到 State=California，赋值为 1
2. 从 city=Miami 到 city=Sacramento，赋值为 2
3. 从 sub_region=West Palm Beach 到 sub_region=east_sacramento，赋值为 3

所有节点名称（州、城市、子区域）唯一，可通过规则明确指定。规则的生效逻辑如下：

1. 找到first_tree中目标节点的所有叶节点后代（记为leaf_node_set1），以及second_tree中目标节点的所有叶节点后代（记为leaf_node_set2），将规则指定的值分配给这两个集合的笛卡尔积（leaf_node_set1 × leaf_node_set2）中的每一对叶节点。
2. 后执行的规则会覆盖先执行规则为同一叶节点对分配的属性值。

当规则作用于两棵树的根节点时，能确保所有叶节点对都被赋值，但通用规则集无法保证这一点。

补充示例 #

假设第一棵树的结构为：

根节点Florida → 子节点Miami（叶节点F1、F2）、Orlando（叶节点F3、F4）
第二棵树的结构为：
根节点California → 子节点Sacramento（叶节点C1、C2）、Los Angeles（叶节点C3、C4）
总共有16组叶节点对：[(F1,C1),(F1,C2),...,(F4,C4)]

示例1：完整覆盖规则集 #

规则集：

1. (Florida, California) → 10
2. (Miami,Sacramento) → 12
3. (F2,C2) → 15

• 应用第一条规则后，所有16组叶节点对均被赋值10；
• 应用第二条规则后，Miami的叶节点[F1,F2]与Sacramento的叶节点[C1,C2]的4组对被更新为12；
• 应用第三条规则后，(F2,C2)的值被更新为15。
  最终结果：[(F1,C1),(F1,C2),(F2,C1)]值为12，(F2,C2)值为15，其余12组对值为10。

示例2：部分覆盖规则集 #

规则集：

1. (F2,C2) → 15
2. (Miami, Sacramento) → 12

• 第二条规则覆盖第一条，因此[(F1,C1),(F1,C2),(F2,C1),(F2,C2)]的值为12；
• 其余12组叶节点对未被赋值。

核心需求 #

需要设计数据结构，同时存储两棵树及节点关联（单棵树可使用任意树形结构），并支持高效完成以下操作：

1. 给定一组赋值规则，快速判断是否所有叶节点对都已被覆盖；
2. 给定一组规则和一个叶节点对，查询该节点对的赋值。

我研究过常见树形数据结构，但它们大多适用于单树场景，本场景需要同时遍历两棵树，赋值时需考虑节点的叶节点后代。

解决方案 #

一、树结构存储优化 #

每棵树的节点需额外存储叶节点后代集合的快速索引：

• 为每个节点维护一个leaf_descendants哈希集合，记录该节点所有叶节点后代的唯一标识；
• 构建树时自底向上计算：叶节点的leaf_descendants仅包含自身，非叶节点的leaf_descendants是所有子节点leaf_descendants的并集；
• 同时为每个叶节点维护祖先链：记录从根到该叶节点的所有祖先节点（如F2的祖先链为[Florida, Miami, F2]），便于后续规则匹配。

二、规则的存储与匹配 #

将规则按优先级逆序存储（后执行的规则放在前面），每个规则包含：

• node_pair: (first_tree_node, second_tree_node)
• value: 属性值
• coverage: 预计算该规则覆盖的叶节点对数量（即len(node1.leaf_descendants) × len(node2.leaf_descendants)）

1. 叶节点对查询优化

对于任意叶节点对(L1, L2)，查询时：

• 遍历优先级从高到低的规则，检查L1是否在规则中first_tree节点的leaf_descendants里，且L2是否在规则中second_tree节点的leaf_descendants里；
• 找到第一个匹配的规则，其value即为该叶节点对的属性值；
• 若没有匹配规则，则该节点对未赋值。

优化点：利用哈希集合的O(1)成员检查特性，大幅提升匹配效率。

2. 全覆盖判断优化

计算所有规则覆盖的叶节点对的并集大小，若等于总叶节点对数量（total_leaves1 × total_leaves2），则所有节点对已被覆盖。

高效计算方式：

• 初始总未覆盖数为total_leaves1 × total_leaves2；
• 按规则优先级从高到低处理：计算当前规则覆盖的叶节点对中，未被后续高优先级规则覆盖的数量，用未覆盖数减去这个值；
• 处理完所有规则后，若未覆盖数为0，则全覆盖，否则存在未赋值节点对。

另一种思路：将两棵树的叶节点映射为连续整数区间，每个规则对应一个二维矩形区间，用区间树或线段树追踪已覆盖区域，最终判断是否填满整个大矩形。

三、推荐数据结构组合 #

1. 树节点结构：每个节点包含id、name、children、leaf_descendants（哈希集合）、is_leaf（布尔值）；
2. 规则存储：列表（按优先级逆序），每个规则包含node1_id、node2_id、value、leaf_set1（引用节点1的leaf_descendants）、leaf_set2（引用节点2的leaf_descendants）；
3. 辅助索引：
   • 节点名称到节点对象的哈希映射（快速查找规则中的节点）；
   • 叶节点到祖先链的哈希映射（加速规则匹配）。

内容的提问来源于stack exchange，提问作者Pranav Rai