¿Cuáles son las aplicaciones prácticas de los árboles de estructura de datos y los árboles binarios?

Hay 10 departamentos en una unidad y cada departamento tiene un teléfono, pero toda la unidad sólo tiene líneas exteriores. Cuando entra una llamada, la telefonista la transfiere al intercomunicador. Se sabe que la frecuencia de llamadas externas que utiliza cada departamento es (veces/día).

5 20 10 12 8 4 ?3 5 6 9

¿Cómo diseñar un número de teléfono interno para que el operador marque el menor número de veces posible?

Esta es una aplicación de los árboles de Huffman.

Una estructura de datos utilizada para almacenar y procesar datos similares a árboles, como árboles genealógicos.

La razón por la que se usa ampliamente es que, según la teoría de la estructura de datos, cualquier árbol complejo se puede convertir a binario y procesar.

La reordenación de árboles binarios, la búsqueda y la indexación de datos a gran escala tienen muchas aplicaciones.

La clasificación de árboles binarios es la más rápida entre las clasificaciones algorítmicas simples.

Una categoría importante de árboles es el árbol de búsqueda binaria autoequilibrado (BST autoequilibrado), que tiene muchas variantes: árbol RB en el que cada nodo es rojo o negro, y árbol AVL atávico coloreado en el que cada nodo el nodo es rojo o negro. Cada nodo contiene un factor de equilibrio, que es igual a alto izquierdo - alto derecho; el árbol Splay significa que cada nodo tiene un puntero con un nodo principal. Treap significa que cada nodo tiene un número de prioridad aleatorio, prioridad principal; > = nivel de prioridad infantil.

Los árboles de búsqueda binarios autoequilibrados aparecen con frecuencia en las entrevistas, pero los codificadores de Internet rara vez los utilizan en páginas web. Si se utilizan como mapas, normalmente es mejor utilizar tablas hash directamente. Si se usan para ordenar, es mejor usar el algoritmo de clasificación directamente... pero también hay ocasiones en las que es útil, como encontrar los límites superior e inferior de un número.

Otra categoría importante de árboles es Trie, que se caracteriza por un orden de diccionario garantizado, una alta tasa de compresión de espacio para almacenar diccionarios y búsqueda de prefijos. Los intentos se pueden utilizar para coincidencias generales, compresión de datos y creación de índices. Hay muchas variaciones: matriz doble: la implementación clásica de un trie.

Cada nodo puede almacenar una cadena en lugar de solo un carácter Matriz Judy, basada en un árbol de base de 256 elementos, que utiliza 20 métodos de compresión y es extremadamente complejo...burst Trie: si es un subárbol es lo suficientemente pequeño como para almacenarse en el montón binario.

Pero en general, el efecto de compresión de HAT Trie- tiene una alta tasa de compresión, es menos propenso a errores de caché de la CPU, tiene una velocidad de búsqueda cercana a la de una tabla hash y ocupa mucha menos memoria. . Los nodos pueden ser uno de los siguientes tres tipos: matriz Hash, depósito serializado, nodo Trie tradicional Marisa Trie: la tasa de compresión más alta, admite la carga de mmap, también es una implementación compleja, tiene muchas tecnologías de compresión, pero el tiempo de construcción es largo y no puede ser renovación dinámica.