• Author / Uploaded
• Edgar Ordoñez

Citation preview

INSTITUTO TECNOLOGICO DE VERACRUZ CARRERA: Ing. En Sistemas Computacionales ALUMNO: Edgar Ordoñez Ruiz PROFESOR: Córdoba del Valle Rafael MATERIA: Estructura de Datos TAREA: Árboles Balanceados y Árboles B+ HORARIO: 11am - 12pm

Árboles Balanceados Los AB, son eficientes en las operaciones de búsqueda, inserción y eliminación pero que sucede cuando el árbol crece o decrece descontroladamente, la eficiencia de la estructura de datos decae, una situación crítica es cuando se insertan elementos ordenados en un AB. Veamos el ejemplo: Insertar los datos 15, 18, 30, 60

Insertar los datos 32, 11, 9, 4

Se expanden incrementando las comparaciones n/2

9

30

60

4

La Idea Central  

Realizar reacomodos o balanceos después de inserciones o eliminaciones de elementos. Se les conoce igual como arboles AVL (autores: 2 matemáticos rusos G.M. Adelson-Velskii y E.M Landis).

Definición: Es un árbol binario de búsqueda, en la cual se cumple la siguiente condición “Para todo nodo T del árbol la altura de los subárboles izquierdo y derecho no deben diferir en más de una unidad.

Ejemplo de Árbol Balanceado

35

60

20

40

25

15

40

90

45

75

97

De altura 3 10

18

27

De altura 4 68

Calculo del Total de Nodo de un ABB (Se asemeja al cálculo de Números Fibonacci) 1. 2. 3. 4. 5.

El árbol de altura 0 es null El árbol de altura 1 = 1 nodo El árbol de altura 3 = ? Aplica la formula Kh= kh-1+1+kh-2

Ejemplo (Prueba de escritorio) K=5 = k4 +1 k3 k4 = k3 +1 k2 k3= k2+1k1 k2= k1+1+k0 k1=1 k0=0

k2=2 k3=4 k4=7 K5=12

Inserción 

CASO 1: La rama Izquierda y Derecha del árbol tienen la misma estructura Hri= hrd Por lo tanto: o si se inserta a la izquierda Hri >Hrd o si se inserta a la derecha Hrd >Hri  .

15



 .

15

15

 .

CASO 2: La altura del Ri != Rd 2.1 Hri < Hrd o Si se inserta en Hri = Equilibrio o Si se inserta en Hrd = No hay equilibrio

15

 .

 .

15

15

X



CASO 3: La altura del Ri != Rd 2.1 Hri > Hrd o Si se inserta en Hri = No hay equilibrio o Si se inserta en Hrd = Equilibrio  .

15

X

15

 .

15

Factor de Equilibrio Se calcula: Los valores que puede tomar son: -1, 0, 1. Si no son estos valores se tendrá que reestructurar el árbol. -1

-1

65

35 1 -1

0 20

70

40 0

0 15

45

0

25

-1

0 54

33

50

0

68

0

Reestructuración El proceso de inserción en un árbol balanceado es sencillo pero con detalles complicados.  Paso 1: Seguir un camino de búsqueda para localizar el lugar de la inserción.  Paso 2: Calcular el FE (obviamente 0)  Paso 3: Regresar por el camino calculando el Fe de los distintos nodos, si en algún momento se viola el criterio de equilibrio Reestructurar el árbol, significa rotar los nodos del mismo y puede ser: SIMPLE  DD (Derecha derecha)  II (izquierda, izquierda) COMPUESTA  DI (derecha izquierda)  ID (izquierda derecha)

32

11

9

-2 32

-1

0

11

9

-2

-1

0

0 11

Rotación hacia la II

0

0 9

3 2

18

2 18

30

1 30

60

0 60

0 30 0

Rotación hacia la DD

0 6 0

18

-2 18

-2 18

I

I 6

6

1

0 0

D

1

D

0

10 10

Rotación hacia la ID

0

0 6

1 8

10

-

18

18

D

D

-

-

30

30

0

0 25

I

25

Rotación hacia la DI

I 0

25 0 18

0 60

Eliminación Se tienen los mismos casos que en arboles binarios de búsqueda:  Nodo terminal u hoja se suprime  1 Descendiente (izquierda o derecha) se sustituye  2 Descendientes Buscamos en el sub izquierda el que este más a la derecha. Buscamos en el sub der el que se encuentre más a la izquierda. Para eliminar se siguen estos pasos:     

PASO 1.- Se busca la ruta. PASO 2.- Se aplica la regla anterior. PASO 3.- Regresar por el camino de búsqueda y recalcular FE (Factor de Equilibrio). PASO 4.- Si en un momento se viola la regla se reacomoda como en la inserción. PASO 5.- Se hace la operación hasta llegar al nodo raíz.

Árboles B+ Los arboles B+ son una variante de los arboles B, se diferencian en que los arboles B+ toda la información se encuentra almacenada en las hojas. En la raíz y en las páginas internas se encuentran almacenado índices o claves para llegar a un dato.

Principales características de los arboles B+ de orden m son:       

La raíz almacena como mínimo un dato y como máximo m-1 datos. La página raíz tiene como mínimo dos descendientes. Las paginas intermedias tienen como mínimo (m-1)/2(Parte entera) datos. Las páginas intermedias tienen como máximo m-1 datos. Todas las paginas hojas tienen la misma altura La información se encuentra ordenada. Toda la información se encuentra almacenada en las páginas hoja, por lo que en las páginas internas se puede duplicar las claves.

Ejemplo de un árbol B+ de orden 5:

Inserción en un árbol B+: La inserción en un árbol B+ es similar a la del árbol B se diferencia en el momento que una página deja de cumplir la condición del número de datos almacenados. Para realizarla se debe subir una copia de la clave mediana de los datos del nodo a la página padre, solo se duplica la información cuando la clave que sube es de una página hoja. Los pasos a seguir para una inserción son los siguientes: 1. Se ubica en la página raíz. 2. Se evalúa si es una página hoja 2.1. Si la respuesta es afirmativa, se evalúa si no sobrepasa los límites de datos.

2.1.1.

Si la respuesta es afirmativa, entonces se procede a insertar el nuevo valor en lugar del correspondiente. 2.1.2. Si la respuesta es negativa, se divide la página en dos, se sube una copia de la mediana a la página padre, si la página padre se encuentra llena se debe de partir igual y así el mismo proceso hasta donde sea necesario, si este proceso llega hasta la raíz la altura del árbol aumenta en uno. 2.2. Si no es hoja, se compara el elemento a insertar con cada uno de los valores almacenados para encontrar la página descendiente donde proseguir la búsqueda. Se regresa al paso 1.

Ejemplo de inserción: Insertar las siguientes claves a un árbol de orden 5: 10-27-29-17-25-21-15-31-13-51-20-24-48-1960-35-66

Eliminación: La operación de eliminación en árboles-B+ es más simple que en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las páginas hojas. En general deben distinguirse los siguientes casos:  Si al eliminar una clave, la cantidad de llaves queda mayor o igual que [m/2] entonces termina la operación. Las claves de los nodos raíz o internos no se modifican por más que sean una copia de la clave eliminada en las hojas.  Si al eliminar una clave, la cantidad de llaves queda menor que [m/2] entonces debe realizarse una redistribución de claves, tanto en el índice como en las páginas hojas.

Ejemplo del caso 1:

Ejemplo del caso 2: