如何在TreeSet中找到元素的索引？
我正在使用TreeSet ，我非常想在集合中找到数字的索引。 有没有一种很好的方法来实际利用二叉树的O（log（n））复杂度？
（如果不是，我该怎么做，有谁知道为什么不呢？我很好奇为什么这样的类会被包含在Java中，而不会像搜索函数那样。）
正如@Yrlec所指出的， set.headSet(element).size将返回0，尽管集合中没有此元素。 所以我们最好检查一下：
return set.contains(element)? set.headSet(element).size(): -1;
这是一个显示问题的测试用例：
public static void main(String args[]){ TreeSet set = new TreeSet<>(); set.add(4); set.add(2); set.add(3); set.add(1); System.out.println(set.headSet(1).size());//0 System.out.println(set.headSet(2).size());//1 System.out.println(set.headSet(3).size());//2 System.out.println(set.headSet(4).size());//3 System.out.println(set.headSet(-1).size());//0!!Caution!,retusn 0 though it does not exits }
我在TreeSet及其接口周围探索了一段时间，我发现获取元素索引的最佳方法是：
set.headSet(element).size()
headSet(element)返回小于其参数的元素的子TreeSet ，因此该set的大小将是所讨论元素的索引。 确实是一个奇怪的解
我有同样的问题。 所以我拿了java.util.TreeMap的源代码并编写了IndexedTreeMap 。 它实现了我自己的IndexedNavigableMap ：
public interface IndexedNavigableMap extends NavigableMap { K exactKey(int index); Entry exactEntry(int index); int keyIndex(K k); }
该实现基于在更改时更新红黑树中的节点权重。 权重是给定节点下的子节点数加一个自身。 例如，当树向左旋转时：
private void rotateLeft(Entry p) { if (p != null) { Entry r = p.right; int delta = getWeight(r.left) - getWeight(p.right); p.right = r.left; p.updateWeight(delta); if (r.left != null) { r.left.parent = p; } r.parent = p.parent; if (p.parent == null) { root = r; } else if (p.parent.left == p) { delta = getWeight(r) - getWeight(p.parent.left); p.parent.left = r; p.parent.updateWeight(delta); } else { delta = getWeight(r) - getWeight(p.parent.right); p.parent.right = r; p.parent.updateWeight(delta); } delta = getWeight(p) - getWeight(r.left); r.left = p; r.updateWeight(delta); p.parent = r; } }
updateWeight只是更新权重到根：
void updateWeight(int delta) { weight += delta; Entry p = parent; while (p != null) { p.weight += delta; p = p.parent; } }
当我们需要通过索引找到元素时，这是使用权重的实现：
public K exactKey(int index) { if (index < 0 || index > size() - 1) { throw new ArrayIndexOutOfBoundsException(); } return getExactKey(root, index); } private K getExactKey(Entry e, int index) { if (e.left == null && index == 0) { return e.key; } if (e.left == null && e.right == null) { return e.key; } if (e.left != null && e.left.weight > index) { return getExactKey(e.left, index); } if (e.left != null && e.left.weight == index) { return e.key; } return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1); }
还可以非常方便地找到键的索引：
public int keyIndex(K key) { if (key == null) { throw new NullPointerException(); } Entry e = getEntry(key); if (e == null) { throw new NullPointerException(); } if (e == root) { return getWeight(e) - getWeight(e.right) - 1;//index to return } int index = 0; int cmp; if (e.left != null) { index += getWeight(e.left); } Entry p = e.parent; // split comparator and comparable paths Comparator cpr = comparator; if (cpr != null) { while (p != null) { cmp = cpr.compare(key, p.key); if (cmp > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } else { Comparable k = (Comparable) key; while (p != null) { if (k.compareTo(p.key) > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } return index; }
我将很快实现IndexedTreeSet，同时您可以使用IndexedTreeMap中的键集。
更新：现在实现了IndexedTreeSet。
您可以在http://code.google.com/p/indexed-tree-map/找到这项工作的结果。
Java中的TreeSet类无法在集合中查找数字的索引。 为此，您必须提供自己的实现 – 它是引擎盖下的红黑树，并且可以对其进行扩充以支持索引操作。 看看“算法简介”的“扩充数据结构”一章中的OS-RANK程序，它正是您所要求的。
这里显示我的function：
//为TREESET提供一席之地的职能
private static void get_posistion(TreeSet abre, String codig) { Iterator iterator; iterator = abre.iterator(); int cont = 0; String prova = ""; while (iterator.hasNext()) { prova = iterator.next().toString(); if (codig.equals(prova)) { System.out.println(cont); } else { cont++; } } }