Un árbol splay es una implementación eficiente de un árbol de búsqueda binaria equilibrado que aprovecha la localidad en las claves utilizadas en las solicitudes de búsqueda entrantes. Para muchas aplicaciones, existe una excelente localidad clave.
1. Un buen ejemplo es un enrutador de red. Un enrutador de red recibe paquetes de red a una velocidad alta de las conexiones entrantes y debe decidir rápidamente qué cable de salida enviar cada paquete, en función de la dirección IP en el paquete. El enrutador necesita una tabla grande (un mapa) que se pueda usar para buscar una dirección IP y averiguar qué conexión saliente usar. Si una dirección IP se ha usado una vez, es probable que se vuelva a usar, quizás muchas veces. Por lo tanto, podemos agrupar la tabla de búsqueda anterior utilizando el árbol splay. Si hemos buscado una dirección IP una vez que aparezca en la parte superior del árbol, la próxima vez que aparezca esa dirección IP, podemos encontrar su entrada en la parte superior y no tenemos que ir hasta el final.
2. Los árboles de despliegue se usan típicamente en la implementación de cachés, asignadores de memoria, recolectores de basura, compresión de datos, cuerdas (reemplazo de cadenas usadas para cadenas de texto largas), en Windows NT (en la memoria virtual, redes y código del sistema de archivos) etc.
- ¿Cuándo Quicksort tiene su peor complejidad de tiempo de caso?
- ¿BFS es más rápido y más eficiente que DFS?
- ¿Cómo funciona el algoritmo de Google Maps?
- ¿Cuáles son las estructuras de datos más utilizadas y más necesarias en el mundo de hoy?
- ¿Cuál es el mejor algoritmo de cifrado real utilizado en el almacenamiento de datos basado en hardware?
3. Un ejemplo de un dominio en el que se utilizan árboles de separación son los sistemas de detección de intrusiones (IDS), que son una parte esencial de la infraestructura de seguridad. Se utilizan para detectar, identificar y detener intrusos. Los administradores pueden confiar en ellos para descubrir ataques exitosos y evitar un uso futuro de exploits conocidos. Los IDS también se consideran una solución complementaria a la tecnología de firewall al reconocer los ataques contra la red que el firewall no detecta. Sin embargo, los IDS están plagados de alertas falsas positivas, lo que permite que los profesionales de seguridad se vean abrumados por las tareas de análisis. Por lo tanto, los IDS emplean varias técnicas para aumentar la probabilidad de detección de amenazas sospechosas y reducir el riesgo de falsos positivos. Esto lleva a la construcción de un árbol de decisión como el árbol de separación utilizado para verificar el tráfico. La estrategia propuesta para detectar intrusiones usando el análisis de protocolo consiste en extraer datos de cada paquete recibido y luego atravesar un árbol de decisión preconstruido.
4. El árbol Splay se usa en el compilador gcc y la biblioteca GNU C ++, el editor de cadenas sed, la implementación más popular de Unix malloc, los módulos del kernel cargables de Linux y en muchos otros programas.
ÁRBOL AVL: No pude encontrar ninguna aplicación del mundo real en la que se usa el árbol avl.
1. El árbol AVL es otra estructura que admite la búsqueda, inserción y eliminación de O (log n ). Está más rígidamente equilibrado que los árboles rojo-negros, lo que lleva a una inserción y extracción más lenta pero a una recuperación más rápida. Esto lo hace atractivo para las estructuras de datos que pueden construirse una vez y cargarse sin reconstrucción, como los diccionarios de idiomas (o los diccionarios de programas, como los códigos de operación de un ensamblador o intérprete).
2. El competidor de avl tree es Red-black tree. La altura del peor caso del árbol avl es ~ 1.44 log (n), del árbol negro rojo es 2 log (n). Pero como la inserción y eliminación en el árbol avl es costosa (más rotación que el árbol negro rojo) que el negro rojo, el árbol avl no se usa mucho.
