在 java 中,我从一个列表创建一个 SortedSet,该列表总是要排序的(但只是 ArrayList 类型)。我认为一个一个地添加它们的性能会很差(例如在 AVL 树的情况下),因为它必须对树进行大量重新排序。
我的问题是,我应该如何创建这个集合?以尽可能快的方式构建平衡树?
我计划使用的具体实现是来自 http://fastutil.dsi.unimi.it/docs/it/unimi/dsi/fastutil/ints/IntSortedSet.html 的 IntRBTreeSet 或 IntAVLTreeSet。
写完这篇文章后,我认为糟糕的性能无论如何不会对我造成太大影响(数据量太小),但我仍然对在一般情况下如何完成它感兴趣。
最佳答案
具有树实现的集合会将列表中的中间元素放在顶部。所以算法如下:
- 找到List的中间元素
- 将其插入集合
- 重复中间元素左侧和右侧的子列表
关于java - 从有序列表构建树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/576478/