323 votos

¿Cuáles son las aplicaciones de los árboles binarios?

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

425voto

Aunque la recompensa se ha ido, ya que la respuesta aceptada da la extremadamente-falsa impresión de que los árboles binarios no son muy útiles, publicaré otra respuesta.

Discutir sobre la actuación de binary-trees 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 árboles binarios desequilibrados funcionan mucho peor que árboles binarios autoequilibrados para la búsqueda, hay muchos árboles binarios (como los intentos binarios) para el cual "balanceo" no tiene ningún significado.

Aplicaciones de los árboles binarios

  • Árbol de búsqueda binaria - Usado en muchos aplicaciones de búsqueda en las que los datos se introducen y salen constantemente, como la map y set objetos en las bibliotecas de muchos idiomas.

  • Partición del espacio binario - Se usa en casi todos los videojuegos 3D para determinar qué objetos necesitan ser renderizados.

  • Intentos binarios - Se utiliza en casi todos los enrutadores de banda ancha para almacenar tablas de enrutadores.

  • Árboles de hachís - utilizado en programas p2p y firmas de imágenes especializadas en las que hay que verificar un hash, pero el archivo completo no está disponible.

  • Montones - Se utiliza en la implementación de colas de prioridad eficientes, que a su vez se utilizan para procesos de programación en muchos sistemas operativos, calidad de servicio en los enrutadores, y A* (algoritmo de búsqueda de caminos usado en aplicaciones de IA, incluyendo robótica y videojuegos). También se usa en el "heap-sort".

  • Árbol de códigos Huffman (Chip Uni) - utilizado en los algoritmos de compresión, como los utilizados por los formatos de archivo .jpeg y .mp3.

  • Árboles GGM - Se utiliza en aplicaciones criptográficas para generar un árbol de números seudoaleatorios.

  • árbol de sintaxis - Construido por compiladores y (implícitamente) calculadoras para analizar las expresiones.

  • Treap - Estructura de datos aleatoria utilizada en redes inalámbricas y asignación de memoria.

  • Árbol T - Aunque la mayoría de las bases de datos utilizan alguna forma de árbol B para almacenar datos en la unidad, las bases de datos que guardan todos (la mayoría) sus datos en la memoria suelen utilizar árboles T para hacerlo.

    • *

La razón por la que los árboles binarios se utilizan más a menudo que los árboles n-ary para la búsqueda es que los árboles n-ary son más complejos, pero normalmente no proporcionan una ventaja real de velocidad.

En un árbol binario (equilibrado) con m nodos, pasar de un nivel a otro requiere una comparación, y hay log_2(m) para un total de log_2(m) comparaciones.

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

(Sin embargo, los árboles n-ary siguen siendo útiles en situaciones de nicho. Los ejemplos que vienen inmediatamente a la mente son quad-trees y otros árboles de división del espacio, donde la división del espacio usando sólo dos nodos por nivel haría la lógica innecesariamente compleja; y Árboles B utilizado en muchas bases de datos, donde el factor limitante no es cuántas comparaciones se hacen en cada nivel, sino cuántos nodos pueden ser cargados desde el disco duro a la vez)

291voto

paxdiablo Puntos 341644

Un árbol binario, en su forma cruda, es en realidad útil para poco más que educar a los estudiantes sobre las estructuras de datos :-) *a

Esto se debe a que, a menos que los datos lleguen en un orden relativamente aleatorio, el árbol puede degenerar fácilmente en su peor caso, que es una lista vinculada, ya que los árboles binarios simples son no ...equilibrado.

Un buen ejemplo: una vez tuve que arreglar un software que cargaba sus datos en un árbol binario para manipularlos y buscarlos. Escribió 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 buscas a Frank en ese árbol, tendrás que buscar en los seis nodos antes de encontrarlo.

Los árboles binarios se vuelven realmente útiles cuando los equilibras. Esto implica rotar los subárboles a través de su nodo de raíz para que la diferencia de altura entre dos subárboles cualesquiera sea menor o igual a 1. Añadiendo esos nombres por encima de uno a uno en un árbol equilibrado se obtendrí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, puedes ver subárboles enteros girando a la izquierda a medida que se añaden las entradas y esto te da un árbol binario equilibrado en el que la peor búsqueda es O(log N) en lugar de O(N) como da la forma degenerada. En ningún momento el NULL más alto (=) difieren de los más bajos en más de un nivel. Y, en el último árbol de arriba, puedes encontrar a Frank con sólo mirar tres nodos (Chloe, Edwina y, finalmente, Frank).

