Indexación

Estructura de datos. Indexado. Árboles. Inserción. Borrado. Cuentas

  • Enviado por: Jesús Alonso
  • Idioma: castellano
  • País: España España
  • 25 páginas

publicidad
cursos destacados
Aprende jQuery sin sufrimiento
Aprende jQuery sin sufrimiento
En este curso aprenderás a utilizar jQuery desde su instalación hasta que puedas hacer una galería...
Ver más información

Programación Android 01 Conceptos generales
Programación Android 01 Conceptos generales
Conceptos generales sobre el sistema operativo Android, necesarios para realizar programas para estos dispositivos....
Ver más información


TEMA 2

INDEXACIÓN

`Una piedra angular de la teoría de estructura de datos es la

distinción entre estructuras fundamentales y “avanzadas”.'

Niklaus Wirth,

`Algoritmos + Estructuras de Datos = Programas'

OBJETIVOS DE ESTE CAPÍTULO:

• Comparar las ED's básicas con sus equivalentes avanzadas

• Estudiar el concepto y propiedades fundamentales de los

árboles AVL

• Estudiar el concepto y propiedades fundamentales de los

árboles B como solución al problema de gran número de claves

• Introducir el concepto de Indexación

ÍNDICE TEMA 2.

2.1 Justificación

2.2 Criterios de equilibrio

Árbol perfectamente equilibrado

Árbol AVL

2.3 Árboles B

Concepto

Inserción

Borrado

Cuentas

2.4 Otras organizaciones de árboles B

B*

B+

2.5. Índice

2.6. Acceso secuencial Indexado

1. INDEXACIÓN.- Justificación

Formas de trabajo sobre Memoria Principal:

Tablas

Listas enlazadas

Árboles binarios de búsqueda

Formas de trabajo sobre Memoria Secundaria:

Ficheros secuenciales

Ficheros de acceso directo

  • Objetivo: Acceso directo por clave que reduzca el nº de accesos a realizar.

Algunas definiciones

Árbol de Búsqueda:

Las claves del subárbol izquierdo de un nodo son menores, y las del subárbol derecho, mayores, que la del nodo que se trata.

Árbol Ordenado:

Aquel en que las ramas de cada nodo están ordenadas

Grado:

Número de descendientes directos de un nodo interior

Grado de un Árbol:

Máximo de los grados de todos los nodos del árbol

Árbol Binario:

Árboles ordenados de Grado 2.

2. CRITERIOS DE EQUILIBRIO

Árbol perfectamente equilibrado

`Para cada nodo, `el número de nodos' del subárbol izquierdo y del derecho difieren como mucho en una unidad'

Las claves pueden estar ordenadas o no

Criterio algo `rígido'

Generación de un árbol perfectamente equilibrado:

- Hay que conocer el número de claves del árbol

- El procedimiento ha de ser recursivo

- No es necesario que el árbol esté ordenado

- Si `N' es el número de claves del árbol, se generan dos subárboles, con:

Ni = N div 2 nodos

Nd = N - Ni - 1 nodos

- Altura máxima del árbol <= log (n) + 1

-->[Author:(null)]

Árbol equilibrado

`Para cada nodo, `la longitud' del subárbol izquierdo y del derecho difieren como mucho en una unidad'

Si además el árbol es binario de búsqueda Árboles AVL (Adelson-Velskii y Landis, 1962)

Altura mínima del árbol: log ( N + 1 )

Inserción en árbol equilibrado AVL

Situación de desequilibrio. Factor de equilibrio.

Rotaciones: secuencia de rotaciones de punteros que se intercambian cíclicamente:

Simple derecha, DD

Simple izquierda, II

Doble derecha, ID(*)

Doble izquierda, DI(*)

Estado de equilibrio de cada nodo:

TYPE

tarbol = ^tnodo

tnodo = RECORD

clave: tclave;

izquierdo, derecho: tarbol;

equilibrio: -1..1;

END;

Proceso de Inserción :

