¿Qué es más rápido: un “árbol de raíz” o un “árbol B”

Question

Para el procesamiento del lenguaje, como en las palabras del diccionario regulares, lo que sería más rápido en lectura , un árbol de raíz, o un árbol B regular? ¿Hay un método más rápido, como un diccionario con cubos y hash?

Answer 1

Como siempre, usted necesitará punto de referencia en el contexto de aplicación para estar seguro.

Sin embargo, espero que en este caso una tabla hash bien implementado probablemente resultará ser más rápido. Básicamente, esto requiere:

• Una exploración a través de la cadena para calcular el valor hash, por lo general mediante operaciones muy rápidas, tales como desplazamiento de bits / XORs
• Una tabla hash de búsqueda basado en el valor hash
• Una comparación de cadenas para confirmar que tienen la palabra correcta
• Un poco de procesamiento adicional en el caso de que hay una colisión de hash - sin embargo se puede ajustar el tamaño de su tabla hash para minimizar este

Un árbol de radix también será muy rápido, sólo hay un poco de sobrecarga adicional debido a la necesidad de atravesar varios niveles de nodos del árbol. Si el árbol es relativamente escasa, lo más probable es que las búsquedas de mayo sólo tendrán que bajar un pequeño número de niveles para encontrar una respuesta única. Una de las ventajas del árbol de raíz es que le dirá muy pronto si no tiene coincidencias posibles (por ejemplo, una rama de vacío para el árbol que comienzan con "q")

Un árbol binario será probablemente el más lento ya que en promedio tienen que buscar a través de un buen número de niveles de nodos del árbol. Sin embargo, todavía será lo suficientemente rápido para la mayoría de los propósitos.