tipos recursivo recorrido operaciones lleno con busqueda binarios binario arboles arbol altura binary-tree

binary-tree - recursivo - recorrido de un arbol binario



Me pregunto cuáles son las aplicaciones particulares de los árboles binarios. ¿Podrías dar algunos ejemplos reales?

Cuando la mayoría de la gente habla de árboles binarios, la mayoría de las veces piensa en árboles de búsqueda binarios, así que eso lo cubriré primero.

Un árbol de búsqueda binario no equilibrado es realmente útil para poco más que educar a los estudiantes sobre las estructuras de datos.

Esto se debe a que, a menos que los datos ingresen en un orden relativamente aleatorio, el árbol puede degenerar fácilmente en su forma de caso más desfavorable, que es una lista enlazada, ya que los árboles binarios simples no están equilibrados.

Un buen ejemplo de ello: una vez tuve que arreglar un software que cargaba sus datos en un árbol binario para su manipulación y búsqueda. Se escribieron los datos en forma ordenada:

Alice Bob Chloe David Edwina Frank

de modo que, al leerlo de nuevo, terminó con el siguiente árbol:

Alice / / = Bob / / = Chloe / / = David / / = Edwina / / = Frank / / = =

Que es la forma degenerada. Si vas a buscar a Frank en ese árbol, tendrás que buscar en los seis nodos antes de encontrarlo.

Los árboles binarios se vuelven verdaderamente útiles cuando los equilibras. Esto implica rotar subárboles a través de su nodo raíz para que la diferencia de altura entre dos subárboles sea menor o igual a 1. Agregar esos nombres arriba de uno en uno en un árbol balanceado le daría la siguiente secuencia:

1. Alice / / = =

2. Alice / / = Bob / / = =

3. Bob _/ /_ Alice Chloe / / / / = = = =

4. Bob _/ /_ Alice Chloe / / / / = = = David / / = =

5. Bob ____/ /____ Alice David / / / / = = Chloe Edwina / / / / = = = =

6. Chloe ___/ /___ Bob Edwina / / / / Alice = David Frank / / / / / / = = = = = =

De hecho, puede ver subárboles enteros girando hacia la izquierda a medida que se agregan las entradas, lo que le proporciona un árbol binario equilibrado en el que la búsqueda en el peor de los casos es O (registro N) en lugar de O (N) como indica la forma degenerada. En ningún momento el NULL más alto ( = ) difiere del más bajo en más de un nivel. Y, en el árbol final de arriba, puedes encontrar a Frank solo mirando tres nodos ( Chloe , Edwina y, finalmente, Frank ).

Por supuesto, se vuelven aún más útiles cuando los haces árboles de múltiples vías equilibrados en lugar de árboles binarios. Eso significa que cada nodo contiene más de un elemento (técnicamente, contienen N elementos y N + 1 punteros, un árbol binario es un caso especial de un árbol de múltiples vías de 1 vía con 1 elemento y 2 punteros).

Con un árbol de tres vías, terminas con:

Alice Bob Chloe / | | / = = = David Edwina Frank / | | / = = = =

Esto se utiliza normalmente en el mantenimiento de claves para un índice de elementos. Escribí un software de base de datos optimizado para el hardware donde un nodo es exactamente del tamaño de un bloque de disco (por ejemplo, 512 bytes) y pones tantas claves como puedas en un solo nodo. Los indicadores en este caso eran en realidad números de registro en un archivo de acceso directo de registro de longitud fija independiente del archivo de índice (por lo que se puede encontrar el número de registro X buscando solo X * record_length ).

Por ejemplo, si los punteros son 4 bytes y el tamaño de la clave es 10, el número de claves en un nodo de 512 bytes es 36. Eso es 36 claves (360 bytes) y 37 punteros (148 bytes) para un total de 508 bytes con 4 bytes desperdiciados por nodo.

El uso de claves de múltiples vías introduce la complejidad de una búsqueda de dos fases (la búsqueda de múltiples vías para encontrar el nodo correcto combinado con una pequeña búsqueda secuencial para encontrar la clave correcta en el nodo) pero la ventaja de hacer menos I / O más que compensa esto.

No veo ninguna razón para hacer esto para una estructura en memoria, sería mejor que te quedaras con un árbol binario equilibrado y que mantengas tu código simple.

También tenga en cuenta que las ventajas de O (log N) sobre O (N) no aparecen realmente cuando sus conjuntos de datos son pequeños. Si está utilizando un árbol multidireccional para almacenar las quince personas en su libreta de direcciones, probablemente sea una exageración. Las ventajas vienen cuando almacena algo como cada pedido de sus cien mil clientes en los últimos diez años.

