Estructura de Datos : Busqueda Fibonacci

Definiciones

• Criterios de particion del subarchivo remanente en la busqueda de una clave en un archivo :
  • Partir por partes iguales.
  • Partir por partes no iguales.
    • Criterio de Fibonacci.
    • Criterio de Interpolacion.
• Secuencia de Fibonacci :
  • F(0) = 0
  • F(1) = 1
  • ......
  • ......
  • ......
  • F(i) = F(i-1) + F(i-2) para todo i >= 2
• Llamamos numeros de Fibonacci los numeros enteros que forma parte de la secuencia de Fibonacci.
• Observar que no se usan divisiones o multiplicaciones, por el contrario, solo sumas y restas. Estas ultimas operaciones son mas performantes en computadoras.
• Ejemplo de Fibonacci :
  • F(0) = 0
  • F(1) = 1
  • F(2) = 1 + 0 = 1
  • F(3) = 1 + 1 = 2
  • F(4) = 2 + 1 = 3
  • F(5) = 3 + 2 = 5
  • F(6) = 5 + 3 = 8
  • F(7) = 8 + 5 = 13
  • F(8) = 13 + 8 = 21
  • F(9) = 21 + 13 = 34
  • F(10) = 34 + 21 = 55
  • F(11) = 55 + 34 = 89
  • F(12) = 89 + 55 = 144
  • ......
  • ......
  • ......
  En el siguiente grafico senalamos con ( * ) los valores enteros que formen la secuencia de Fibonacci.

          *
  --|-*-|-*-|-*-|-*-|---|-*-|---|---|-*-|---|---|---|---|-*-|---|---|---|---|---|---|---|-*-|---|---|-.........
      0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23              Numeros enteros
  
      0   1   3   4       5           6                   7                               8                       Indices de Fibonacci
          2
  

  Observar que los Numeros de Fibonacci van dejando intervalos de numeros enteros cada vez mayores a medida que el indice crece.
• Las condiciones iniciales son las siguientes :
  • Los registros del archivo ya estan en memoria principal.
  • Los registros estan almacenados secuencialmente en memoria principal.
  • Los registros del archivo los denominaremos R1, R2, R3, ..., Ri, ..., Rn donde 1=< i =< n.
  • Existen en memoria n slots, donde en cada uno de ellos se dispone un registro del archivo a clasificar.
  • Todos los registros tienen una clave Ki, donde i es 1 =< i =< n.
  • Los registros están ordenados respecto de la clave mencionada.
  • La busqueda se hara sobre el archivo a partir de una clave que se busca.
• La secuencia de acciones es la siguiente :
  • Se determina el Numero de Fibonacci mas cercano a n, pero menor a n. Lo denominaremos F(k).
  • La primer comparacion es hecha estre K y la clave de R(F(k-1)).
    • Si K < K(F(k-1)) se busca en el subarchivo isquierdo
    • Si K = K(F(k-1)) se ha hallado la clave
    • Si K > K(F(k-1)) se busca en el subarchivo derecho
• Ejemplo 1
  • Archivo de n registros con n = 100
  • Determino F(k+1) = F(12) = 144
  • Determino F(k) = F(11) = 89
  • Determino F(k-1) = F(10) = 55
• Ejemplo 2
  • Archivo de n registros con n = 35.
  • Determino F(k+1) = F(10) = 55
  • Determino F(k) = F(9) = 34
  • Determino F(k-1) = F(8) = 21
• Ejemplo 3
  • Archivo de n registros con n = 25.
  • Determino F(k+1) = F(9) = 34
  • Determino F(k) = F(8) = 21
  • Determino F(k-1) = F(7) = 13

               R1   R2   R3             Ri                   Rk             Rn
         ...------------------.......--------.............--------.......--------...............--------....
             | K1 | K2 | K3 |         | Ki |               | Kk |         | Kn |                 |    |           n slots
         ...------------------.......--------.............--------.......--------...............--------....

                                      F(k-1)                F(k)                                 F(k+1)

             |<---------------------->|    |<--------------------------------->|
                  subarchivo menor                   subarchivo mayor

Funciones

SEQSRCH

