¿Los árboles binarios tienen un propósito específico en el almacenamiento de datos jerárquicos? ¿Cuál es su uso canónico?

12

Entiendo la estructura de los árboles binarios y cómo atravesarlos. Sin embargo, estoy luchando por darme cuenta de sus usos reales, propósitos en programas y programación. Cuando pienso en ejemplos de "vida real" de datos jerárquicos, casi con toda seguridad tienen más de 2 hijos. Por ejemplo, en un árbol genealógico, una madre a menudo puede tener más de dos hijos.

¿Son realmente útiles los 'árboles binarios' para almacenar datos relacionados linealmente debido a los tiempos de procesamiento más rápidos en las matrices y listas? Alternativamente, ¿tienen un propósito específico en el almacenamiento de datos jerárquicos? Si es así, ¿qué ejemplos hay de la aplicación de árboles binarios? ¿Qué datos son tales que un nodo tiene como máximo 2 hijos?

data-structures binary-tree sw123456
fuente
Creo que el uso principal de un árbol binario es ordenar datos. https://en.wikipedia.org/wiki/Binary_search_tree
Mandrill

Respuestas:

25

No, los árboles binarios no son para almacenar datos jerárquicos en el sentido en que está pensando. El caso de uso principal para los árboles n-arios, donde nes un número fijo, es la capacidad de búsqueda rápida , no una jerarquía semántica.

Recuerde el viejo juego en el que una persona piensa en un número entre 1 y 100, y la otra tiene que adivinarlo con la menor cantidad de conjeturas posible, y si adivina mal, la persona que piensa en el número tiene que decirle si usted también alto o muy bajo? Se vuelve aburrido después de un tiempo porque rápidamente descubres que siempre debes comenzar en 50, luego ir a 25 o 75, y seguir dividiendo el rango a buscar por la mitad con cada nueva suposición después de eso, y eventualmente puedes adivinar cualquier número en un máximo de 7 conjeturas, garantizado.

Puede que no sea un juego divertido, pero esa propiedad es lo que hace que los árboles binarios (y otros n-arios) sean útiles: puede usarlos para buscar un conjunto de datos muy grande en muy poco tiempo.

Mason Wheeler
fuente
Excelente respuesta muchas gracias. Entonces, ¿los árboles binarios son realmente otra estructura para almacenar datos como lo haría en una matriz o una lista, pero con el beneficio adicional de las capacidades de búsqueda rápida?
sw123456
1
@ sw123456: Eso es correcto. Al igual que con cualquier ingeniería, viene con compensaciones (usa más memoria, y más fragmentada) que una matriz con el mismo número de elementos, O (n) acceso al elemento #n del conjunto de datos en lugar de O (1) acceso, etc., pero la búsqueda rápida es definitivamente el principal beneficio de los árboles binarios.
Mason Wheeler
@ sw123456 Me alegra poder explicarlo :)
Mason Wheeler
3
El acceso a los elementos es O (log (n)) cuando el árbol está equilibrado. O (n) será el peor de los casos cuando se degenere (la mayoría de los nodos con un solo paréntesis).
Mandrill
@ sw123456 El enrutamiento de red utiliza una ligera modificación de un árbol binario llamado Trie (creado para una mayor eficiencia para el dominio del problema). En realidad, almacena información de jerarquía a medida que los enrutadores atraviesan el árbol bit por bit cuando buscan una dirección IP para encontrar a dónde debe reenviar el paquete. Las direcciones IP también son jerárquicas por naturaleza, por lo que al recorrer una IP para encontrar la coincidencia de prefijo más larga, el enrutador atraviesa la jerarquía de IP, las IP de subred, etc. No es obvio semánticamente, pero la relación está ahí. Los enrutadores usan esta estructura para la eficiencia de búsqueda, como respondió Mason.
Chris Cirefice
3

Cualquier estructura de árbol, donde un nodo puede tener un número ilimitado de hijos, se puede implementar utilizando un árbol binario.

Para cada nodo en su árbol, reemplácelo con un nodo con un puntero derecho e izquierdo. El puntero izquierdo va al primero de los hijos del nodo. El nodo derecho va al siguiente hermano del nodo. Todos los elementos secundarios de un nodo dado están en una lista vinculada unida por sus punteros derechos, con el encabezado de la lista señalado por el puntero izquierdo de su elemento primario.

Su complicado árbol n-ario se ha convertido en un árbol simple y binario.

Estoy seguro de que esto está en Knuth, vol. 1 en alguna parte.

Justsalt
fuente
Esta es una implementación realmente interesante. Estoy en lo cierto al pensar que debido a que cada nodo hijo era el comienzo de una lista vinculada, el árbol ya no sería O (log) n) si estaba equilibrado u O (n) si no, debido al hecho de que comenzaría la visita de cada nodo fuera de una búsqueda lineal? ¿Esta implementación resultaría en tiempos de búsqueda mucho más lentos? Pero por el lado positivo, los tiempos de búsqueda serían más rápidos que los de una estructura lineal estándar? ¿He entendido esto correctamente?
sw123456
@ sw123456, si el árbol original estuviera equilibrado, el árbol binario resultante seguramente no lo estaría. Creo que todo lo demás dependería del abanico del árbol, cuántos hijos tiene un nodo dado. Una búsqueda lineal solo ocurriría al descubrir a cuál de los hijos de un nodo dado seguir. Pero no estoy seguro de que pueda evitar eso en cualquier otra implementación de un árbol n-ary.
Justsalt
2

Árboles binarios, ¿por qué usarlos?

En programación trabajas mucho con colecciones de datos del mismo tipo.

Las dos formas básicas de almacenar estos datos son: listas y matrices vinculadas.

Ambos vienen con ventajas y desventajas: en una lista vinculada es fácil agregar elementos en cualquier posición o eliminar elementos. Pero el acceso a un elemento específico es más difícil, ya que debe revisar la lista hasta que esté en el elemento que desea.

  • No busca de manera eficiente, pero insertar y eliminar es fácil.

Con una matriz, el acceso a un elemento específico es fácil, pero es más difícil insertar o eliminar un elemento porque insertar significa: extender la matriz en uno, desplazar todos los elementos antes de la posición de inserción 1 a la derecha e insertar el elemento.

  • Busca de manera eficiente (si está ordenado) pero insertar y eliminar es difícil.

Entonces, tanto la lista vinculada como la matriz tienen desventajas.

Los árboles binarios están hechos para abordar los problemas de la matriz y la lista vinculada:

  1. Fácil de insertar y borrar
  2. Búsqueda fácil

Entonces, el árbol binario está hecho para cuando tienes muchos datos que cambian regularmente.

Pieter B
fuente