Aplicaciones de Árbol Binario

Aplicaciones de Árbol Binario

Un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, supongamos que tenemos un arreglo en donde queremos encontrar todos los duplicados. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia.

 

También podemos observar la aplicación de árboles binarios en:

• Árbol de Búsqueda binario: se utiliza en muchas aplicaciones de búsqueda donde los datos es constantemente entrada/salida, tales como el map y set objetos en muchos idiomas y bibliotecas.
• Binary Space Partition: se utiliza en casi todos los juegos de vídeo 3D para determinar qué objetos deben ser prestados.
• Binario Trata: se usa en casi todos los routers de alto ancho de banda para almacenar tablas-routers.
• Hash Árboles: se usan en los programas p2p.
• Montones: utilizado en la aplicación eficiente de prioridad-colas, que a su vez se utilizan para los procesos de programación en muchos sistemas operativos. Asimismo, en rutas para encontrar el algoritmo utilizado en aplicaciones de la AI, como la robótica y los juegos de video. También se utiliza en heap-sort.
• La Codificación Huffman Árbol Chip Unit: se utiliza en los algoritmos de compresión, tales como los utilizados por el .jpeg y .mp3 (archivo-formatos).
• GGM Árboles: tiene aplicaciones criptográficas para generar un árbol de números pseudo-aleatorios.
• El Árbol sintáctico: construido por los compiladores y (implícitamente) calculadoras para analizar expresiones.
• Treap: estructura aleatoria de datos utilizadas en las redes inalámbricas y la asignación de memoria.

Algoritmo para eliminar un nodo en árbol binario:

1. Padre = NULL
2. Si el árbol está vacío: el elemento no está en el árbol, por lo tanto salimos sin eliminar ningún elemento.
3. Si el valor del nodo raíz es igual que el del elemento que buscamos, estamos ante uno de los siguientes casos:
   • El nodo raíz es un nodo hoja:
     • Si 'Padre' es NULL, el nodo raíz es el único del árbol, por lo tanto el puntero al árbol debe ser NULL.
     • Si raíz es la rama derecha de 'Padre', hacemos que esa rama apunte a NULL.
     • Si raíz es la rama izquierda de 'Padre', hacemos que esa rama apunte a NULL.
     • Eliminamos el nodo, y salimos.
   • El nodo no es un nodo hoja:
     • Buscamos el 'nodo' más a la izquierda del árbol derecho de raíz o el más a la derecha del árbol izquierdo. Hay que tener en cuenta que puede que sólo exista uno de esos árboles. Al mismo tiempo, actualizamos 'Padre' para que apunte al padre de 'nodo'.
     • Intercambiamos los elementos de los nodos raíz y 'nodo'.
     • Borramos el nodo 'nodo'. Esto significa volver a (3), ya que puede suceder que 'nodo' no sea un nodo hoja.
4. Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
5. Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

Algoritmo para insertar un nodo en árbol binario

• Se toma el dato a ingresar X.
• Partiendo de la raíz preguntamos: Nodo == null.
• En caso afirmativo X pasa a ocupar el lugar del nodo y ya hemos ingresado nuestro primer dato.
• En caso negativo preguntamos: X Nodo
• En caso de ser menor pasamos al Nodo de la IZQUIERDA del que acabamos de preguntar y repetimos desde el paso 2 partiendo del Nodo al que acabamos de visitar.
• En caso de ser mayor pasamos al Nodo de la DERECHA y tal cual hicimos con el caso anterior repetimos desde el paso 2 partiendo de este nuevo Nodo.

Algoritmo para Buscar un Nodo en Árbol Binario

• Si el árbol está vacío, terminamos la búsqueda: el elemento no está en el árbol.
• Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda con éxito.
• Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
• Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

Algoritmo para el Recorrido de árbol Binario

Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

• Visite la raíz
• Atraviese el sub-árbol izquierdo
• Atraviese el sub-árbol derecho

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

• Atraviese el sub-árbol izquierdo
• Visite la raíz
• Atraviese el sub-árbol derecho

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

• Atraviese el sub-árbol izquierdo
• Atraviese el sub-árbol derecho
• Visite la raíz

En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.

• En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
• En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho
• En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho.