Árbol de prefijos comprimido

árbol base

Tipo de

madera

año de invención

1968

Autor

Donald R Morrison

	Lo peor
Búsqueda	$OK)$
Insertar	$OK)$
Eliminación	$OK)$

Archivos multimedia en Wikimedia Commons

Un árbol básico ( árbol radix , también árbol compacto de prefijos, árbol principal, árbol residual [1] ) es una estructura de datos que es una implementación optimizada para memoria de un árbol de prefijos. En el árbol base, el nodo que es el único hijo del nodo se fusiona con el nodo . $A$ $B$ $B$

La complejidad temporal de las operaciones de búsqueda, adición y eliminación de un elemento del árbol base se estima como , donde es la longitud del elemento que se procesa. El tiempo de ejecución no depende del número de elementos en el árbol. $OK)$ $k$

A diferencia de los árboles de prefijos convencionales, un nodo de árbol base se puede etiquetar con un solo elemento (carácter, bit, etc.) o una secuencia de elementos. Esto hace que el árbol base sea más eficiente para conjuntos pequeños de cadenas (especialmente si las cadenas en sí son lo suficientemente largas) y también para conjuntos que tienen una pequeña cantidad de prefijos largos.

Aplicación

El árbol base se utiliza, en particular, para el análisis de lenguajes naturales [2] .
El árbol base es una de las estructuras de datos del kernel de Linux [3] .

Notas

↑ Estructura Radix Tree para compresión de datos https://habrahabr.ru/post/141145/ Archivado el 20 de diciembre de 2016 en Wayback Machine .
↑ Pymorphy 2 https://m.habrahabr.ru/post/176575/ Archivado el 19 de junio de 2017 en Wayback Machine .
↑ Roberto Amor. Desarrollo del núcleo de Linux. tercera edicion. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 Archivado el 15 de diciembre de 2015 en Wayback Machine .

Enlaces

Material de referencia e investigación sobre algoritmos y estructuras de datos: PATRICIA , por Lloyd Allison, Monash University
Patricia Tree , Diccionario NIST de Algoritmos y Estructuras de Datos
Árboles de bits críticos , por Daniel J. Bernstein
Radix Tree API en el kernel de Linux , por Jonathan Corbet
Kart (árbol radix de alteración clave) , por Paul Jarc

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión