问题标签 [treeset]

我最近遇到了一些 Java 代码，它们只是将一些字符串放入 Java TreeSet，为它实现了一个基于距离的比较器，然后在日落时分计算给定分数以解决给定问题。

我的问题，

• 是否有可用于 Python 的等效数据结构？

  • Java 树集看起来基本上是一个有序字典，可以使用某种比较器来实现这种排序。

• 我看到有一个PEP for Py3K for an OrderedDict，但我使用的是 2.6.x。那里有一堆有序的 dict 实现 - 特别是可以推荐的任何人？

PS，只是补充一下——我可能会导入 DictMixin 或 UserDict 并实现我自己的排序/排序字典，并通过比较器函数实现它——但这似乎有点矫枉过正。

谢谢。

更新。感谢您的回答。详细说明一下，假设我有一个比较函数，它的定义如下（给定一个特定的值 ln），

我有点不确定如何将其集成到此处给出的有序 dict 链接中给出的排序中......

就像是，

欢迎提出想法。

在我的代码中，Java TreeSet迭代是主要的时间因素。在查看系统时，我认为它是 O(n) 复杂度。任何人都可以验证这一点吗？

我在想，通过提供从子节点到父节点的反向链接，我可以提高性能。

我有一个这样定义的 SortedSet：

我有一个 RateMessage[] 数组

我不得不使用数组，因为该集合错过了序列化功能，现在我需要将其构造回来。

有没有一种快速的方法可以将数组中的所有项目再次添加到集合中？

我试图澄清一些有关 TreeSet 某些操作的复杂性的事情。在javadoc上它说：

“此实现为基本操作（添加、删除和包含）提供有保证的 log(n) 时间成本。”

到现在为止还挺好。我的问题是 addAll()、removeAll() 等会发生什么。这里 Set 的 javadoc 说：

“如果指定的集合也是一个集合，那么 addAll 操作会有效地修改这个集合，使其值是两个集合的并集。”

它只是解释操作的逻辑结果还是暗示了复杂性？我的意思是，如果这两个集合由例如红黑树表示，那么以某种方式加入树比将一个的每个元素“添加”到另一个要好。

无论如何，有没有办法将两个 TreeSet 组合成一个复杂度为 O(logn) 的树集？

先感谢您。:-)

所以我一直在努力解决一个问题，我想我不妨在这里寻求帮助。

我将 Ticket 对象添加到 TreeSet，Ticket 实现了 Comparable 并覆盖了 equals()、hashCode() 和 CompareTo() 方法。我需要使用 contains() 检查对象是否已经在 TreeSet 中。现在，在向集合中添加 2 个元素之后，一切都很好，但是在添加了第三个元素之后，它就搞砸了。

在向 TreeSet 添加第三个元素后运行这段小代码，Ticket temp2 是我正在检查的对象（verkoopLijst）。

返回这个：

现在我的问题是这怎么可能？

编辑：

为什么这会抛出一个ClassCastException？

有人知道一种快速检测给定元素在TreeSet中处于什么级别的方法吗？层级是指该元素在树中的深度，即其祖先的数量。

背景。 我使用 Java 的 TreeSet 类来存储我的元素。为了比较两个元素，我需要计算一些关于它们的辅助信息。我无法为每个元素存储这些辅助信息，因为它会占用太多内存。另一方面，如果我为每次比较重新生成辅助信息，我的程序就太慢了。当一个元素被插入到 TreeSet 中时，我当前的实现会计算它插入的元素的辅助信息，并且在元素在 TreeSet 中找到它的位置之前不会重新计算它。之后，辅助信息被丢弃。为了加快我的程序，我还想为 TreeSet 的顶层存储辅助信息，因为它们涉及许多比较。因此，在比较两个节点之后，

更新。 如果有人可以建议一个替代类来实现某种平衡树（AVL 树、红/黑树、Splay 树……），并且可以访问元素的高度，我也将不胜感激。

有一个 Java bean 对象已经实现了equals基于特定标准（Criteria A）的功能。我需要根据另一个标准（标准 B）识别唯一对象。由于该equals函数使用标准 A，我不能使用HashSet. 所以我想使用基于标准 B 的TreeSet自定义。我的问题是，是否允许这样做？Comparator这种方法有什么问题吗？

谢谢你。

我正在制作一个 Point2D.Float 类型的 TreeSet，并使用实现 Point2D 类型的 compare() 的自定义 Comparable 类创建它。但是，在 TreeSet 上调用“包含”时，我收到一个类转换错误：java.lang.ClassCastException: java.awt.geom.Point2D$Float cannot be cast to java.lang.Comparable

该集合是这样创建的：

这是我的比较类：

关于出了什么问题的任何想法？我已经被困在这里几个小时试图调试它无济于事。谢谢。

每种结构的优点是什么？

在我的程序中，我将执行这些步骤，我想知道我应该使用上面的哪个数据结构：

1. 接受一个未排序的数组并将它们添加到一个排序的结构1。
2. 遍历排序的数据并删除正确的数据
3. 添加数据（从不删除）并将该结构作为数组返回