我试图建立一个通用的数据结构，需要保持键和值，并在同一时间保持跟踪的索引，其中键和值被放在像arraylist做只是在复杂度为0 (log n)或更少。
我试图解决这个问题，并创建了各种TreeMaps，具有整数索引和值，反之亦然，与键相同。
为了更清楚，索引符号表示来自用户的插入顺序。所以如果我有3个元素，那么它们的索引是0 1 2，如果0号元素被删除了，那么我需要将1压入0，将2压入1，然后添加一个索引为2的新元素。
我的问题是，当我删除一个键和它的值，如果我想插入下一个键和值在正确的索引，我必须确保所有旧的被设置回1。我不知道怎样做才能不陷入O(n)的复杂度。
我的目标是使用现有的数据结构和混合它们来得到这个结果，请看看我实现的方法，因为我需要那些。
我正在添加我的代码供参考，任何帮助将不胜感激。
谢谢汤姆
import java.util.Collection;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map;
public class SuperStruct<K,V>
{
private Map<K,V> mInternalKeyToValueMap;//all the keys and their values
private Map<Integer,V> mIndexToValueMap;//index's for values according to the entrance order to
private Map<V,Integer> mValueToIndexMap;//values and their index's
private Map<Integer,K> mIndexToKeyMap;//index's and their keys according to entrance order
private Map<K,Integer> mKeyToIndexMap;//keys and their index's
private int mNextIndex;//index for the data structure according to the order data was received by user
public SuperStruct(){
mInternalKeyToValueMap = new TreeMap<K,V>();
mIndexToValueMap = new TreeMap<Integer,V>();
mValueToIndexMap = new TreeMap <V,Integer>();
mIndexToKeyMap = new TreeMap <Integer, K>();
mKeyToIndexMap = new TreeMap <K,Integer>();
}
public boolean containsKey(Object key) {
boolean containable = mInternalKeyToValueMap.containsKey(key);
return containable;
}
public boolean containsValue(Object value) {
boolean containable = mValueToIndexMap.containsKey(value);
return containable;
}
public V get(Object key) {
if(mInternalKeyToValueMap.containsKey(key)){
V value = mInternalKeyToValueMap.get(key);
return value;
}
return null;
}
public Collection<K> keySet() {
return mInternalKeyToValueMap.keySet();
}
/**
* This method is putting the key and the value in the main TreeMap "mInternalKeyToValueMap", while on the mean time updating 4 other TreeMaps
* with data regarding to the index in which data was received from the user.
* all in all this method runs in complexity of 6*(O(log n)) that sums down to O(log n) cause constants don't calculate over the whole
* Complexity calculation
* In case that a key already had a mapping to it and we overwrite the value we will run in complexity of 11*(O(log n)) which still sums down to O(log n)
* cause constants don't calculate over the whole
*/
public V put(K key, V value) {
if(mValueToIndexMap.containsKey(value))//preventing duplications of value
return value;
if(mInternalKeyToValueMap.containsKey(key)){//when a key already exist in system and we want to overwrite its value
int indexToDelete = mKeyToIndexMap.get(key);//we get the index of the value we over-write
V value1 = mIndexToValueMap.get(indexToDelete);//using this index we get the value
mValueToIndexMap.remove(value1);//we remove the value and its index
mIndexToValueMap.remove(indexToDelete);//we remove the index and its value
}
mInternalKeyToValueMap.put(key, value);//putting the new value for the key in the main TreeMap
mValueToIndexMap.put(value, mNextIndex);//populating the TreeMap of values and their index's - the order we received them from the user
mIndexToValueMap.put(mNextIndex, value);//This TreeMap holds the index's for each value according to the order of insertion by user
mIndexToKeyMap.put(mNextIndex, key);//This TreeMap holds the index's for each key according to the order of insertion by user
mKeyToIndexMap.put(key,mNextIndex);//populating the TreeMap of keys and their index's - the order we received them from the user
++mNextIndex;//advancing the index which mark the insertion order of arguments to structure
return null;
}
public V remove(Object key) {
if(mInternalKeyToValueMap.containsKey(key)==true && (mInternalKeyToValueMap.get(key)!=null))
{
V value = mInternalKeyToValueMap.get(key);
mInternalKeyToValueMap.remove(key);//removing map for the value
int mIndexToRemoveValue = mValueToIndexMap.get(value);//getting the right index to remove the value
mIndexToValueMap.remove(mIndexToRemoveValue);//vacating the value for this index
mIndexToKeyMap.remove(mIndexToRemoveValue);//vacating the key for this index
mKeyToIndexMap.remove(key);//removing a key and index in the keyToIndex Map
mValueToIndexMap.remove(value);//removing a key and index in the ValueToIndex Map
return value;
}
return null;
}
public Collection<V> values() {
return mInternalKeyToValueMap.values();
}
public Collection<V> getStrcutureSorted(){
return mValueToIndexMap.keySet();
}
public V getValueByIndex(int index){//return the index in which the value sits in, if not present null
V value = mIndexToValueMap.get(index);
return value;
}
public Integer getIndexByKey(K key){
Integer returnable = mKeyToIndexMap.get(key);
if(returnable == null)
return -1;
return returnable;
}
public K getKeyByIndex(int index){
return mIndexToKeyMap.get(index);
}
}
这是一个有趣的难题。感觉这应该是可能的，但细节难以捉摸。问题出在删除后的索引更新操作上。例如，如果索引存储在树节点中，那么在删除操作之后，平均要修改n/2个索引，这会破坏您所追求的O(log n)属性。
如果你同时在树和数组列表中存储对象，你仍然有在数组列表中定位对象的问题，我无法在少于O(n)的时间内以直接的方式工作。可能在ArrayList上有一些变化，也许是一个自定义构造，但这似乎需要做很多工作。
相反，我建议您考虑红黑树或类似的平衡树，其修改在红黑树通过有序索引访问时注意到:对于树的每个节点，也存储以给定节点为根的子树中的节点计数。在插入和删除操作期间，您必须更新受旋转操作影响的所有节点的计数。这仍然可以在O(log n)时间内完成，但它很复杂。
那么对于第k个最小(或最大)元素的二进制搜索也将在O(log n)时间内运行，与通常的递归算法一样。
这里有关于该技术的更多参考:http://www.cs.usfca.edu/~galles/cs673/lecture/lecture8.pdf, http://fdatamining.blogspot.ca/2011/09/functional-red-black-tree-with-dynamic.html, http://en.wikipedia.org/wiki/Order_statistic_tree。这应该可以让你开始了。
更新:实现细节
你要做的是创建两棵树。一个可以是普通的平衡树(比如红黑树)，用键/值对保存对对象的引用。你可以在键上搜索并在O(log n)内得到相应的值;插入和删除也将是O(log n)。此外，第一棵树中的节点将保存对第二棵树(如下)中的节点的引用。
第二个树也将保存对第一个树中的节点的引用，但它将是上面讨论的顺序统计树。插入总是将新项放在树的右端。
对该数据结构的插入操作将是普通的按键插入到第一个树中，插入到顺序统计树的右侧，并且每个插入节点中的引用将被更新为指向另一个树中的适当位置。
对于给定的键，可以在O(log n)内对第一棵树进行搜索操作，这将返回适当的值，并且可以使用对另一棵树的引用，通过遍历树到根并执行简单的计算，可以在O(log n)时间内找到第二棵树中节点的"顺序统计量"。
对于队列中的第k个位置，可以在O(log n)时间内对第二棵树进行搜索操作，返回对第二棵树的引用，该引用可以解引用以获得关联的键/值对。
在任何一棵树中删除之前，先将引用推迟到另一棵树中，然后删除第一棵树中的节点，然后删除另一棵树中相应的节点，这两个操作都是O(log n)。
我想就是这样。一切都可以在O(log n)时间内完成。第二棵树的空间开销很小，但它只包含引用;
可以吗?