我使用的是TreeSet<Integer>
,我很想在集合中找到数字的索引。有没有一种很好的方法可以真正利用二叉树的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<Integer> 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,returns 0 though it does not exist!
}
我在TreeSet及其接口周围戳了一会儿,发现元素的索引的最佳方法是:
set.headSet(element).size()
headSet(element)
返回小于其参数的元素的sub- TreeSet
,因此此集合的大小将为所讨论元素的索引。确实是一个奇怪的解决方案。
我有同样的问题。因此,我采用了java.util.TreeMap的源代码并编写了[[IndexedTreeMap。它实现了我自己的IndexedNavigableMap:
public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
K exactKey(int index);
Entry<K, V> exactEntry(int index);
int keyIndex(K k);
}
该实现是基于更改时更改红黑树中的节点权重。权重是给定节点下的子节点数加上一个-self。例如,当树向左旋转时:
private void rotateLeft(Entry<K, V> p) { if (p != null) { Entry<K, V> 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<K, V> 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<K, V> 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<K, V> 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<K, V> p = e.parent; // split comparator and comparable paths Comparator<? super K> 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<? super K> k = (Comparable<? super K>) 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/找到这项工作的结果更新:
TreeSet
类无法在集合中找到数字的索引。为此,您必须提供自己的实现-它是底层的一棵红黑树,可以对其进行扩展以支持索引操作。在“算法简介”的“增强数据结构”一章中查看OS-RANK
过程,这正是您所要的。//将字符串位置赋予树的功能
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++;
}
}
}