Se busca, en un archivo secuencial G, con claves ordenadas en forma creciente, por un registro Ri, tal que Ki = K La variable n es la cantidad de registros del archivo. La variable K es la clave que se busca. La variable i es la unica clave de salida, e indicara 0, si no existe la clave K en el archivo, y la posicion del registro, si la clave K existe en el archivo. Se asume que F(k) + m = n + 1. O sea, m = n + 1 - F(k).

• procedure FIBSRCH(G,n,K,i)
  • i <---- F(k-1)
  • p <---- F(k-2)
  • q <---- F(k-3)
  • if K > Ki
    • then
      • i <---- i + m
  • while i not= 0
    • do
      • case
        • :K < Ki :
          • if q = 0
            • then i <---- 0
            • else i <---- i - q; t <---- p; p <---- q; q <---- t - q
        • :K = Ki : return
        • :K > Ki :
          • if p = 1
            • then i <---- 0
            • else i <---- i + q; p <---- p - q; q <---- q - p
      • end
    • end
• end FIBSRCH

               1    2    3              q              p                  i                    r              n   n+1               s

               R1   R2   R3             Rq             Rp                 Ri                   Rk             Rn
         ...------------------.......--------.......--------...........--------.............--------.......--------..............--------.......
             | K1 | K2 | K3 |         | Kq |         | Kp |             | Ki |               | Kk |         | Kn |                |    |              n slots
         ...------------------.......--------.......--------...........--------.............--------.......--------..............--------.......


                                    q = F(k-3)     p = F(k-2)         i = F(k-1)            r =  F(k)                            s = F(k+1)

Interpretacion usando un arbol binario

Ejmeplo n = 33
        k = 8
        m = 33 + 1 - 21 = 13
        F(k)   = F(8) = 21
        F(k-1) = F(7) = 13
        F(k-2) = F(6) = 8
        F(k-3) = F(5) = 5
        F(k-4) = F(4) = 3
        F(k-5) = F(3) = 2
        F(k-6) = F(2) = 1
                                                          *---*
                                                          |2 1|                                                  Primera comparacion
                                                          *---*
                                                           | |
                                    +----------------------+ +----------------------+
                                    |                                               |
                                  *---*                                           *---*
                                  |1 3|                                           |2 9|                          Segunda comparacion
                                  *---*                                           *---*
                                   | |                                             | |
                        +----------+ +----------+                       +----------+ +----------+
                        |                       |                       |                       |
                      *---*                   *---*                   *---*                   *---*
                      | 8 |                   |1 8|                   |2 6|                   |3 2|              Tercera comparacion
                      *---*                   *---*                   *---*                   *---*
                       | |                     | |                     | |                     | |
                  +----+ +----+           +----+ +----+           +----+ +----+           +----+ +----+
                  |           |           |           |           |           |           |           |
                *---*       *---*       *---*       *---*       *---*       *---*       *---*       *---*
                | 5 |       |1 1|       |1 6|       |2 0|       |2 4|       |2 8|       |3 1|       |3 3|        Cuarta comparacion
                *---*       *---*       *---*       *---*       *---*       *---*       *---*       *---*
                 | |         | |         | |         |           | |         |           |
               +-+ +-+     +-+ +-+     +-+ +-+     +-+         +-+ +-+     +-+         +-+
               |     |     |     |     |     |     |           |     |     |           |
             *---* *---* *---* *---* *---* *---* *---*       *---* *---* *---*       *---*
             | 3 | | 7 | |1 0| |1 2| |1 5| |1 7| |1 9|       |2 3| |2 5| |2 7|       |3 0|                       Quinta comparacion
             *---* *---* *---* *---* *---* *---* *---*       *---* *---* *---*       *---*
              | |   |     |           |                       |
            +-+ 4 +-+   +-+         +-+                     +-+
            |     |     |           |                       |
          *---* *---* *---*       *---*                   *---*
          | 2 | | 6 | | 9 |       |1 4|                   |2 2|                                                  Sexta comparacion
          *---* *---* *---*       *---*                   *---*
           |
         +-+
         |
       *---*
       | 1 |                                                                                                     Septima comparacion
       *---*