Java 一个树结构插入问题，大佬们看看怎么办

[chunqicoder]

一个新需求，一个新的树结构要根据名称和层级匹配加入一个已有的树，如果上级层级和名称完全一样就加入目标树的子级

目前想用字符串+hashmap 做

• 先将目标树每一个最终节点及其所有上级节点扁平化为父子结构
• 然后使用名字+分隔符作为 key 存储入 map ，拿出所有的 key 组成一个组成一个集合
• 然后将新的树也扁平化不过要新增的树扁平化就按层级每一级都要和上级组成一个父子结构
• 然后用 ksy 循环使用二分查找加左精确右模糊进行匹配，查找出来再依次加入

问题：

• 1.目标树比较大，可能有上万节点
• 2.目标树扁平化处理后做 hash 会不会太大了
• 3.处理后的集合需要做 redis 缓存吗

大佬们有更好的方法求推荐

[chunqicoder]

[WashFreshFresh]

新的树结构和已有的树 是一对一 还是一对多 还是多对一

[wysnxzm]

dfa 确定有穷自动机

[netabare]

这是典型的算法题吧，不懂和 redis 有啥联系

[heiya]



- 感觉和我的需求有些类似。只不过在我这个需求中没有固定的顶级节点，每一个节点都有可能是顶级节点，而且层级是不确定的。此外，还有一种特性，顶级节点的下的某一层级的的节点很有可能又链接回了顶级节点（或者它的上层节点），例如：1_1->2_1->3_1->1_1 。
- 考察了两种解决方法。一种是把所有节点扁平化放在 mysql 中，实时查询组装成树形结构返回。另一种是使用图数据库存储。考虑到由于查询页面是在管理端，且未来数据量并不会多，并发量也不会大，最后决定使用第一种扁平化存储的方式。
- 查询方法。例如，某一个节点作为顶级节点，它的直接子节点有三个，那就开三个子线程，采用递归的方法让当前子节点作为中心节点查询，一直查询到最后一级。等到所有的线程查询完成，陆续通知主线程，最后返回，当某个线程超出时间限制没有返回时，直接丢弃。其中，要注意环的问题，判断出有环直接返回，不然递归无法跳出，直接内存溢出；还有之前通过节点查询出的数据在这个请求中要缓存一下，避免重复请求数据库。
- 递归问题。我的需求中使用缓存是不太合理的，原因是每个节点都是顶级节点，意味着每当和这个节点有关系的树形结构发生变更时都要进行缓存的更新，我感觉使用缓存不太合适。如果你的需求中顶级节点是固定的且更新不太频繁可以试一试，不过由于你说节点有上万个，是不是考虑一下是否有大 key 问题。使用 protobuff 结构所占的空间比使用 json 所占的空间要小的多。

[chunqicoder]

@heiya 大佬牛逼啊

[heiya]

@lemonteacode 牛个毛啊，应该还有别的效率好的方法

[chunqicoder]

@heiya #7 懒得想，预计我合同结束之前系统不会崩