El punto principal de la notación big-O es indicar qué sucede cuando la N se acerca al infinito. Algunas personas pueden estar en desacuerdo, pero incluso está bien usar el ordenamiento de burbuja si está seguro de que los conjuntos de datos se mantendrán por debajo de cierto tamaño, siempre que no haya otra cosa disponible :-)

En cuanto a otros usos para árboles binarios, hay muchos, como:

  • Montones binarios donde las claves más altas están por encima o iguales a las más bajas en lugar de a la izquierda de (o por debajo o igual a y derecha);
  • Hash trees, similar a hash tables;
  • Árboles de sintaxis abstractos para la compilación de lenguajes informáticos;
  • Árboles Huffman para la compresión de datos;
  • Árboles de enrutamiento para el tráfico de red.

Dada la explicación que generé para los árboles de búsqueda, soy reticente a entrar en muchos detalles sobre los otros, pero eso debería ser suficiente para investigarlos, si así lo desea.

Discutir sobre el rendimiento de los árboles binarios no tiene sentido, no son una estructura de datos, sino una familia de estructuras de datos, todas con diferentes características de rendimiento. Si bien es cierto que los árboles binarios desbalanceados tienen un rendimiento mucho peor que los árboles binarios auto-equilibrados para la búsqueda, hay muchos árboles binarios (como los intentos binarios) para los cuales el "equilibrio" no tiene sentido.

Aplicaciones de arboles binarios.

  • Árbol de búsqueda binario : se utiliza en muchas aplicaciones de búsqueda donde los datos entran / salen constantemente, como el map y los objetos set en las bibliotecas de muchos idiomas.
  • Partición del espacio binario : se utiliza en casi todos los videojuegos en 3D para determinar qué objetos deben renderizarse.
  • Intentos binarios : se utilizan en casi todos los enrutadores de gran ancho de banda para almacenar tablas de enrutadores.
  • Hash Trees : se utiliza en programas p2p y firmas de imagen especializadas en las que se debe verificar un hash, pero el archivo completo no está disponible.
  • Heaps : se utilizan para implementar colas de prioridad eficientes, que a su vez se usan para programar procesos en muchos sistemas operativos, calidad de servicio en enrutadores y A * (algoritmo de búsqueda de ruta utilizado en aplicaciones de inteligencia artificial, incluida la robótica y los videojuegos) . También se utiliza en la ordenación del montón.
  • Árbol de codificación de Huffman ( Chip Uni ): se utiliza en algoritmos de compresión, como los utilizados por los formatos de archivo .jpeg y .mp3.
  • Árboles GGM : se utilizan en aplicaciones criptográficas para generar un árbol de números pseudoaleatorios.
  • Árbol de sintaxis : construido por compiladores y calculadoras (implícitamente) para analizar expresiones.
  • Treap : estructura de datos aleatorizada utilizada en redes inalámbricas y asignación de memoria.
  • T-tree : aunque la mayoría de las bases de datos usan algún tipo de árbol B para almacenar datos en la unidad, las bases de datos que guardan todos (la mayoría) de sus datos en la memoria a menudo usan árboles T para hacerlo.

La razón por la que los árboles binarios se utilizan con más frecuencia que los árboles n-arios para la búsqueda es que los árboles n-arios son más complejos, pero por lo general no proporcionan una ventaja de velocidad real.

En un árbol binario (balanceado) con m nodos, pasar de un nivel al siguiente requiere una comparación, y hay niveles log_2(m) , para un total de comparaciones log_2(m) .

En contraste, un árbol n-ario requerirá comparaciones de log_2(n) (usando una búsqueda binaria) para pasar al siguiente nivel. Como hay niveles totales de log_n(m) , la búsqueda requerirá log_2(n)*log_n(m) = log_2(m) total de comparaciones. Entonces, aunque los árboles n-arios son más complejos, no proporcionan ninguna ventaja en términos de comparaciones totales necesarias.

