У меня есть структура, которая не совсем пропущена, но в чем-то похожа.
существует список узлов, где каждый узел имеет прямой массив для указания на следующие узлы и обратный массив, который указывает на предыдущие узлы, размер массива задается конструктору узла и ограничен количеством элементов в список. каждый слот в массиве является ссылкой (той, на которую указывает текущий узел), и он указывает на следующий узел, размер массива которого больше или равен тому, на котором я сейчас нахожусь.
список:
public class FloorsArrayList implements DynamicSet {
//@TODO: add fields
private int bound;
private int size;
private FloorsArrayLink ninf;
private FloorsArrayLink pinf;
private int roof;
/*
* create a list with positive and negative infinity nodes
* set a bound on the number of items in the list
* initiates array with values pointing forward at POSITIVE INFINITY for NEGATIVE INFINITY
* and values pointing backwards at NEGATIVE INFINITY for POSITIVE INFINITY
* */
public FloorsArrayList(int N){
//@TODO: implement
this.bound = N;
this.size = 0;
this.roof = 0;
ninf = new FloorsArrayLink(Double.NEGATIVE_INFINITY , N+1);
pinf = new FloorsArrayLink(Double.POSITIVE_INFINITY , N+1);
for(int i = ninf.getArrSize() ; i > 0 ; i-- ) {
ninf.setNext(i, pinf) ;
pinf.setPrev(i, ninf);
}
}
@Override
/*
* returns the number of items in the list.
* @return number of items in the list.
* */
public int getSize(){
//@TODO: implement
return size;
}
@Override
/*
* method that takes a key value and an array size value
* inserts a node with those value to the list in a sorted order
* by key ( small - large)
* updates , if needed , the size of the largest array in the list
* */
public void insert(double key, int arrSize){
//@TODO: implement
FloorsArrayLink toInsert = new FloorsArrayLink(key, arrSize);
int i = arrSize;
FloorsArrayLink curr = ninf;
FloorsArrayLink next = curr.getNext(i);
while(i>0) {
while( next.getKey() < key ) {
curr = next;
next = curr.getNext(i);
}
toInsert.setPrev(i, curr);
toInsert.setNext(i, next);
next.setPrev(i, toInsert);
curr.setNext(i, toInsert);
i=i-1;
if(i>0) {
next = curr.getNext(i);
}
}
if(arrSize > roof){
roof = arrSize;
}
size++;
}
@Override
/*
* removes existing node from the list and update the pointer values
* */
public void remove(FloorsArrayLink toRemove) {
//@TODO: implement
for(int i = 1; i<= toRemove.getArrSize(); i++){
(toRemove.getNext(i)).setPrev(i, toRemove.getPrev(i));
(toRemove.getPrev(i)).setNext(i, toRemove.getNext(i));
}
}
@Override
/*
* search for a node with the specified key value and return
* the node containing it . returns null if such node does not exist.
* @return a node with a specified key value.
* @return null if there is no such node.
* */
public FloorsArrayLink lookup(double key) {
//@TODO: implement
int i = roof;
FloorsArrayLink curr = ninf;
FloorsArrayLink next = curr.getNext(i);
while(i>=0) {
while( next.getKey() <= key ) {
curr = next;
next = curr.getNext(i);
}
i=i-1;
if(i>0) {
next = curr.getNext(i);
}
}
if(curr.getKey() == key) {
return curr;
}
return null;
}
@Override
/*
* returns the successor of a given link. returns NEGATIVE INFINITY
* if link does not have a successor.
* @return the successor of given link. @return NEGATIVE INFINITY if
* link has no successor.
* */
public double successor(FloorsArrayLink link) {
//@TODO: implement
if(link.getNext(1).getKey() != Double.POSITIVE_INFINITY ){
return link.getNext(1).getKey();
}
return Double.NEGATIVE_INFINITY;
}
@Override /*
* returns the predecessor of a given link. returns POSITIVE INFINITY
* if link does not have a predecessor.
* @return the predecessor of given link. @return POSITIVE INFINITY if
* link has no predecessor.
* */
public double predecessor(FloorsArrayLink link) {
//@TODO: implement
if(link.getPrev(1).getKey() != Double.NEGATIVE_INFINITY ){
return link.getPrev(1).getKey();
}
return Double.POSITIVE_INFINITY;
}
@Override
/*
* returns minimum key value from the list.
* @return minimum key value from the list.
* */
public double minimum() {
//@TODO: implement
if(size == 0){
return Double.POSITIVE_INFINITY;
}
return ninf.getNext(1).getKey();
}
@Override
/*
* returns maximum key value from the list.
* @return maximum key value from the list.
* */
public double maximum() {
//@TODO: implement
if(size == 0){
return Double.NEGATIVE_INFINITY;
}
return pinf.getPrev(1).getKey();
}
}
узел:
public class FloorsArrayLink {
//@TODO: add fields
private double key;
private int arrSize;
private FloorsArrayLink[] fArray;
private FloorsArrayLink[] bArray;
public FloorsArrayLink(double key, int arrSize){
//@TODO: implement
this.key = key;
this.arrSize = arrSize;
this.fArray = new FloorsArrayLink[arrSize];
this.bArray = new FloorsArrayLink[arrSize];
}
/*
* returns key value
* @return key value
* */
public double getKey() {
//@TODO: implement
return this.key;
}
/*
* returns the next node in the list on the same level as i.
* @return the next node in the list on the same level as i.
* */
public FloorsArrayLink getNext(int i) {
//@TODO: implement
return this.fArray[i-1];
}
/*
* returns the previous node in the list on the same level as i.
* @return the previous node in the list on the same level as i.
* */
public FloorsArrayLink getPrev(int i) {
//@TODO: implement
return this.bArray[i-1];
}
/*
* sets the next node in the list at level i to next.
* */
public void setNext(int i, FloorsArrayLink next) {
//@TODO: implement
if(i>this.arrSize) {
return;
}
fArray[i-1]=next;
}
/*
* sets the previous node in the list at level i to previous.
* */
public void setPrev(int i, FloorsArrayLink prev) {
//@TODO: implement
if(i>this.arrSize) {
return;
}
bArray[i-1]=prev;
}
/*
* return the size of the arrays storing the pointers.
* @return size of arrays storing the pointers.
* */
public int getArrSize(){
//@TODO: implement
return arrSize;
}
}
Я понимаю, что все методы вставки, поиска и удаления выполняются во время O (n), но теперь я ввел новую структуру, которая фактически говорит, что если я нахожусь на i-м узле, размер массива будет x + 1 где x - минимальное x, такое, что i mod (2 ^ x) = 0
так, например, для 1-го узла 1 mod 2 ^ 0 = 0, поэтому размер массива будет равен 1, а для 8-го, 8 mod 2 ^ 3 = 0, поэтому размер массива будет равен 4.
теперь эта структура налагает O (log (n)) сложность времени, но у меня возникают проблемы с ее анализом. любая помощь?
