tree - guia - qgis manual
¿Diferencia entre tries y árboles? (3)
Recibí algunas ideas de esta charla , incluso a través del árbol de Radix utilizado en el núcleo de Linux es ligeramente diferente al de wikipedia.
Los árboles solo almacenan claves, no almacenan el valor asociado con las claves.
Recuerdo de forma remota que los intentos no almacenan todos los datos por nodo, solo el sufijo del nodo principal.
Donde los árboles almacenan toda la información, pero solo se organizan en base a un prefijo.
Así, los intentos se hacen más pequeños, lo que permite, por ejemplo, comprimir muy bien los diccionarios.
¿Es esa realmente la única diferencia?
De las aplicaciones reales, recuerdo que los intentos son más rápidos en las consultas de rango. Incluso hay campos especiales solr / lucene trie para acelerar las consultas de rango. ¿Pero cómo es eso?
¿Cuál es la diferencia real y cuáles son las ventajas y desventajas de los intentos y los árboles?
Un árbol es una estructura general de nodos recursivos. Hay muchos tipos de árboles. Los populares son el árbol binario y el árbol equilibrado . Un Trie es un tipo de árbol, conocido por muchos nombres, incluyendo el árbol de prefijos, el árbol de búsqueda digital y el árbol de recuperación (de ahí el nombre ''trie'').
Cada tipo de árbol tiene un propósito, estructura y comportamiento diferentes. Por ejemplo, un árbol binario almacena una colección de elementos comparables (por ejemplo, números). Por lo tanto, se puede utilizar para almacenar un conjunto de números o para indexar otros datos que se pueden representar con números (por ejemplo, objetos que se pueden hashear). Su estructura está ordenada por lo que se puede buscar rápidamente para encontrar un solo elemento. Otras estructuras de árboles, como un árbol equilibrado, son similares en principio.
Un Trie representa una secuencia en su estructura. Es muy diferente porque almacena secuencias de valores en lugar de valores individuales individuales. Cada nivel de recursión dice "cuál es el valor del elemento I de la lista de entrada". Esto es diferente a un árbol binario que compara el único valor buscado con cada nodo.
Un árbol binario o un bst se utiliza normalmente para almacenar valores numéricos. La complejidad del tiempo en un bst es O (log (n)) para inserción, eliminación y búsqueda. Cada nodo en un árbol binario tiene como máximo 2 nodos secundarios.
Trie : Cada nodo de trie consta de múltiples ramas. Cada rama representa un posible carácter de las claves. Necesitamos marcar el último nodo de cada clave como nodo hoja. Se utilizará un valor de campo de nodo trie para distinguir el nodo como nodo de hoja (hay otros usos del campo de valor)
Para aprender acerca de los intentos consulte este tutorial de codificador superior. https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/