sorcererxw's blog

列表转树形实现思路

January 09, 2019
问题描述

由于传统的关系型数据库的单张表里面, 所有数据都是平级的, 所以如果要存储无限层级的树形关系的时候, 只能通过子节点索引父节点来实现

JavaScript

但是, 从数据库检索出来的数据也是列表形态的, 如果需要进行展示, 就需要重新转化为树状结构, 由于是用于展示, 所以需要尽可能快地完成转换, 所以找出一种高效的转换方式非常重要.

如果保证根节点只有一个, 且数据是有序的(指符合如先序, 中序, 层序等)的情况下, 整体复杂度会降低, 但是我希望可以找出一种通用的算法, 所以限定一下几个条件:

根节点可能不止一个
每条数据之间是无序的
每条 item 的 id 非有序数, 而是 uuid
同一层级的条目保证原有顺序 (optional)
保证所有节点的 id 是唯一的
如果没有父亲, id 即为空
没有回环
层级数目没有上限
定义输入输出
Kotlin

为了保证算法可移植性, 我使用静态语言进行实现, 我选择 Kotlin, 尽可能保证代码精简.

暴力实现

建立字典 dic, 遍历 list, 对于每一个遍历的 item 做两个工作

找儿子: 检查是否有 child 已经在 dic 当中, 把儿子拉到自己的 children 中, 并从将儿子从 dic 中删除
找爹: 检查父亲节点是否已经在树里面, 检查的过程中也要考虑到爹可能已经找到了爷爷(爹的爹), 所以得一层一层往下找
如果直接找到了爹, 把自己查到爹的 children 里面
如果没有找到爹, 就把自己直接插入 dic, 等着爹来找自己

所以整个流程就是找儿子和找爹的过程, 我把它称之为孤儿院算法🤣, 因为整个 dic 就像一个孤儿院, 所有人都按顺序来找儿子, 找爹, 没找到就待着, 等着儿子和爹自己找上门来

Kotlin

孤儿院算法非常直观, 在节点数目不多地情况下, 是个不错的选择, 但是算法的效率是 O(n^2), 是不是可能存在更好的选择?

思考

在暴力解决的思路里面, 我将每个节点直接存在树里面, 每次都去树里面去检索寻找父节点, 这是暴力算法最耗时的操作, 如果能优化这一步操作, 就能够将整体效率控制在 O(nlogn) 内

如果我们设置一个特别的数据结构进行对树内节点的索引, 就能加快检索效率, 属于使用空间换时间的思路

其他
测试
Kotlin
license by-nc-nd 4.0