Árboles Balanceados
Cuando se estudiaron los arboles binarios de búsqueda se menciono que es una estructura sobre la cual se pueden realizar eficientemente las operaciones de búsqueda, inserción y eliminación. Sin embargo, si el árbol crece o decrece descontroladme, el rendimiento puede disminuir considerablemente. El caso más desfavorable se produce cuando se inserta un conjunto de claves ordenadas en forma ascendente o descendente.
Es de notar que el número promedio de comparaciones que se deben realizar para localizar una determinada clave en un árbol binario de búsqueda con crecimiento descontrolado es N/2, cifra que muestra un rendimiento muy pobre en la estructura.
Con el objeto de mantener la eficiencia en la operación de búsqueda surgen los arboles balanceados.La principal característica de estos es la de realizar reacomodos o balanceos, después de inserciones o eliminaciones de elementos. Estos arboles tén reciben el nombre de AVL en honor a sus inventores, dos matemáticos rusos, G. M. Adelson-Velskii y E. M. Landis.
Formalmente se define un árbol balanceado como un árbol binario de búsqueda, en el cual se debe cumplir la siguiente condición: Para todo nodo T del árbol, la altura de los subárbols izquierdo y derecho no deben diferir en más de una unidad.
Donde HRI es la altura de la rama o subárbol izquierdo y HRD es la altura de la rama o subárbol derecho.
Los arboles balanceados se parecen mucho, en su mecanismo de formación, a los números Fibonacci. El árbol de altura 0 es vacío, el árbol de altura 1 tiene un único nodo y, en general, el número de nodos del árbol con altura h > 1 se calcula aplicando la siguiente formula recursiva:
donde Kindica el número de nodos del árbol y hla altura.
Por otra parte, algunos estudios demuestran que la altura de un árbol balanceado de n nodos nunca excederá de 1.44 * log n.
Inserción en árboles balanceados
Al insertar un elemento en un árbol balanceado se deben distinguir los siguientes casos:
1. Las ramas izquierda (RI) y derecha (RD) del árbol tienen la misma altura (HRI = HRD) por lo tanto:
1.1 Si se inserta un elemento en RI, entonces HRI será mayor en una unidad.
1.2 Si se inserta un elemento en RD, entonces HRD será mayor en una unidad.
Observe que en cualquiera de los dos casos mencionados (1.1 y 1.2), no se viola el criterio de equilibrio del árbol.
2. Las ramas izquierda (RI) y derecha (RD) del árbol tienen altura diferente
2.1 Supongamos que HRI < HRD :
2.1.1 Si se inserta un elemento en RI, entonces HRI será igual a HRD . las ramas tienen la misma altura, por lo que se mejora el equilibrio de y no es necesario estructurarlo
2.1.2 Si se inserta un elemento en RD, entonces se rompe el criterio de equilibrio del árbol y es necesario reestructurarlo.
2.2 Supongamos que HRI > HRD:
2.2.1 Si se inserta un elemento en RI, entonces se rompe el criterio de equilibrio del árbol y es necesario reestructurarlo.
2.2.2 Si se inserta un elemento en RD, entonces HRD será igual a HRI Las ramas tienen la misma altura, por lo que se mejora el equilibrio del árbol
Ahora bien, para poder determinar si un árbol esta balanceado o no, se debe manejar información relativa al equilibrio de cada nodo del árbol. Surge así el concepto de factor de equilibrio de un nodo(FE) que se define como la altura del subárbol derecho menos la altura del subárbol izquierdo.
A continuación se presenta la definición de un árbol balanceado en lenguaje algorítmico.
ENLACE = ^NODO
NODO = REGISTRO
IZQ, DER: tipo ENLACE
INFO: tipo de dato
FE: -1 … 1
Fin de la definición
NODO = REGISTRO
IZQ, DER: tipo ENLACE
INFO: tipo de dato
FE: -1 … 1
Fin de la definición
Reestructuración del árbol balanceado
El proceso de inserción en un árbol balanceado es sencillo, sin embargo requiere operaciones auxiliares que complican parcialmente el proceso. Primero se debe seguir el camino de búsqueda del árbol, hasta localizar el lugar donde hay que insertar el elemento. Luego se calcula su FE, que obviamente será 0, y regresamos por el camino de búsqueda calculando el FE de los distintos nodos visitados. Si en alguno de los nodos viola el criterio de equilibrio entonces se debe reestructurar el árbol. El proceso termina al llegar a la raíz del árbol, o cuando se realiza la reestructuración del mismo, en cuyo caso no es necesario determinar el FE de los nodos restantes.
Reestructurar el árbol significa rotar los nodos del mismo para llevarlo a un estado de equilibrio. La rotación puede ser simple o compuesta. El primer caso involucra dos nodos y el segundo caso afecta a tres. Si la rotación es simple se puede realizar por las ramas derechas (DD) o por las ramas izquierdas (IT). Si por otra parte la rotación es compuesta se puede realizar por las ramas derecha e izquierda (DI) o por las ramas izquierda y derecha (ID).
Inserta_balanceado(NODO, BO, INFOR)
El algoritmo inserta un elemento en un árbol balanceado. NODO es un parámetro de tipo puntero, por referencia. BO es un parámetro de tipo booleano, por referencia. BO se utiliza para indicar que la altura del árbol ha crecido, su valor inicial es FALSO. INFOR es un parametro de tipo entero que contiene la información del elemento que queremos insertar
OTRO, NODOl y NODO2 son variables auxiliares de tipo puntero
El algoritmo inserta un elemento en un árbol balanceado. NODO es un parámetro de tipo puntero, por referencia. BO es un parámetro de tipo booleano, por referencia. BO se utiliza para indicar que la altura del árbol ha crecido, su valor inicial es FALSO. INFOR es un parametro de tipo entero que contiene la información del elemento que queremos insertar
OTRO, NODOl y NODO2 son variables auxiliares de tipo puntero
1. Si (NODO ≠ NULO)
entonces
1.1 Si (INFOR < NODO^.INFO)
entonces
Regresar a Inserta_balanceado con NODO^.IZQ, BO e INFOR
Llamada recursiva
1.1.1 Si (BO = VERDADERO)
entonces
1.1.1.1 Si (NODO^. FE) = 1: Hacer NODO^.FE <- 0 y BO <-FALSO = 0: Hacer NODO^.FE <- -1
= -1: Hacer NODO1 <- NODO^.IZQ Reestructuración del árbol
1.1.1.1.1 Si (NODO^.FE ≤0)
entonces Rotación II
Hacer NODO^.IZQ <- NODO1^.DER,
NODO1^.DER <- NODO,
NODO^.FE <-0 y NODO <-NODOl Termina la rotación II
si no Rotación ID
Hacer NODO2 <- NODO1^.DER,
NODO^.IZQ <- NODO2^.DER,
NODO2^.DER <- NODO,
NODO1^.DER <- NODO2^.IZQ y
NODO2^.IZQ <- NODOl
1.1.1.1.1.A Si(NODO2^.FE = -l)
entonces
Hacer NODO^.FE <- -1
si no
Hacer NODO^.FE <- 0
1.1.1.1.1.B. Fin del condicional del paso 1.1.1.1.1.A
1.1.1.1.1.C Si(NODO2^.FE = l)
entonces
Hacer NODO1^. FE <- -1
si no
Hacer NODOl^. FE <- 0
1.1.1.1.1.D. Fin del condicional del paso 1.1.1.1.1.C
Hacer NODO <- NOD02
Termina la rotación ID
1.1.1.1.2 Fin del condicional del paso 1.1.1.1.1
Hacer NODO^.FE <- 0 y BO <- FALSO
1.1.1.2 Fin del condicional del paso 1.1.1.1
1.1.2 Fin del condicional del paso 1.1.1
si no
1.1.3 Si (INFOR > NODO^.INFO)
entonces
Regresar a Inserta_balanceado con NODO^.DER, BO e INFOR
Llamada recursiva
1.1.3.1 Si (BO = VERDADERO)
entonces
1.1.3.1.1 Si (NODO^.FE)
= -1: Hacer NODO^.FE <- 0 y BO <- FALSO
= 0: Hacer NODO1^.FE <- 1
= 1: Hacer NODOl <-NODO^.DER
Reestructuración del árbol
1.1.3.1.1.A Sí (NODOl^.FE ≥ 0)
entonces Rotación DD
Hacer NODO^.DER <- NODOl^.IZQ,
NODO1^.IZQ <- NODO,
NODO^.FE <- 0 y NODO <- NODOl
Termina la rotación DD
si no Rotación DI
Hacer NODO2 <- NODO1^.IZQ,
NODO^.DER <- NODO2^.IZQ,
NODO2^.IZQ <- NODO,
NODO1^.IZQ <- NODO2^.DER y
NODO2^.DER <- NODOl
(NODO2^.FE = 1)
entonces
Hacer NODO^.FE <- 1
si no
Hacer NODO^.FE <- 0
Fin del condicional interno
Sí (NOD02^.FE = -l)
entonces
Hacer NODO1^. FE <- -1
si no
Hacer NODO1^.FE <- 0
Fin del condicional interno
Hacer NODO <- NODO2
Termina la rotación DI
1.1.3.1.1.B Fin del condicional del paso 1.1.3.1.1.A
Hacer NODO^.FE <- 0 y BO <- FALSO
1.1.3.1.2 Fin del condicional del paso 1.1.3.1.1
1.1.3.2 Fin del condicional del paso 1.1.3.1
si no
Escribir “La información ya se encuentra en el árbol”
1.1.4 Fin del condicional del paso 1.1.3
1.2 Fin del condicionante del paso 1.1
Si no
Crear(NODO)
Hacer NODO^.INFO <- INFOR, NODO^.IZQ <- NULO, NODO^.DER <- NULO, NODO^.FE <- 0 y
BO <- VERDADERO
2. Fin del condicional del paso 1
entonces
1.1 Si (INFOR < NODO^.INFO)
entonces
Regresar a Inserta_balanceado con NODO^.IZQ, BO e INFOR
Llamada recursiva
1.1.1 Si (BO = VERDADERO)
entonces
1.1.1.1 Si (NODO^. FE) = 1: Hacer NODO^.FE <- 0 y BO <-FALSO = 0: Hacer NODO^.FE <- -1
= -1: Hacer NODO1 <- NODO^.IZQ Reestructuración del árbol
1.1.1.1.1 Si (NODO^.FE ≤0)
entonces Rotación II
Hacer NODO^.IZQ <- NODO1^.DER,
NODO1^.DER <- NODO,
NODO^.FE <-0 y NODO <-NODOl Termina la rotación II
si no Rotación ID
Hacer NODO2 <- NODO1^.DER,
NODO^.IZQ <- NODO2^.DER,
NODO2^.DER <- NODO,
NODO1^.DER <- NODO2^.IZQ y
NODO2^.IZQ <- NODOl
1.1.1.1.1.A Si(NODO2^.FE = -l)
entonces
Hacer NODO^.FE <- -1
si no
Hacer NODO^.FE <- 0
1.1.1.1.1.B. Fin del condicional del paso 1.1.1.1.1.A
1.1.1.1.1.C Si(NODO2^.FE = l)
entonces
Hacer NODO1^. FE <- -1
si no
Hacer NODOl^. FE <- 0
1.1.1.1.1.D. Fin del condicional del paso 1.1.1.1.1.C
Hacer NODO <- NOD02
Termina la rotación ID
1.1.1.1.2 Fin del condicional del paso 1.1.1.1.1
Hacer NODO^.FE <- 0 y BO <- FALSO
1.1.1.2 Fin del condicional del paso 1.1.1.1
1.1.2 Fin del condicional del paso 1.1.1
si no
1.1.3 Si (INFOR > NODO^.INFO)
entonces
Regresar a Inserta_balanceado con NODO^.DER, BO e INFOR
Llamada recursiva
1.1.3.1 Si (BO = VERDADERO)
entonces
1.1.3.1.1 Si (NODO^.FE)
= -1: Hacer NODO^.FE <- 0 y BO <- FALSO
= 0: Hacer NODO1^.FE <- 1
= 1: Hacer NODOl <-NODO^.DER
Reestructuración del árbol
1.1.3.1.1.A Sí (NODOl^.FE ≥ 0)
entonces Rotación DD
Hacer NODO^.DER <- NODOl^.IZQ,
NODO1^.IZQ <- NODO,
NODO^.FE <- 0 y NODO <- NODOl
Termina la rotación DD
si no Rotación DI
Hacer NODO2 <- NODO1^.IZQ,
NODO^.DER <- NODO2^.IZQ,
NODO2^.IZQ <- NODO,
NODO1^.IZQ <- NODO2^.DER y
NODO2^.DER <- NODOl
(NODO2^.FE = 1)
entonces
Hacer NODO^.FE <- 1
si no
Hacer NODO^.FE <- 0
Fin del condicional interno
Sí (NOD02^.FE = -l)
entonces
Hacer NODO1^. FE <- -1
si no
Hacer NODO1^.FE <- 0
Fin del condicional interno
Hacer NODO <- NODO2
Termina la rotación DI
1.1.3.1.1.B Fin del condicional del paso 1.1.3.1.1.A
Hacer NODO^.FE <- 0 y BO <- FALSO
1.1.3.1.2 Fin del condicional del paso 1.1.3.1.1
1.1.3.2 Fin del condicional del paso 1.1.3.1
si no
Escribir “La información ya se encuentra en el árbol”
1.1.4 Fin del condicional del paso 1.1.3
1.2 Fin del condicionante del paso 1.1
Si no
Crear(NODO)
Hacer NODO^.INFO <- INFOR, NODO^.IZQ <- NULO, NODO^.DER <- NULO, NODO^.FE <- 0 y
BO <- VERDADERO
2. Fin del condicional del paso 1
Eliminación en árboles balanceados
La operación de eliminación en árboles balanceados es un poco más compleja que la operación de inserción, como normalmente ocurre en casi todas las estructuras de datos. Esta consiste en quitar un nodo del árbol sin violar los principios que definen un árbol balanceado. Recuerde que se definió como una estructura en la cual, para todo nodo del árbol, se debe cumplir que: la altura del subárbol izquierdo y la altura del subárbol derecho no deben diferir en más de una unidad.
Eliminar nodos en un árbol balanceado resulta difícil a pesar de que se utiliza mismo algoritmo de eliminación, idéntico en lógica pero diferente en implementación que en los árboles binarios de búsqueda y las mismas operaciones de reacomodo que se utilizan en el algoritmo de inserción en arboles balanceados.
En la operación de eliminación en arboles balanceados se deben distinguir los siguientes casos:
1. Si el elemento a eliminar es terminal u hoja, simplemente se suprime.
2. Si el elemento a eliminar tiene un solo descendiente, entonces se tiene que sustituir por ese descendiente.
3. Si el elemento a eliminar tiene los dos descendientes, entonces se tiene que sustituir por el nodo que se encuentra más a la izquierda en el subárbol derecho o por el que se encuentra más a la derecha en el subárbol izquierdo.
Para eliminar un nodo en un árbol balanceado lo primero que se debe hacer es localizar su position en el árbol. Se elimina siguiendo los criterios establecidos anteriormente y se regresa por el camino de búsqueda calculando el FE de los nodos visitados. Si en alguno de los nodos se viola el criterio de equilibrio, entonces se debe reestructurar el árbol. El proceso termina cuando se llega a la raíz del árbol. Cabe aclarar que mientras que en el algoritmo de inserción una vez efectuada una rotación se podía detener el proceso, en este algoritmo se debe continuar puesto que se puede producir más de unarotación en el camino hacia atrás.
Con el fin de darle mayor modularidad al algoritmo de eliminación en arboles balanceados, se estudiaran dos algoritmos auxiliares. El primero, Reestructura_izq, se utiliza cuando la altura de la rama izquierda ha disminuido. El segundo, Reestructura_der, se emplea cuando la altura de la rama derecha ha disminuido.
Reestructura_izq (NODO, BO)
Este algoritmo reestructura el árbol cuando la altura de la rama izquierda ha disminuido y el FE de NODO es igual a 1. NODO es un parámetro por referencia de tipo puntero. BO es un parámetro de tipo booleano, también por referencia. BO se utiliza para indicar que la altura de la rama izquierda ha disminuido) NODOl y NODO2 son variables auxiliares de tipo puntero
1. Sí(BO = VERDADERO)
entonces
1.1 Si (NODO^.FE)
= -1: Hacer NODO^.FE <- 0
= -0: Hacer NODO^.FE <- 1 y BO <- FALSO
= -1: Restructuración del árbol
Hacer NODOl <- NODO^.DER
1.1.1 Sí (NODO1^.FE ≥ 0)
entonces Rotación DD
Hacer NODO^.DER <- NODO1^.IZQ y
NODO1^.IZQ <-NODO
1.1.1.1 Sí NODO1^.FE
= 0: Hacer NODO^.FE <- 1, NODO1^.FE <- -1 y BO <-FALSO
= 1: Hacer NODO^.FE <- 0 y NODO1^.FE <- 0
1.1.1.2 Fin del condicional 1.1.1.1
Hacer NODO <- NODOl
Termina la rotación DD
si no Rotación DI
Hacer NODO2 <- NODO1^.IZQ,
NODO^.DER <- NODO2^.IZQ,
NODO2^.IZQ <- NODO,
NODO1^.IZQ <- NODO2^.DER y
NODO2^.DER <- NODO1
1.1.1.3 Sí(NODO2^.FE = l)
entonces
Hacer NODO^.FE <- 1
si no
Hacer NODO^.FE <- 0
1.1.1.4 {Fin del condicional 1.1.1.3}
1.1.1.5 Si (NODO2^.FE = -1)
entonces
Hacer NODO1^.FE <-- 1
si no
Hacer NODOl^.FE <- 0
1.1.1.6 Fin del condicional 1.1.1.5
Hacer NODO <- NODO2 y NODO2^.FE <- 0
Termina la rotación DI
1.1.2. Fin del condicional del paso 1.1.1
1.2 Fin del condicional del paso 1.1
2. Fin del condicional del paso 1
entonces
1.1 Si (NODO^.FE)
= -1: Hacer NODO^.FE <- 0
= -0: Hacer NODO^.FE <- 1 y BO <- FALSO
= -1: Restructuración del árbol
Hacer NODOl <- NODO^.DER
1.1.1 Sí (NODO1^.FE ≥ 0)
entonces Rotación DD
Hacer NODO^.DER <- NODO1^.IZQ y
NODO1^.IZQ <-NODO
1.1.1.1 Sí NODO1^.FE
= 0: Hacer NODO^.FE <- 1, NODO1^.FE <- -1 y BO <-FALSO
= 1: Hacer NODO^.FE <- 0 y NODO1^.FE <- 0
1.1.1.2 Fin del condicional 1.1.1.1
Hacer NODO <- NODOl
Termina la rotación DD
si no Rotación DI
Hacer NODO2 <- NODO1^.IZQ,
NODO^.DER <- NODO2^.IZQ,
NODO2^.IZQ <- NODO,
NODO1^.IZQ <- NODO2^.DER y
NODO2^.DER <- NODO1
1.1.1.3 Sí(NODO2^.FE = l)
entonces
Hacer NODO^.FE <- 1
si no
Hacer NODO^.FE <- 0
1.1.1.4 {Fin del condicional 1.1.1.3}
1.1.1.5 Si (NODO2^.FE = -1)
entonces
Hacer NODO1^.FE <-- 1
si no
Hacer NODOl^.FE <- 0
1.1.1.6 Fin del condicional 1.1.1.5
Hacer NODO <- NODO2 y NODO2^.FE <- 0
Termina la rotación DI
1.1.2. Fin del condicional del paso 1.1.1
1.2 Fin del condicional del paso 1.1
2. Fin del condicional del paso 1
Reestructura der (NODO, BO)
Este algoritmo reestructura el árbol cuando la altura de la rama derecha ha disminuido y el FE de NODO es igual a -1. NODO es un parámetro por referencia, de tipo puntero. BO es un parámetro de tipo booleano, también por referencia. BO se utiliza para indicar que la altura de la rama derecha ha disminuido NODOl y NODO2 son variables auxiliares de tipo puntero
1.Sí (BO = VERDADERO)
entonces
1.1 Sí NODO^.FE
= 1 : Hacer NODO^.FE <- 0
= 0 : Hacer NODO^.FE <- -1 y BO <- FALSO
= -1: Reestructuración del árbol
Hacer NODOl <- NODO^.IZQ
1.1.1 Si (NODO1^.FE ≤ 0)
entonces Rotación II
Hacer NODO^.IZQ <- NODO1^.DER y
NODO1^.DER <- NODO
1.1.1.1 Si NODO1^.FE
= -0: Hacer NODO^.FE <- -1, NODO1^.FE <-1 y BO <- FALSO
= -1: Hacer NODO^.FE <- 0 y NODOl^.FE<-0
1.1.1.2 Fin del condicional del paso 1.1.1.1
Hacer NODO <- NODOl
Termina la rotación II
si no Rotación ID)
Hacer NODO2 <- NODOl^.DER,
NODO^.IZQ <- NODO2^.DER
NODO2^.DER <- NODO,
NODO1^.DER <- NODO2^.IZQ
NODO2^.IZQ <-NODOl
1.1.1.3 Sí(NODO2^.FE = -l)
entonces
Hacer NODO^.FE <- 1
si no
Hacer NODO^.FE <- 0
1.1.1.4 Fin del condicional del paso 1.1.1.3
1.1.1.5 Sí(NODO2^.FE = l)
entonces
Hacer NODO1^.FE <- -1
Hacer NODO1^.FE <- 0
1.1.1.6 Fin del condicional del paso 1.1.1.5
Hacer NODO <- NODO2 y NODO2^.FE <- 0
Termina la rotación ID
1.1.2 Fin del condicional del paso 1.1.1
1.2 Fin del condicional del paso 1.1
2. Fin del condicional del paso 1
entonces
1.1 Sí NODO^.FE
= 1 : Hacer NODO^.FE <- 0
= 0 : Hacer NODO^.FE <- -1 y BO <- FALSO
= -1: Reestructuración del árbol
Hacer NODOl <- NODO^.IZQ
1.1.1 Si (NODO1^.FE ≤ 0)
entonces Rotación II
Hacer NODO^.IZQ <- NODO1^.DER y
NODO1^.DER <- NODO
1.1.1.1 Si NODO1^.FE
= -0: Hacer NODO^.FE <- -1, NODO1^.FE <-1 y BO <- FALSO
= -1: Hacer NODO^.FE <- 0 y NODOl^.FE<-0
1.1.1.2 Fin del condicional del paso 1.1.1.1
Hacer NODO <- NODOl
Termina la rotación II
si no Rotación ID)
Hacer NODO2 <- NODOl^.DER,
NODO^.IZQ <- NODO2^.DER
NODO2^.DER <- NODO,
NODO1^.DER <- NODO2^.IZQ
NODO2^.IZQ <-NODOl
1.1.1.3 Sí(NODO2^.FE = -l)
entonces
Hacer NODO^.FE <- 1
si no
Hacer NODO^.FE <- 0
1.1.1.4 Fin del condicional del paso 1.1.1.3
1.1.1.5 Sí(NODO2^.FE = l)
entonces
Hacer NODO1^.FE <- -1
Hacer NODO1^.FE <- 0
1.1.1.6 Fin del condicional del paso 1.1.1.5
Hacer NODO <- NODO2 y NODO2^.FE <- 0
Termina la rotación ID
1.1.2 Fin del condicional del paso 1.1.1
1.2 Fin del condicional del paso 1.1
2. Fin del condicional del paso 1
A continuación se presenta el algoritmo de eliminación en arboles balanceados, el cual hará uso de los previamente explicados.
Elimina_balanceado (NODO, BO, INFOR)
El algoritmo elimina un elemento en un árbol balanceado. Utiliza dos algoritmos auxiliares Reestructura izq y Reestructura der. NODO es un parámetro por referencia de tipo puntero. BO es un parámetro de tipo booleano, también por referencia, y se utiliza para indicar que si la altura del árbol ha disminuido, su valor inicial es FALSO. INFOR es un parámetro de tipo entero que contiene la información del elemento que se quiere eliminar OTRO, AUX, AUX1 son variables auxiliares de tipo puntero. BOOL es una variable de tipo booleano
1. Si (NODO ≠ NIL)
entonces
1.1 Si (INFOR < NODO^.INFO)
entonces
Regresar a Elimina_balanceado con NODO^.IZQ, BO e INFOR
Llamar al algoritmo Reestructura_izq con NODO y BO
si no
1.1.1 Si (INFOR > NODOMNFO)
entonces
Regresar a Elimina_balanceado con NODO^.DER, BO e INFOR
Llamar al algoritmo Reestructura_der con NODO y BO
si no
Hacer OTRO <- NODO y BO <- VERDADERO
1.1.1.1 Si (OTRO^.DER = NULO)
entonces
Hacer NODO <- OTRO^.IZQ
si no
1.1.1.1.1 Si (OTRO^.IZQ = NULO)
entonces
Hacer NODO <-OTRO^.DER
Hacer AUX <- NODO^.IZQ y BOOL <- FALSO
1.1.1.1.1.A Mientras (AUX^.DER ≠ NULO) Repetir
Hacer AUX1 <- AUX,
AUX <- AUX^.DER y
BOOL <- VERDADERO
1.1.1.1.1.B {Fin del ciclo del paso 1.1.1.1.1.A }
Hacer NODO^.INFO <- AUX^.INFO y
OTRO <-AUX
1.1.1.1.1.C Si (BOOL = VERDADERO)
entonces
Hacer AUX1^.DER <- AUX^.IZQ
si no
Hacer NODO^.IZQ <- AUX^.IZQ
1.1.1.1.1.D Fin del condicional del paso 1.1.1.1.1.C
Llamar al algoritmo Reestructura_der con NODO^.IZQ y BO 1.1.1.1.2 Fin del condicional del paso 1.1.1.1.1
1.1.1.2 Fin del condicional del paso 1.1.1.1
Quitar (OTRO) Libera la memoria del nodo
1.1.2. Fin del condicional del paso 1.1.1
1.2. Fin del condicional del paso 1.1
si no
Escribir "La información no se encuentra en el árbol"
2. Fin del condicional del paso 1
entonces
1.1 Si (INFOR < NODO^.INFO)
entonces
Regresar a Elimina_balanceado con NODO^.IZQ, BO e INFOR
Llamar al algoritmo Reestructura_izq con NODO y BO
si no
1.1.1 Si (INFOR > NODOMNFO)
entonces
Regresar a Elimina_balanceado con NODO^.DER, BO e INFOR
Llamar al algoritmo Reestructura_der con NODO y BO
si no
Hacer OTRO <- NODO y BO <- VERDADERO
1.1.1.1 Si (OTRO^.DER = NULO)
entonces
Hacer NODO <- OTRO^.IZQ
si no
1.1.1.1.1 Si (OTRO^.IZQ = NULO)
entonces
Hacer NODO <-OTRO^.DER
Hacer AUX <- NODO^.IZQ y BOOL <- FALSO
1.1.1.1.1.A Mientras (AUX^.DER ≠ NULO) Repetir
Hacer AUX1 <- AUX,
AUX <- AUX^.DER y
BOOL <- VERDADERO
1.1.1.1.1.B {Fin del ciclo del paso 1.1.1.1.1.A }
Hacer NODO^.INFO <- AUX^.INFO y
OTRO <-AUX
1.1.1.1.1.C Si (BOOL = VERDADERO)
entonces
Hacer AUX1^.DER <- AUX^.IZQ
si no
Hacer NODO^.IZQ <- AUX^.IZQ
1.1.1.1.1.D Fin del condicional del paso 1.1.1.1.1.C
Llamar al algoritmo Reestructura_der con NODO^.IZQ y BO 1.1.1.1.2 Fin del condicional del paso 1.1.1.1.1
1.1.1.2 Fin del condicional del paso 1.1.1.1
Quitar (OTRO) Libera la memoria del nodo
1.1.2. Fin del condicional del paso 1.1.1
1.2. Fin del condicional del paso 1.1
si no
Escribir "La información no se encuentra en el árbol"
2. Fin del condicional del paso 1
El análisis matemático de los algoritmos de inserción Inserta balanceado y eliminación demuestra que es posible buscar, insertar y minar un elemento en un árbol balanceado de n nodos en O(log n)unidades de tiempo. Por otra parte, diversos análisis demuestran que son más frecuentes las rotaciones en las operaciones de inserción que en las de eliminación, ya que mientras se produce aproximadamente una rotación por cada dos inserciones, se produce una rotación por cada cinco eliminaciones.
No hay comentarios:
Publicar un comentario