Seguir el camino de búsqueda hasta ver que la clave no esta en el árbol.

  • Insertar el nuevo nodo, y obtener los nuevos valores de equilibrio.

  • Volver por el camino de búsqueda comprobando el factor de equilibrio de cada nodo

    Parámetros que se necesitan :

    Árbol donde realizar la inserción

  • Clave que se quiere insertar

  • Información de la altura del subárbol (tipo de parámetro ?)

  • Casos posibles en la realización:

    hi < hd ! a!.equilibrio = +1

    hi = hd ! a!.equilibrio = 0

    hi > hd ! a!.equilibrio = -1

    Borrado en árbol equilibrado AVL

    Proceso de Borrado:

    Búsqueda de la clave.

  • Estudio del equilibrio del árbol.

  • Parámetros que se necesitan:

    Árbol donde realizar la inserción

  • Clave que se quiere borrar.

  • Información de la altura del subárbol.

  • Casos posibles en la implementación:

    Borrado de una hoja sin desequilibrio

  • Borrado de una hoja con desequilibrio

  • Borrado de un nodo interno sin desequilibrio

  • Borrado de un nodo interno con desequilibrio

  • Caso 2: DD, II, DI, ID, Indexación

    Caso 2: DD, II, DI, ID,

    Indexación

    Caso 2: DD, II, DI, ID,

    Indexación

    3. ÁRBOLES B

    “Al buscar una forma de controlar el crecimiento, el árbol perfectamente equilibrado se deshecha inmediatamente debido al gran esfuerzo que requiere la operación de reequilibrado.”

    N. Wirth.

    Árboles MULTICAMINO: Cada nodo puede tener más de dos ramas.

    Realización:

    Array de registros

    Lista lineal

    Utilización:

    • Construcción y mantenimiento de árboles de búsqueda a gran escala.

    División del árbol en subárboles

    Páginas

    Árboles B

    El orden del árbol es n

    Todas las páginas, excepto la raíz, tienen entre n y 2n claves

    Cada página es una página-hoja (no tiene descendientes), o tiene m+1 descendientes; m ! número de claves de la página

    Todas las páginas-hoja se encuentran al mismo nivel

    Supóngase la página del árbol:

    !

    P0 K1 P1 K2 P2 ... Pm-1 Km Pm

    ! ! ! ! !

    ¿Qué casos pueden presentarse si una clave `x' no se encuentra en esta página?

    Inserción de un elemento en un árbol B

    Si la página donde se inserta tiene m > 2n nodos?

    Si “ “ “ tiene m = 2n nodos?

    Declaración de la estructura de una página:

    type pagina = record

    m: indice;

    p0: ref;

    e: array [1 .. nn] of item

    end;

    const nn = 2 * n;

    type ref = !pagina;

    indice = 0 .. nn;

    item = record

    clave: integer;

    p: ref;

    contador: integer

    end;

    Conveniencia de una formulación recursiva?

    Algoritmo de Búsqueda e Inserción en un árbol B

    Buscar ( x: integer; (* Nodo a insertar/buscar *)

    a: tArbol; (* Árbol B *)

    var cambio: boolean; (* El árbol ha crecido *)

    var u: tItem;) (* Elemento que sube de nivel *)

    if a = nil

    - copiar `x' en `u'

    - cambio := true

    else

    - buscar x en el array

    - si está ! operaciones a realizar con la clave

    - si no está !

    llamada recursiva (x, página siguiente, cambio, u)

    if cambio (* se sube un elemento *)

    - si m < 2n

    - se inserta en esa página

    - m := m + 1

    - cambio := false

    - si m = 2n

    - divide página

    - copiar en u el elemento en el medio

    end

    Borrado de un elemento en un árbol B

    Casos:

    - la clave a borrar está en una hoja

    - la clave a borrar no está en una hoja

    !

    Se sustituye por elementos adyacentes

    Número de claves de la página en un árbol B

    1.- La información se almacena dentro de la página asociada a las claves

    - Estructura para las claves: 2n * tamaño clave

    - Estructura para la información: 2n * tamaño info

    - Estructura para los descendientes: (2n + 1) * tamaño descendientes

    Tamaño de la página "

    1 + (2n * Tclave) + (2n * Tinfo) + (2n + 1) * Tdescen =

    = (1 + Tdescen) + 2n * (Tclave + Tinfo + Tdescen)

    Tpagina - (1 + Tdescen)

    n " ___________

    Tclave + Tinfo * Tdescen

    2.- La información se almacena en un TAD independiente (p.ej. un fichero).

    - Estructura para las claves: 2n * tamaño clave

    - Estructura para las posiciones: 2n * tamaño posición

    - Estructura para los descendientes: (2n + 1) * tamaño descendientes

    Tamaño de la página "

    1 + (2n * Tclave) + (2n * Tposición) + (2n + 1) * Tdescen =

    = (1 + Tdescen) + 2n * (Tclave + Tposición + Tdescen)

    Tpagina - (1 + Tdescen)

    n " ____________

    Tclave + Tposición * Tdescen

    Altura de la página de un árbol B

    En el peor caso:

    - La raíz sólo tiene una clave

    - Todas las demás páginas tienen n claves

    Nivel 1 1 sola clave-->[Author:(null)] 2 descendientes

    Nivel 2 2 pág. con n claves-->[Author:(null)] 2 * (n + 1) descen.

    Nivel 3 2 * (n + 1) pág. con n claves-->[Author:(null)] 2 * (n + 1)2 descen.

    Nivel 4 2 * (n + 1)2 pág. con n claves 2 * (n + 1)3 descen.

    .

    .

    .

    Nivel d 2 * (n + 1)d-2 pág. con n claves 2 * (n + 1)d-1 descen.

    Un razonamiento iterativo:

    - Una página tiene `n' claves `n + 1' descendientes

    - La raíz sólo tiene 1 clave

    - Un árbol con `x' claves tiene `x + 1' descendientes en el nivel de las hojas

    La altura será aquella que cumpla:

    x + 1 " Nº de descendientes al nivel de las hojas = 2 * (n + 1) d - 1

    de donde:

    d " 1 + log n*1 ((x + 1)/2)

    Árboles B*:

    Concepto de `Redistribución'

    Árboles B*:

    Árbol B especial, en el que cada nodo está lleno por lo menos en dos terceras partes (66%). Proporcionan mejor utilización del almacenamiento que los árboles B(6). La situación se genera cuando se produce una inserción al dividir, de dos páginas a tres en lugar de una a dos.

    ! Cada página tiene un máximo de m descendientes.

    ! Todas las páginas, excepto la raíz y las hojas, tiene al menos (2m - 1) / 3) descendientes.

    ! La raíz tiene al menos dos descendientes, al menos que sea `hoja'.

    ! Todas las páginas-hoja se encuentran al mismo nivel.

    ! Una página que no sea hoja, con k descendientes, contiene k - 1 claves.

    ! Una página-hoja contiene al menos [(2m - 1) / 3] claves, y no más de (m - 1)

    Árboles B+: El índice del árbol se almacena en un árbol B separado, que permite encontrar la información, que se encuentra en los registros de un fichero secuencial indexado.

    5. INDEXACIÓN

    Índice Establece un `Orden' en un fichero

    Puede ser múltiple

    Primera aproximación : tabla de registros

    Operaciones básicas de un fichero Indexado :

    Creación

    Lectura de Índice

    Actualización de Índice

    Inserción de registros

    Eliminación de registros

    Modificación de registros