¿Diferencia entre intentos y árboles?

Question

Recuerdo de forma remota que los intentos no almacenan los datos completos por nodo, sino solo el sufijo al nodo padre.

Donde los árboles almacenan toda la información, pero solo se organizan basados ​​en el prefijo.

Así que los intentos se hacen más pequeños, lo que puede, por ejemplo, comprimir diccionarios muy buenos.

¿Entonces esa es realmente la única diferencia?

De las aplicaciones reales recuerdo que los intentos son más rápidos en las consultas de rango? Incluso existen campos trie solr/lucene especiales para acelerar las consultas de rango. Pero, ¿cómo es eso?

¿Cuál es la diferencia real y cuáles son las ventajas/desventajas de los intentos y los árboles?

Answer 1

Un árbol es una estructura general de nodos recursivos. Hay muchos tipos de árboles. Los más populares son binary tree y balanced tree. A Trie es un tipo de árbol, conocido por muchos nombres, incluido el árbol de prefijo, 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 usar para almacenar un conjunto de números o para indexar otros datos que se pueden representar mediante números (por ejemplo, objetos que se pueden dividir en hash). Su estructura está ordenada por lo que se puede buscar rápidamente para encontrar un solo elemento. Otras estructuras de árbol, como un árbol equilibrado, son similares en principio.

A trie representa una secuencia en su estructura. Es muy diferente ya que almacena secuencias de valores en lugar de valores individuales individuales. Cada nivel de recursividad dice 'cuál es el valor del ítem I de la lista de entrada'. Esto es diferente a un árbol binario que compara el único valor buscado con cada nodo.

Answer 2

Un árbol binario o una BSTse suele utilizar para almacenar valores numéricos. La complejidad de 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 se compone de varias ramas. Cada rama representa un posible carácter de claves. Necesitamos marcar el último nodo de cada tecla como nodo hoja. Se usará un valor de campo de nodo trie para distinguir el nodo como nodo de hoja (hay otros usos del campo de valor)

Para obtener más información acerca de los intentos, consulte este tutorial de topcoder. https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/