Inserción de nodos al árbol.
Inserción en un árbol binario de búsqueda
La inserción en un árbol binario de búsqueda es una operación que se puede realizarse eficientemente en este tipo de estructura de datos. La estructura crece conforme se insertan elementos al árbol. Los pasos que se deben realizar para agregar un nuevo nodo a un árbol binario de búsqueda son los siguientes:
1. Comparar la clave a insertar con la raíz del árbol. Si es mayor, se sigue con el a subárbol derecho. Si es menor, se
continúa con el subárbol izquierdo.
2. Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las siguientes a condiciones:
2.1 El subárbol derecho, o el subárbol izquierdo, es igual a vacío, en cuyo caso se procederá a insertar el
elemento en el lugar que le corresponde.
continúa con el subárbol izquierdo.
2. Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las siguientes a condiciones:
2.1 El subárbol derecho, o el subárbol izquierdo, es igual a vacío, en cuyo caso se procederá a insertar el
elemento en el lugar que le corresponde.
Insercion ABB(APNODO, INFOR)
{El algoritmo realiza la inserción de un nodo en un árbol binario de búsqueda. APNODO es una variable de tipo puntero y la primera vez debe ser distinta de vacío. INFOR es un parámetro de tipo entero que contiene la información que se quiere insertar en un nuevo nodo}
{Se utiliza además, como auxiliar, la variable OTRO de tipo puntero}
{El algoritmo realiza la inserción de un nodo en un árbol binario de búsqueda. APNODO es una variable de tipo puntero y la primera vez debe ser distinta de vacío. INFOR es un parámetro de tipo entero que contiene la información que se quiere insertar en un nuevo nodo}
{Se utiliza además, como auxiliar, la variable OTRO de tipo puntero}
1. Si (INFOR < APNODO^.INFO)
entonces
1.1 Si (APNODO^.IZQ = NULO)
entonces
Crear(OTRO) {Se crea un nuevo nodo}
Hacer OTRO^.IZQ <- NULO
Hacer OTRO^.DER <- NULO
Hacer OTRO^.INFO <-INFO
Hacer APNODO^.IZQ <- OTRO
si no
Regresar a Insercion_ABB con APNODO^.IZQ e INFOR {Llamada recursiva}
1.2 {Fin del condicional del paso 1.1}
si no
1.3 Si (INFOR > APNODO^.INFO)
entonces
1.3.1 Si (APNODO^.DER = NULO)
entonces
Crear(OTRO) {Se crea un nuevo nodo}
Hacer OTRO^.IZQ <- NULO
Hacer OTRO^.DER <- NULO
Hacer OTRO^.INFO <- INFOR
Hacer NODO^.DER <- OTRO
si no
Regresar a Insercion_ABB con NODO^.DER e INFOR {Llamada recursiva}
1.3.2 {Fin del condicional del paso 1.3.1}
si no
Escribir “El nodo ya se encuentra en el árbol”
1.4 {Fin del condicional del paso 1.3}
2. {Fin del condicional del paso 1}
entonces
1.1 Si (APNODO^.IZQ = NULO)
entonces
Crear(OTRO) {Se crea un nuevo nodo}
Hacer OTRO^.IZQ <- NULO
Hacer OTRO^.DER <- NULO
Hacer OTRO^.INFO <-INFO
Hacer APNODO^.IZQ <- OTRO
si no
Regresar a Insercion_ABB con APNODO^.IZQ e INFOR {Llamada recursiva}
1.2 {Fin del condicional del paso 1.1}
si no
1.3 Si (INFOR > APNODO^.INFO)
entonces
1.3.1 Si (APNODO^.DER = NULO)
entonces
Crear(OTRO) {Se crea un nuevo nodo}
Hacer OTRO^.IZQ <- NULO
Hacer OTRO^.DER <- NULO
Hacer OTRO^.INFO <- INFOR
Hacer NODO^.DER <- OTRO
si no
Regresar a Insercion_ABB con NODO^.DER e INFOR {Llamada recursiva}
1.3.2 {Fin del condicional del paso 1.3.1}
si no
Escribir “El nodo ya se encuentra en el árbol”
1.4 {Fin del condicional del paso 1.3}
2. {Fin del condicional del paso 1}
Otra forma de expresar el algoritmo de inserción es la siguiente
Insercion_vl_ABB
El algoritmo realiza la inserción de un elemento en un árbol binario de búsqueda. APNODO es una variable de tipo ENLACE, la primera vez apunta a la raíz del árbol. INFOR es parámetro de tipo entero que contiene la información del elemento que se quiere insertar. El algoritmo considera el caso de un árbol vacío
1 Si (APNODO ≠ NULO)
entonces
1.1 Si (INFOR < APNODO^.INFO)
entonces
Regresar a Insercion_vl_ABB con APNODO^.IZQ e INFOR Llamada recursiva
si no
1.1.1 Si (INFOR > APNODO^.INFO)
entonces
Regresar a Insercion_vl_ABB con APNODO^.DER e INFOR Llamada recursiva
si no
Escribir "La información ya se encuentra en el árbol"
1.1.2 Fin del condicional del paso 1.1.1
1.2 Fin del condicional del paso 1.1
si no
Crear (OTRO) {Se crea un nuevo nodo}
Hacer OTRO^.IZQ <- NULO, OTRO^.DER <- NULO, OTRO^.INFO <- INFOR y APNODO <- OTRO
2. Fin del condicional del paso 1
entonces
1.1 Si (INFOR < APNODO^.INFO)
entonces
Regresar a Insercion_vl_ABB con APNODO^.IZQ e INFOR Llamada recursiva
si no
1.1.1 Si (INFOR > APNODO^.INFO)
entonces
Regresar a Insercion_vl_ABB con APNODO^.DER e INFOR Llamada recursiva
si no
Escribir "La información ya se encuentra en el árbol"
1.1.2 Fin del condicional del paso 1.1.1
1.2 Fin del condicional del paso 1.1
si no
Crear (OTRO) {Se crea un nuevo nodo}
Hacer OTRO^.IZQ <- NULO, OTRO^.DER <- NULO, OTRO^.INFO <- INFOR y APNODO <- OTRO
2. Fin del condicional del paso 1
Con la información alimentada se tiene un nuevo nodo y se generan las direcciones para el subárbol izq y der del nodo. Si es el primer nodo que se crea automáticamente pasara a ser la raíz del árbol, si no dependiendo del valor de la información se creara el hijo izq si el valor es menor que el de la raíz, o el hijo derecho si el valor es mayor que el de la raíz.
Pseudocódigo:
Procedimiento insertar ()
Entrada
Arbol: raíz, p, q
Entero: bandera
Tipo_elemento: dato
Inicio
Banderaß0
Pedir información: leer (dato)
Pßcrear_nodo
p.infoßdato
p.izqßnull
p.derßnull
Si (raíz=null) entonces
raízßp//inserta la raíz
si-no qßraíz//crea un nodo temporal para recorrer el árbol
Mientras (bandera !=1) hacer
Si (p.info
Si (q.izq=null)entonces
q.izqßp//inserta hijo izq
banderaß1
si-no
qßq.izq
fin-si
si-no
si (q.der=null)entonces
q.derßp//inserta hijo der.
Banderaß1
Si-no
qßq.der
Fin-si
Fin-si
Fin-mientras
Fin-si
Fin-procedimiento
Implementación en C sharp:
public void Insertar(int x)
{
int bandera = 0;
Arbol temp = new Arbol();
Arbol hoja = new Arbol();
hoja.info = x;
hoja.izq = null;
hoja.der = null;
if (raiz == null)
raiz = hoja;
else
{
temp = raiz;
while (bandera != 1)
{
if (hoja.info <>
{
if (temp.izq == null)
{
temp.izq = hoja;
bandera = 1;
}
else
temp = temp.izq;
}
else
{
if (temp.der == null)
{
temp.der = hoja;
bandera = 1;
}
else
temp = temp.der;
}
}
}
}
No hay comentarios:
Publicar un comentario