(Sin embargo, los árboles n-arios aún son útiles en situaciones de nicho. Los ejemplos que vienen a la mente de inmediato son los quad-trees y otros árboles de partición de espacio, donde la división del espacio usando solo dos nodos por nivel haría la lógica innecesariamente compleja; y B-trees utilizados en muchas bases de datos, donde el factor limitante no es la cantidad de comparaciones que se realizan en cada nivel, sino la cantidad de nodos que se pueden cargar desde el disco duro a la vez.

En C ++ STL, y muchas otras bibliotecas estándar en otros lenguajes, como Java y C #. Los árboles de búsqueda binarios se utilizan para implementar el conjunto y el mapa.

En el hardware moderno, un árbol binario es casi siempre subóptimo debido al mal comportamiento de la memoria caché y el espacio. Esto también se aplica a las variantes (semi) equilibradas. Si los encuentra, es donde el rendimiento no cuenta (o está dominado por la función de comparación), o más probablemente por razones históricas o de ignorancia.

Implementaciones de java.util.Set

La aplicación principal es árboles binarios de búsqueda . Estos son una estructura de datos en la que la búsqueda, inserción y eliminación son muy rápidas (sobre las operaciones de log(n) )

No creo que haya ningún uso para los árboles binarios "puros". (excepto con fines educativos) Los árboles binarios equilibrados, como los árboles rojo-negro o los árboles AVL son mucho más útiles, ya que garantizan las operaciones O (logn). Los árboles binarios normales pueden terminar siendo una lista (o casi una lista) y no son realmente útiles en aplicaciones que usan mucha información.

Los árboles equilibrados se utilizan a menudo para implementar mapas o conjuntos. También se pueden utilizar para clasificar en O (nlogn), aunque existen mejores formas de hacerlo.

También para buscar / insertar / eliminar tablas Hash se pueden usar, que generalmente tienen un mejor rendimiento que los árboles de búsqueda binarios (equilibrados o no).

Una aplicación en la que los árboles de búsqueda binarios (equilibrados) sería útil sería si se necesitara buscar / insertar / eliminar y ordenar. La clasificación podría estar en el lugar (casi, ignorando el espacio de pila necesario para la recursión), dado un árbol equilibrado listo para la construcción. Aún sería O (nlogn) pero con un factor constante más pequeño y no se necesita espacio adicional (excepto para la nueva matriz, suponiendo que los datos se deben colocar en una matriz). Por otro lado, las tablas hash no se pueden clasificar (al menos no directamente).

Tal vez también sean útiles en algunos algoritmos sofisticados para hacer algo, pero nada me viene a la mente. Si encuentro más editaré mi post.

Otros árboles como fe B+trees son ampliamente utilizados en bases de datos.

Se pueden utilizar como una forma rápida de ordenar los datos. Inserte datos en un árbol de búsqueda binario en O (log (n)). Luego atraviesa el árbol para ordenarlos.

Un árbol binario es una estructura de datos de árbol en la que cada nodo tiene a lo sumo dos nodos secundarios, que normalmente se distinguen como "izquierda" y "derecha". Los nodos con hijos son nodos principales y los nodos secundarios pueden contener referencias a sus padres. Fuera del árbol, a menudo hay una referencia al nodo "raíz" (el antecesor de todos los nodos), si existe. Se puede llegar a cualquier nodo en la estructura de datos comenzando en el nodo raíz y siguiendo repetidamente las referencias al elemento secundario izquierdo o derecho. En un árbol binario un grado de cada nodo es máximo dos.

Los árboles binarios son útiles, porque como puede ver en la imagen, si desea encontrar cualquier nodo en el árbol, solo debe mirar un máximo de 6 veces. Si quisiera buscar el nodo 24, por ejemplo, comenzaría desde la raíz.

  • La raíz tiene un valor de 31, que es mayor que 24, por lo que vas al nodo izquierdo.
  • El nodo izquierdo tiene un valor de 15, que es menor que 24, por lo que debe ir al nodo derecho.
  • El nodo derecho tiene un valor de 23, que es menor que 24, por lo que debe ir al nodo correcto.
  • El nodo derecho tiene un valor de 27, que es mayor que 24, por lo que debe ir al nodo izquierdo.
  • El nodo izquierdo tiene un valor de 25, que es mayor que 24, por lo que debe ir al nodo izquierdo.
  • El nodo tiene un valor de 24, que es la clave que estamos buscando.

Esta búsqueda se ilustra a continuación:

Puede ver que puede excluir la mitad de los nodos de todo el árbol en la primera pasada. y la mitad del subárbol izquierdo sobre el segundo. Esto hace para búsquedas muy efectivas. Si esto se hiciera con 4 mil millones de elementos, solo tendría que buscar un máximo de 32 veces. Por lo tanto, cuantos más elementos contenga el árbol, más eficiente será su búsqueda.

Las eliminaciones pueden volverse complejas. Si el nodo tiene 0 o 1 hijo, es simplemente cuestión de mover algunos punteros para excluir el que se va a eliminar. Sin embargo, no puede eliminar fácilmente un nodo con 2 hijos. Así que tomamos un atajo. Digamos que queríamos eliminar el nodo 19.

Ya que tratar de determinar dónde mover los punteros a la izquierda y a la derecha no es fácil, encontramos uno para sustituirlo. Vamos al subárbol de la izquierda y vamos tan a la derecha como podemos ir. Esto nos da el siguiente valor máximo del nodo que queremos eliminar.

Ahora copiamos todos los contenidos de 18, excepto los punteros izquierdo y derecho, y eliminamos el nodo 18 original.

Para crear estas imágenes, implementé un árbol AVL, un árbol de auto balanceo, de modo que en cualquier momento, el árbol tiene como máximo un nivel de diferencia entre los nodos de la hoja (nodos sin hijos). Esto evita que el árbol se desvíe y mantiene el tiempo máximo de búsqueda O(log n) , con el costo de un poco más de tiempo necesario para las inserciones y eliminaciones.

Aquí hay una muestra que muestra cómo mi árbol AVL se ha mantenido tan compacto y equilibrado como sea posible.

En una matriz ordenada, las búsquedas seguirían tomando O(log(n)) , como un árbol, pero la inserción y eliminación aleatorias tomaría O (n) en lugar de O(log(n)) del árbol. Algunos contenedores STL utilizan estas características de rendimiento para su ventaja, por lo que los tiempos de inserción y extracción requieren un máximo de O(log n) , que es muy rápido. Algunos de estos contenedores son map , multimap , set y multiset .

El código de ejemplo para un árbol AVL se puede encontrar en http://ideone.com/MheW8

Un compilador que usa un árbol binario para una representación de un AST, puede usar algoritmos conocidos para analizar el árbol como postorder, inorder. El programador no necesita crear su propio algoritmo. Debido a que un árbol binario para un archivo fuente es más alto que el árbol n-ario, su construcción lleva más tiempo. Toma esta producción: selstmnt: = "if" "(" expr ")" stmnt "ELSE" stmnt En un árbol binario tendrá 3 niveles de nodos, pero el árbol n-ario tendrá 1 nivel (de chids)

Es por eso que los sistemas operativos basados ​​en Unix son lentos.

Un ejemplo interesante de un árbol binario que no se ha mencionado es el de una expresión matemática evaluada recursivamente. Básicamente es inútil desde un punto de vista práctico, pero es una forma interesante de pensar en tales expresiones.

Básicamente, cada nodo del árbol tiene un valor que es inherente a sí mismo o se evalúa recursivamente mediante el funcionamiento de los valores de sus hijos.

Por ejemplo, la expresión (1+3)*2 se puede expresar como:

* / / + 2 / / 1 3

Para evaluar la expresión, pedimos el valor del padre. Este nodo, a su vez, obtiene sus valores de sus hijos, un operador más y un nodo que simplemente contiene ''2''. El operador positivo a su vez obtiene sus valores de los hijos con los valores ''1'' y ''3'' y los agrega, devolviendo 4 al nodo de multiplicación que devuelve 8.

Este uso de un árbol binario es similar a la notación de pulido inverso en un sentido, en el sentido de que el orden en que se realizan las operaciones es idéntico. Una cosa a tener en cuenta es que no necesariamente tiene que ser un árbol binario, sino que los operadores más utilizados son binarios. En su nivel más básico, el árbol binario aquí es de hecho solo un lenguaje de programación puramente funcional muy simple.

Una de las aplicaciones más comunes es almacenar eficientemente los datos en forma ordenada para acceder y buscar elementos almacenados rápidamente. Por ejemplo, std::map o std::set en C ++ Standard Library.

El árbol binario como estructura de datos es útil para varias implementaciones de analizadores de expresión y solucionadores de expresión.

También se puede utilizar para resolver algunos de los problemas de la base de datos, por ejemplo, la indexación.

En general, el árbol binario es un concepto general de la estructura de datos basada en un árbol particular y se pueden construir varios tipos específicos de árboles binarios con diferentes propiedades.

Una de las aplicaciones más importantes de los árboles binarios son los árboles de búsqueda binarios balanceados como:

Este tipo de árboles tiene la propiedad de que la diferencia en las alturas del subárbol izquierdo y derecho se mantiene pequeña al realizar operaciones como rotaciones cada vez que se inserta o elimina un nodo.

Debido a esto, la altura total del árbol permanece del orden de log n y las operaciones como la búsqueda, inserción y eliminación de los nodos se realizan en tiempo O (log n). El STL de C ++ también implementa estos árboles en forma de conjuntos y mapas.

la sintaxis de sus programas, o para el caso, muchas otras cosas, como los lenguajes naturales, se pueden analizar utilizando un árbol binario (aunque no necesariamente).