Download Árbol binario

Árbol binario
Elaborado por
Ricardo Cárdenas cruz
Jeremías Martínez Guadarrama
Que es un árbol
Introducción
• Un Árbol Binario es un conjunto finito
de Elementos, de nombre Nodos de
forma que:
 El Árbol Binario es Vació si no tiene ningún elemento en
el.
 El Árbol Binario contiene un Nodo Raíz y los dos que
parten de él, llamados Nodo Izquierdo y Nodo Derecho.
 Los Árboles tiene 3 Recorridos Diferentes los cuales son:
 Pre-Orden
 In-Orden
 Post-Orden
 Pre-Orden
• Definición:
• El Recorrido “Pre-Orden” lo recorre de la siguiente
manera, viaje a través del Árbol Binario
desplegando el Contenido en la Raíz, después
viaje a través del Nodo Izquierdo y después a
través del Nodo Derecho.
• Detalle:
• Temp toma el Valor de la Raíz y compara si el
Árbol tiene algún Elemento, de otra manera
Desplegara “Árbol Vació…” y terminara el método.
Si el Árbol tiene elementos dentro de él, lo
recorrerá y viajara a través de los Arreglos Izq y
Der para determinar que valor meter en la Pila y
en Temp para de esta manera imprimir el
siguiente Elemento correspondiente.
• In-Orden
• El Recorrido “In-Orden” lo recorre de la siguiente
manera, viaje a través del Árbol Binario desplegando
el Contenido en el Nodo Izquierdo después la Raíz y
finalmente viaja a través del Nodo Derecho.
• Detalle:
• Temp toma el Valor de la Raíz y compara si el Árbol
tiene algún Elemento, de otra manera Desplegara
“Árbol Vació…” y terminara el método. Si el Árbol tiene
elementos dentro de él, lo recorrerá y viajara a través
de los Arreglos Izq y Der para determinar que valor
meter en la Pila y en Temp para de esta manera
imprimir el siguiente Elemento correspondiente.
• Operaciones básicas
• Una tarea muy común a realizar con un árbol es
ejecutar una determinada operación con cada uno de
los elementos del árbol. Esta operación se considera
entonces como un parámetro de una tarea más
general que es la visita de todos los nodos o, como se
denomina usualmente, del recorrido del árbol.
• Si se considera la tarea como un proceso secuencial,
entonces los nodos individuales se visitan en un orden
específico, y pueden considerarse como organizados
según una estructura lineal. De hecho, se simplifica
considerablemente la descripción de muchos
algoritmos si puede hablarse del proceso del siguiente
elemento en el árbol, según un cierto orden
subyacente.
Diagrama:
• Búsqueda
• Definición:
• La Búsqueda es Similar a todas los Métodos
anteriores de Búsqueda, simplemente efectúa
un recorrido comparando el Elemento que
deseas encontrar contra cada uno de los
Elementos en los Arreglos.
• Detalle:
• El Algoritmo de Búsqueda compara el
Elemento a buscar con cada uno de los datos
de nuestro Árbol, compara si el Elemento con
el Nodo Raíz, si no se encuentra en la Raíz…
compara Elemento contra la Raíz para
empezar a viajar por el Árbol
respectivamente, usa un método similar al
anterior hasta encontrar el Elemento. De otra
forma la búsqueda es fallida.
• Un árbol binario puede definirse como un
árbol que en cada nodo puede tener como
mucho grado 2,es decir, a lo más 2 hijos. Los
hijos suelen denominarse hijo a la izquierda e
hijo a la derecha, estableciéndose de esta
forma un orden en el posicionamiento de los
mismos.
• Todas las definiciones básicas que se dieron para
árboles generales permanecen inalteradas sin
más que hacer las particularizaciones
correspondientes.En los árboles binarios hay que
tener en cuenta el orden izqda-drcha de los
hijos.Por ejemplo:los árboles binarios a) y b) de la
figura 1(adoptamos el convenio de que los hijos a
la izquierda son extraídos extendiéndonos hacia
la izquierda y los hijos a la derecha a la derecha)
son diferentes,puesto que difieren en el nodo 5.El
árbol c por convenio se supone igual al b) y no al
a).
2. EL TIPO DE DATO ABSTRACTO
ARBOL BINARIO.
• Para construir el TDA Arbol Binario bastaría
con utilizar las primitivas de los árboles
generales pero dado la gran importancia y
peculiaridades que tienen este tipo de
árboles, construiremos una serie de
operaciones específicas. Consideraremos las
siguientes:
• CREAR(e,Ti,Td).Devuelve un árbol cuya raíz
contiene la etiqueta e asignando como hijo a
la izquierda Ti y como hijo a la derecha Td.
• DESTRUIR(T).Libera los recursos que
mantienen el árbol T de forma que para volver
a usarlo se debe asignar un nuevo valor con la
operación de creación.
3. Árbol binario de búsqueda.
.
• Los árboles binarios se utilizan
frecuentemente para representar conjuntos
de datos cuyos elementos se identifican por
una clave única. Si el árbol está organizado de
tal manera que la clave de cada nodo es
mayor que todas las claves su subarbol
izquierdo, y menor que todas las claves del
subarbol derecho se dice que este árbol es un
árbol binario de búsqueda.
Operaciones básicas
• Una tarea muy común a realizar con un árbol
es ejecutar una determinada operación con
cada uno de los elementos del árbol. Esta
operación se considera entonces como un
parámetro de una tarea más general que es la
visita de todos los nodos o, como se denomina
usualmente, del recorrido del árbol.
•
•
•
•
•
•
Clasificación de Arboles Binarios
Existen cuatro tipos de árbol binario:.
Arbol Binario Distinto.
Arbol Binario Similares.
Arbol Binario Equivalentes.
Arbol Binario Completos.
• Árbol Binario Distinto
• Se dice que dos árboles binarios son distintos cuando sus
estructuras son diferentes.
• Árbol Binario Similar
• Dos arboles binarios son similares cuando sus estructuras
son idénticas, pero la información que contienen sus nodos
es diferente.
• Árbol Binario Equivalente
• Son aquellos arboles que son similares y que además los
nodos contienen la misma información. Ejemplo:
• Árbol Binario Completo
• Son aquellos arboles en los que todos sus nodos excepto
los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y
el subárbol derecho.
• La idea tras los árboles-B es que los nodos
internos deben tener un número variable de
nodos hijo dentro de un rango predefinido.
Cuando se inserta o se elimina un dato de la
estructura, la cantidad de nodos hijo varía
dentro de un nodo. Para que siga
manteniéndose el número de nodos dentro
del rango predefinido, los nodos internos se
juntan o se parten.
• Un árbol-B se mantiene balanceado porque
requiere que todos los nodos hoja se
encuentren a la misma altura.
• Los árboles B tienen ventajas sustanciales
sobre otras implementaciones cuando el
tiempo de acceso a los nodos excede al
tiempo de acceso entre nodos. Este caso se da
usualmente cuando los nodos se encuentran
en dispositivos de almacenamiento
secundario como los discos rígidos.
• Cada nodo tiene como máximo M hijos.
• Cada nodo (excepto raíz y hojas) tiene como
mínimo M/2 hijos.
• La raíz tiene al menos 2 hijos si no es un nodo
hoja.
• Todos los nodos hoja aparecen al mismo nivel.
• Un nodo no hoja con k hijos contiene k-1
elementos almacenados.
• Los hijos que cuelgan de la raíz (r1, ···, rm) tienen
que cumplir ciertas condiciones:
– El primero tiene valor menor que r1.
– El segundo tiene valor mayor que r1 y menor que r2,
etc.
– El último hijo tiene valor mayor que rm.