java - 有没有可以对对象进行排名的树？

Question

我编写了一个红黑二叉统计树来获得与红黑树中其他对象相当的任意对象的排名。我想知道是否有提供相同功能的 API 类。

如果给定一个等级，该类也有一个函数可以在树中返回该等级的对象。

请注意，红黑 BST 允许在 log(n) 时间内执行这两个操作，其中 n 是树中对象的数量。

Answer 1

查看http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html。

Sedgewick 教授将这些树命名为 RedBlack，因此，它很可能是 RedBlack BST 的正确实现。它也有排名（在 O(lgN) 中运行）。（如果它支持删除，我不会冒险编写自己的版本）。这至少是一个很好的参考。（不在 java.util 中，唉）

Answer 2

标准 API 没有订单统计树。TreeMap特别是没有找到密钥等级或在 O(log n) 时间内按等级查找密钥的方法。

它看起来不像通常的附加库（Apache Commons Collections、Google Guava）也没有订单统计树。

Answer 3

是的，有一个TreeMap：

基于红黑树的 NavigableMap 实现。地图根据其键的自然顺序排序，或者由地图创建时提供的比较器排序，具体取决于使用的构造函数。

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。算法是对 Cormen、Leiserson 和 Rivest 的算法简介中的那些算法的改编。

---

如果给定一个等级，该类也有一个函数可以在树中返回该等级的对象。

该NavigableMap接口（由 TreeMap 实现）提供诸如floorKey和之类的方法ceilingKey。