Problema 1:

Se define una skipList como una lista enlazada en donde, además de la referencia al siguiente nodo, cada elemento puede tener otras referencias a nodos posicionados más adelante en la lista. Un ejemplo de este tipo de lista es el siguiente:

Se le pide que implemente un método de búsqueda de un elemento en una skipList. Si el elemento no se encuentra, retorne null.

Suponga que la estructura de una skipList es la siguiente:

class skipList {
  int llave;
  int k;    // número de referencias del nodo, cantidad de niveles
  skipList[] ref;
  Object info;
  int maxlevel;

  // constructor de lista vacia
  public skipList (int level) {
    maxlevel = level;
    llave = -1;  // o algún valor que signifique NULL
    info = NULL;
    ref = new skipList[maxlevel];
    for (int j = 0; j < k ; j++) ref[j] = null;
  }

  // constructor de lista con un elemento
  public skipList (Object info, int max, int llave) {
    if (max > maxlevel) max = maxlevel;
    this.k = max;
    this.llave = llave;
    this.info = info;
    ref = new skipList[k];
    for (int j = 0; j < k ; j++) ref[j] = null;
  }
}

Solución:

Object buscar(int x){
  skipList raiz = this;
  int k = maxlevel;
  while (true) {
    if (raiz.ref[k] != NULL) && (raiz.ref[k].llave <= x)
      // verifico si el siguiente nodo al nivel k es menor o mayor
      // al elemento buscado x, si es mayor paso al siguiente en el
      // nivel
      raiz = raiz.ref[k];
    else if (k>0) k--;
      // el siguiente del nivel es mayor que el buscado, bajo un nivel
    else if (k==0) && (raiz.llave >= 0)
      // estoy en el nivel 0, corto el while si encontre a la llave
      // o ya llegue a un nodo mayor que la llave
      break;
  }

  // si encontre la llave la retorno
  if (raiz.llave == x) return info;

  // este es el valor de retorno cuando no encuentro la llave
  return NULL;
}

Problema 2:

Suponga que tiene una estructura de datos compuesta por 2 subestructuras:

1. Árbol binario digital como estructura de índice. La estructura es

     ABD {
       ABD hijo0, hijo1; // puntero a hijo 0 e hijo 1
       Info datos;       // punto a una hoja en disco
     }
   

2. Hojas de almacenamiento en disco de capacidad 5

EJEMPLO DE INSERCION

Solución:

Consideremos la siguiente codificación:

A 00001 K 01011 T 10101
B 00010 L 01100 U 10110
C 00011 M 01101 V 10111
D 00100 N 01110 W 11000
E 00101 Ñ 01111 X 11001
F 00110 O 10000 Y 11010
G 00111 P 10001 Z 11011
H 01000 Q 10010
I 01001 R 10011
J 01010 S 10100

Con esto la secuencia de inserción sería:

0: E J E M P, revienta con la L

0: E J E M L, revienta con la D
1: P O

0: E E D E E, revienta con la C
1: P O S R
2: J M L I N

0: C
1: P O S R
2: J M L I N, revienta con la I
3: E E D E E

0: C
1: P O S R O
2: J I I
3: E E D E E
4: M L N N