Por supuesto, se vuelven aún más útiles cuando los haces equilibrados multidireccional árboles en lugar de árboles binarios. Esto significa que cada nodo contiene más de un elemento (técnicamente, contienen N elementos y N+1 punteros, siendo un árbol binario un caso especial de un árbol multidireccional 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 típicamente para mantener las claves de un índice de artículos. He escrito un software de base de datos optimizado para el hardware en el que un nodo es exactamente del tamaño de un bloque de disco (digamos, 512 bytes) y pones tantas claves como puedas en un solo nodo. El punteros en este caso eran en realidad números de registro en un archivo de acceso directo de longitud fija separado del archivo de índice (así que el número de registro X podría ser encontrado con sólo buscar X * record_length).

Por ejemplo, si los punteros son de 4 bytes y el tamaño de la tecla es 10, el número de teclas 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 multidireccionales introduce la complejidad de una búsqueda en dos fases (búsqueda multidireccional 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 E/S de disco más que compensa esto.

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

También ten en cuenta que las ventajas de O(log N) sobre O(N) no aparecen realmente cuando tus conjuntos de datos son pequeños. Si estás usando un árbol de múltiples direcciones para almacenar las quince personas de tu libreta de direcciones, probablemente sea exagerado. Las ventajas vienen cuando estás almacenando algo como cada pedido de tus cien mil clientes en los últimos diez años.

El objetivo de la notación big-O es indicar lo que ocurre cuando el N se acerca al infinito. Algunas personas pueden estar en desacuerdo, pero incluso está bien usar el tipo de burbuja si estás seguro de que los conjuntos de datos se mantendrán por debajo de un cierto tamaño, siempre y cuando no haya nada más disponible :-)


*a En realidad, eso no es del todo cierto ya que también hay usos para los árboles no equilibrados. Pero eso... es divertido y, como la gran mayoría de los árboles binarios están equilibrados o son pequeños (donde el equilibrio no importa tanto), lo dejaré estar.

62voto

Drise Puntos 1871

Un árbol binario es una estructura de datos de árbol en la que cada nodo tiene como máximo dos nodos hijos, que suelen distinguirse como "izquierda" y "derecha". Los nodos con hijos son nodos padres, y los nodos hijos pueden contener referencias a sus padres. Fuera del árbol, suele haber una referencia al nodo "raíz" (el antepasado de todos los nodos), si existe. Se puede llegar a cualquier nodo de la estructura de datos empezando por el nodo raíz y siguiendo repetidamente las referencias al hijo izquierdo o derecho. En un árbol binario un grado de cada nodo es máximo dos.

Binary Tree

Los árboles binarios son útiles, porque como puedes ver en la imagen, si quieres encontrar cualquier nodo en el árbol, sólo tienes que mirar un máximo de 6 veces. Si quisieras buscar el nodo 24, por ejemplo, empezarías por 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, así que vas al nodo derecho.
  • El nodo derecho tiene un valor de 23, que es menor que 24, así que vas al nodo derecho.
  • El nodo derecho tiene un valor de 27, que es mayor que 24, así que vas al nodo izquierdo.
  • El nodo izquierdo tiene un valor de 25, que es mayor que 24, así que vas al nodo izquierdo.
  • El nodo tiene un valor de 24, que es la clave que buscamos.

Esta búsqueda se ilustra a continuación: Tree search

Se puede ver que se puede excluir la mitad de los nodos de todo el árbol en el primer paso y la mitad del subárbol izquierdo en el segundo. Esto hace que las búsquedas sean muy efectivas. Si esto se hizo en 4 mil millones elementos, sólo tendrías que buscar un máximo de 32 veces. Por lo tanto, cuantos más elementos contenga el árbol, más eficiente puede ser su búsqueda.

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

Delete 1

Como no es fácil determinar hacia dónde mover los punteros izquierdo y derecho, encontramos uno con el que sustituirlo. Vamos al subárbol izquierdo, y vamos tan a la derecha como podemos. Esto nos da el siguiente mayor valor del nodo que queremos eliminar.

Delete 3

Ahora copiamos todo el contenido de 18, excepto los punteros izquierdo y derecho, y borramos el nodo 18 original.

Delete 4


Para crear estas imágenes, implementé un árbol AVL, un árbol autobalanceable, 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 máximo O(log n) tiempo de búsqueda, con el costo de un poco más de tiempo requerido para inserciones y supresiones.

Aquí hay una muestra que muestra cómo mi árbol AVL se ha mantenido lo más compacto y equilibrado posible.

enter image description here

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

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

12voto

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

11voto

Chip Uni Puntos 4739

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X