Arboles binarios

UNIVERSIDAD POLITÉCNICA SALESIANA
CARRERA DE INGENIERÍA DE SISTEMAS
ESTRUCTURA DE DATOS

ÁRBOLES BINARIOS
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a “null”, es decir que no almacena ningúndato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
TIPOS DE ÁRBOLES BINARIOS
* Árbol binario lleno: Es un árbol en el que cada nodo tiene cero o dos hijos.
* Árbol binario perfecto: Es un árbol binario lleno enel que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).
* Árbol binario completo: Es un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
*Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o doshijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

ARBOL BINARIO DE BUSQUEDA
Un árbol binario de búsqueda (ABB) es un árbol binario definido de la siguiente forma:
* Todo árbol vacío es un árbol binario de búsqueda.
* Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
1. En caso de tenersubárbol izquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario de búsqueda.
2. En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario de búsqueda.
EJEMPLO:




Un árbol binario de búsqueda de tamaño9 y profundidad 3, con raíz 8 y hojas 1, 4, 7 y 13
Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.
Para estas definiciones se considera que hay una relación de orden establecidaentre los elementos de los nodos. Que cierta relación esté definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.
La altura h en el peor de los casos siempre el mismo tamaño que el número de elementos disponibles. Y en el mejor de los casos viene dada por la expresión h = ceil(log2(c +1)), donde ceil indica redondeo por exceso.
El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.
Dependiendo de las necesidades del usuario que trate con una estructura de este tipo se podrá permitir la igualdad estricta en alguno, enninguno o en ambos de los subárboles que penden de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja.
RECORRIDO DE NODOS
Se puede hacer un recorrido de un árbol en profundidad o en anchura.
Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno delos hijos.
El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inórden, preórden y postórden.
Una propiedad de los ABB es que al hacer un recorrido en profundidad inórden obtenemos los elementos ordenados de forma ascendente.

Recorridos:
Inórden = [6, 9, 13,...