我正在使用 a TreeSet<Integer>，我很想在集合中找到一个数字的索引。有没有一种很好的方法可以真正利用二叉树的 O(log(n)) 复杂性？
（如果没有，我应该怎么做，有谁知道为什么不呢？我很好奇为什么这样的类会包含在 Java 中而没有类似搜索功能的东西。）
问问题
45409 次
5 回答
55
我在 TreeSet 及其接口周围看了一会儿，我发现获取元素索引的最佳方法是：
set.headSet(element).size()
headSet(element)返回TreeSet小于其参数的元素的子元素，因此该集合的大小将是相关元素的索引。确实是一个奇怪的解决方案。
于 2011-10-27T04:26:24.683 回答
18
正如@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!
}
于 2015-04-24T05:06:14.753 回答
13
https://github.com/geniot/indexed-tree-map
我有同样的问题。所以我拿了 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;
}
于 2013-02-08T22:57:09.220 回答
1
Java 中的TreeSet类无法找到集合中数字的索引。为此，您必须提供自己的实现 - 它是底层的红黑树，并且可以对其进行扩充以支持索引操作。看看OS-RANK“算法简介”的“增强数据结构”一章中的过程，这正是您所要求的。
于 2011-10-27T04:29:57.273 回答
-2
这里显示我的功能：
//给一个字符串位置到树集中的函数
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++;
}
}
}
于 2015-11-16T19:34:04.130 回答