TEORÍA DE TÉRMINOS DE GRAFOS

  (Redirigido desde el punto de articulación )

Saltar a navegaciónSaltar a búsqueda

Cada color corresponde a un componente biconconectado. Los vértices multicolores son vértices cortados y, por lo tanto, pertenecen a múltiples componentes biconéctados.

En la teoría de grafos , un componente biconnectado (a veces conocido como un componente conectado a 2 ) es un subgrafo biconnectado máximo . Cualquier gráfico conectado se descompone en un árbol de componentes biconnectados llamado árbol de corte de bloque del gráfico. Los bloques están unidos entre sí en vértices compartidos llamados vértices cortados o puntos de articulación . Específicamente, un vértice cortado es cualquier vértice cuya eliminación aumenta el número de componentes conectados .

Algoritmos [ editar ]

Profundidad de tiempo lineal primera búsqueda [ editar ]

El algoritmo secuencial clásico para calcular componentes biconéctados en un gráfico conectado no dirigido se debe a John Hopcroft y Robert Tarjan (1973). ^[1] Se ejecuta en tiempo lineal y se basa en la búsqueda de profundidad primero . Este algoritmo también se describe como el problema 22-2 de Introducción a los algoritmos (ambas ediciones, segunda y tercera).

La idea es ejecutar una búsqueda profunda mientras se mantiene la siguiente información:

1. la profundidad de cada vértice en el árbol de búsqueda de profundidad primero (una vez que se visita), y
2. para cada vértice v , la profundidad más baja de los vecinos de todos los descendientes de v (incluida la propia v ) en el árbol de búsqueda de profundidad primero, llamado punto bajo .

La profundidad es estándar para mantener durante una búsqueda de profundidad primero. El punto bajo de v puede calcularse después de visitar a todos los descendientes de v (es decir, justo antes de que v salga de la pila de búsqueda de profundidad primero ) como el mínimo de la profundidad de v , la profundidad de todos los vecinos de v (excepto el padre de v en el árbol de búsqueda de profundidad) y el punto bajo de todos los hijos de v en el árbol de búsqueda de profundidad.

El hecho clave es que un vértice no raíz v es un vértice cortado (o punto de articulación) que separa dos componentes biconnectados si y solo si hay un hijo y de v tal que el punto bajo ( y ) ≥ profundidad ( v ). Esta propiedad se puede probar una vez que la búsqueda de profundidad primero regresa de cada hijo de v (es decir, justo antes de que v salga de la pila de búsqueda de profundidad primero), y si es verdadero, v separa el gráfico en diferentes componentes biconéctados. Esto se puede representar calculando un componente conectado de cada y (un componente que contiene y contendrá el subárbol de y, más v ), y luego borrando el subárbol de y del árbol.

El vértice raíz debe manejarse por separado: es un vértice cortado si y solo si tiene al menos dos hijos. Por lo tanto, es suficiente construir simplemente un componente de cada subárbol hijo de la raíz (incluida la raíz).

Pseudocódigo [ editar ]

GetArticulationPoints (i, d)
    visitado [i] = verdadero
    profundidad [i] = d
    bajo [i] = d
    childCount = 0
    isArticulation = false
    para cada ni en adj [i]
        si no se visita [ni]
            padre [ni] = i
            GetArticulationPoints (ni, d + 1)
            childCount = childCount + 1
            si es bajo [ni]> = profundidad [i]
                isArticulation = true
            bajo [i] = Min (bajo [i], bajo [ni])
        más si ni! = padre [i]
            bajo [i] = Min (bajo [i], profundidad [ni])
    if (parent [i]! = null and isArticulation) o (parent [i] == null and childCount> 1)
        Salida i como punto de articulación

Tenga en cuenta que los términos hijo y padre denotan las relaciones en el árbol DFS, no el gráfico original.

Una demostración del algoritmo de Tarjan para encontrar vértices cortados. D denota profundidad y L denota punto bajo.

Otros algoritmos [ editar ]

Una alternativa simple al algoritmo anterior utiliza las descomposiciones de cadena , que son descomposiciones especiales del oído que dependen de los árboles DFS . ^{[2] Las} descomposiciones en cadena se pueden calcular en tiempo lineal mediante esta regla de desplazamiento . Deje C ser una descomposición de la cadena de G . Entonces G está conectado-2-vértice si y sólo si G tiene mínimo grado 2 y C ₁ es el único ciclo en C . Esto proporciona inmediatamente una prueba de conectividad de tiempo lineal 2 y se puede extender para enumerar todos los vértices de corte de Gen tiempo lineal usando la siguiente afirmación: Un vértice v en un gráfico conectado G (con grado mínimo 2) es un vértice cortado si y solo si v incide en un puente o v es el primer vértice de un ciclo en C - C ₁ . La lista de vértices cortados se puede usar para crear el árbol de corte en bloque de G en tiempo lineal.

En la versión en línea del problema, los vértices y los bordes se agregan (pero no se eliminan) dinámicamente, y una estructura de datos debe mantener los componentes conectados. Jeffery Westbrook y Robert Tarjan (1992) ^[3] desarrollaron una estructura de datos eficiente para este problema basada en estructuras de datos de conjuntos disjuntos . Específicamente, procesa n adiciones de vértices ym adiciones de aristas en O ( m  α ( m ,  n )) tiempo total, donde α es la función inversa de Ackermann . Este límite de tiempo ha demostrado ser óptimo.

Uzi Vishkin y Robert Tarjan (1985) ^[4] diseñaron un algoritmo paralelo en CRCW PRAM que se ejecuta en tiempo O (log  n ) con procesadores n  +  m . Guojing Cong y David A. Bader (2005) ^[5] desarrollaron un algoritmo que logra una aceleración de 5 con 12 procesadores en SMP . James A. Edwards y Uzi Vishkin (2012) informaron aceleraciones superiores a 30 basadas en el algoritmo original de Tarjan-Vishkin . ^[6]

Estructuras relacionadas [ editar ]

Relación de equivalencia [ editar ]

Se puede definir una relación binaria en los bordes de un gráfico arbitrario no dirigido, según el cual dos bordes e y f están relacionados si y solo si e  =  f o el gráfico contiene un ciclo simple a través de e y f . Cada borde está relacionado consigo mismo, y un borde e está relacionado con otro borde f si y solo si f está relacionado de la misma manera con e . Menos obvio, esta es una relación transitiva : si existe un ciclo simple que contiene los bordes e y f, y otro ciclo simple que contiene las aristas f y g , entonces uno puede combinar estos dos ciclos para encontrar un ciclo simple a través de e y g . Por lo tanto, esta es una relación de equivalencia , y se puede usar para dividir los bordes en clases de equivalencia, subconjuntos de bordes con la propiedad de que dos bordes están relacionados entre sí si y solo si pertenecen a la misma clase de equivalencia. Las subgrafías formadas por los bordes en cada clase de equivalencia son los componentes biconéctados del gráfico dado. Por lo tanto, los componentes biconéctados dividen los bordes del gráfico; sin embargo, pueden compartir vértices entre sí. ^[7]

Gráfico de bloque [ editar ]

El gráfico de bloques de un gráfico G dado es el gráfico de intersección de sus bloques. Por lo tanto, tiene un vértice para cada bloque de G y un borde entre dos vértices cuando los dos bloques correspondientes comparten un vértice. Un gráfico H es el gráfico de bloques de otro gráfico G exactamente cuando todos los bloques de H son subgráficos completos. Los gráficos H con esta propiedad se conocen como los gráficos de bloque . ^[8]

Árbol cortado en bloque [ editar ]

Un punto de corte , el vértice de corte , o punto de articulación de un gráfico G es un vértice que es compartida por dos o más bloques. La estructura de los bloques y puntos de corte de un gráfico conectado puede describirse mediante un árbol llamado árbol de corte de bloque o árbol BC . Este árbol tiene un vértice para cada bloque y para cada punto de articulación del gráfico dado. Hay un borde en el árbol de corte de bloque para cada par de un bloque y un punto de articulación que pertenece a ese bloque.

Un gráfico y su árbol cortado en bloque.
Los bloques son: b ₁ = [1,2], b ₂ = [2,3,4], b ₃ = [2,5,6,7], b ₄ = [7,8,9,10,11 ], b ₅ = [8,12,13,14,15], b ₆ = [10,16] yb ₇ = [10,17,18];
los puntos de corte son: c ₁ = 2, c ₂ = 7, c ₃ = 8 y c ₄ = 10.

  (Redirigido desde el árbol K-ary )

Saltar a navegaciónSaltar a búsqueda

Un ejemplo de un árbol m-ary con m = 5

En la teoría de grafos , un árbol m -ary (también conocido como árbol k -ary o k -way ) es un árbol enraizado en el que cada nodo no tiene más de m hijos. Un árbol binario es el caso especial donde  m = 2 , y un árbol ternario es otro caso con m = 3 que limita sus hijos a tres.

Tipos de m árboles ary [ editar ]

• Un completo m árbol ary es una m árbol ary donde dentro de cada nivel de cada nodo tiene 0 o m niños.
• Una completa m árbol ary es una m árbol ary que es máximamente eficiente del espacio. Debe estar completamente lleno en todos los niveles, excepto en el último nivel. Sin embargo, si el último nivel no está completo, todos los nodos del árbol deben estar "lo más a la izquierda posible". ^[1]
• Una perfecta m árbol ary es un completo ^[1] m árbol ary en el que todos los nodos hoja son a la misma profundidad. ^[2]

Propiedades de m árboles ary [ editar ]

• Para una m árbol ary con la altura h , el límite superior para el número máximo de hojas es$${\ displaystyle m ^ {h}}.
• La altura h de un árbol m -ary no incluye el nodo raíz, con un árbol que contiene solo un nodo raíz que tiene una altura de 0.
• La altura de un árbol es igual a la profundidad máxima D de cualquier nodo en el árbol.
• El número total de nodos. $${\ displaystyle N}en una perfecta m árbol ary es$${\ textstyle \ sum _ {i = 0} ^ {h} m ^ {i} = {\ frac {m ^ {h + 1} -1} {m-1}}}, mientras que la altura h es

{\ displaystyle {\ begin {alineado} & {\ frac {m ^ {h + 1} -1} {m-1}} \ geq N> {\ frac {m ^ {h} -1} {m-1 }} \\ [8pt] & m ^ {h + 1} \ geq (m-1) \ cdot N + 1> m ^ {h} \\ [8pt] & h + 1 \ geq \ log _ {m} \ left ((m-1) \ cdot N + 1 \ right)> h \\ [8pt] & h \ geq \ left \ lceil \ log _ {m} ((m-1) \ cdot N + 1) -1 \ right \ rceil. \ end {alineado}}}

Por la definición de Big-Ω, la profundidad máxima

$${\ displaystyle D = h \ geq \ left \ lceil \ log _ {m} ((m-1) \ cdot N + 1) -1 \ right \ rceil = O (\ log _ {m} n) = O ( \ log n / \ log m)}

• La altura de una completa m árbol ary con n nodos es$${\ textstyle \ lfloor \ log _ {m} ((m-1) \ cdot n) \ rfloor}.
• El número total de posibles m árbol ary con n nodos es$${\ textstyle C_ {n} = {\ frac {1} {(m-1) n + 1}} \ cdot {\ binom {m \ cdot n} {n}}} (que es un número catalán ) ^[3] .

Métodos de recorrido para árboles arábigos [ editar ]

Artículo principal: transversal del árbol

Recorrido de una m árbol ary es muy similar al recorrido de árbol binario. El recorrido de preorden va al padre, el subárbol izquierdo y el subárbol derecho, y para atravesar el orden posterior va por el subárbol izquierdo, el subárbol derecho y el nodo padre. Para recorrer en orden, dado que hay más de dos hijos por nodo para m> 2 , uno debe definir la noción de subárboles izquierdo y derecho . Un método común para establecer subárboles izquierdo / derecho es dividir la lista de nodos secundarios en dos grupos. Al definir un orden en los m hijos de un nodo, el primero $${\ textstyle \ {0,1, \ dots, \ lfloor {\ frac {m} {2}} \ rfloor \}} los nodos constituirían el subárbol izquierdo y $${\ textstyle \ {\ lceil {\ frac {m} {2}} \ rceil, \ dots, m \}} los nodos constituirían el subárbol correcto.

Convertir un m árbol ary al árbol binario [ editar ]

Un ejemplo de conversión de un árbol m-ary a un árbol binario. m = 6

El uso de una matriz para representar un m- árbol ary es ineficiente, porque la mayoría de los nodos en aplicaciones prácticas contienen menos de m niños. Como resultado, este hecho conduce a una matriz dispersa con un gran espacio no utilizado en la memoria. La conversión de una arbitraria m- árbol ary a un árbol binario sólo aumentaría la altura del árbol por un factor constante y no afectaría el tiempo total en el peor caso. En otras palabras,$${\ textstyle O (\ log _ {m} n) \ equiv O (\ log _ {2} n)} ya que $${\ textstyle \ log _ {2} n \ cdot \ log _ {m} n = {\ frac {\ log m} {\ log 2}} \ cdot {\ frac {\ log n} {\ log m}} = \ log _ {2} n}.

Primero, vinculamos todos los nodos hijos inmediatos de un nodo padre dado para formar una lista de enlaces. Luego, mantenemos el enlace del padre al primer hijo (es decir, el que está más a la izquierda) y eliminamos todos los demás enlaces al resto de los hijos. Repetimos este proceso para todos los hijos (si tienen hijos) hasta que hayamos procesado todos los nodos internos y rotamos el árbol 45 grados en el sentido de las agujas del reloj. El árbol obtenido es el árbol binario deseado obtenido a partir de lo dado m árbol ary.

Métodos para almacenar m árboles ary [ editar ]

Matrices [ editar ]

Un ejemplo de almacenamiento de un árbol m-ary con m = 3 en una matriz

m árboles ary también se pueden almacenar con el fin en amplitud como una estructura de datos implícito en las matrices , y si el árbol es una completa m árbol ary, este método no pierde el espacio. En esta disposición compacta, si un nodo tiene un índice i , su c -ésimo hijo en el rango {1, ..., m } se encuentra en el índice$${\ displaystyle m \ cdot i + c}, mientras que su padre (si lo hay) se encuentra en el índice $${\ displaystyle \ left \ lfloor {\ frac {i-1} {m}} \ right \ rfloor}(suponiendo que la raíz tiene índice cero, lo que significa una matriz basada en 0). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia , particularmente durante un recorrido previo al pedido. La complejidad espacial de este método es$${\ displaystyle O (m ^ {n})}.

Basado en puntero [ editar ]

Cada nodo tendría una matriz interna para almacenar punteros en cada uno de sus $${\ displaystyle m} childeren

Implementación basada en puntero del árbol m-ary donde m = 4.

En comparación con la implementación basada en matriz, este método de implementación tiene una complejidad espacial superior de $${\ displaystyle O (m \ cdot n)}.

La enumeración de m- árboles ary [ editar ]

Artículo principal: Combinatoria enumerativa

Listado de todos los posibles m árboles ary son útiles en muchas disciplinas, como una manera de comprobar hipótesis o teorías. Una representación adecuada de m- objetos de árbol ary puede simplificar en gran medida el proceso de generación. Uno puede construir una representación secuencia de bits utilizando la búsqueda en profundidad de un m árbol ary con n nodos indican la presencia de un nodo en un índice dado usando valores binarios. Por ejemplo, la secuencia de bits x = 1110000100010001000 representa un árbol de 3 arios con n = 6 nodos como se muestra a continuación.

El problema con esta representación es que enumerar todas las cadenas de bits en orden lexicográfico significaría que dos cadenas sucesivas podrían representar dos árboles que son lexicográficamente muy diferentes. Por lo tanto, la enumeración sobre cadenas binarias no daría lugar necesariamente a una generación ordenada de todos los m- árboles ary ^[4] . Una mejor representación se basa en una cadena de enteros que indica el número de ceros entre sucesivos, conocido como Secuencia de cero simple .$${\ textstyle S = s_ {1}, s_ {2}, \ dots, s_ {n-1}} es una secuencia cero simple que corresponde a la secuencia de bits $${\ textstyle 10 ^ {s_ {1}} 10 ^ {s_ {2}} \ ldots 10 ^ {s_ {n-1}} 10 ^ {j}}donde j es el número de ceros necesarios al final de la secuencia para hacer que la cadena tenga la longitud adecuada. Por ejemplo,$${\ displaystyle 1110000100010001000 \ equiv 10 ^ {0} 10 ^ {0} 10 ^ {4} 10 ^ {4} 10 ^ {3} \ equiv 00433}es la representación de secuencia cero simple de la figura anterior. Una representación más compacta de 00433 es$${\ displaystyle 0 ^ {2} 4 ^ {1} 3 ^ {2}}, que se llama secuencia cero , cuyas bases duplicadas no pueden ser adyacentes. Esta nueva representación permite construir una siguiente secuencia válida en$${\ displaystyle O (1)}. Una secuencia cero simple es válida si

$$$${\ displaystyle \ sum _ {i = 1} ^ {i = j} s_ {i} \ leq (m-1) j \ qquad \ qquad \ forall j \ leq n-1.}

, Es decir que el número de ceros en la secuencia de bits de un m árbol ary no puede exceder el número total de punteros nulos (es decir, punteros sin ningún nodo hijo unido a ellos). Este resumen está restringiendo$${\ displaystyle n-1} nodos para que haya espacio para agregar el $${\ displaystyle n ^ {t} h} sin crear una extracción no válida (es decir, tener un puntero nulo disponible para adjuntarle el último nodo).

La tabla a continuación muestra la lista de todas las secuencias cero simples válidas de todos los 3 árboles con 4 nodos:

Comenzando desde la parte inferior derecha de la tabla (es decir, "000"), hay una plantilla de red troncal que rige la generación de los posibles árboles ordenados a partir de "000" a "006". La plantilla de red troncal para este grupo ("00X") se muestra a continuación, donde se agrega un nodo adicional en las posiciones etiquetadas como "x".

Una vez que uno ha agotado todas las posiciones posibles en la plantilla de red troncal, se construirá una nueva plantilla desplazando el tercer nodo una posición a la derecha como se muestra a continuación, y la misma enumeración ocurriría hasta que se agoten todas las posiciones posibles etiquetadas con "X".

Volviendo a la tabla de enumeración de todos los m árboles ary, donde$${\ displaystyle m = 3} y $${\ displaystyle n = 4}, podemos observar fácilmente que el salto aparente de "006" a "010" puede explicarse trivialmente de manera algorítmica como se muestra a continuación:

El pseudocódigo para esta enumeración se proporciona a continuación ^[4] :

   Procedimiento SIGUIENTE ($${\ displaystyle s_ {1}, s_ {2}, \ dots, s_ {n-1}}
  
)
        si $${\ displaystyle s_ {i} = 0}
  
por todo lo que entonces
           terminado
       más
           {\ displaystyle i \ gets max \ {i | s_ {i}> 0 \}}
  

           $${\ displaystyle s_ {i} \ gets s_ {i} -1}
  

           si yo entonces
               $${\ displaystyle s_ {i} \ gets (i + 1) \ cdot (m-1) - \ sum s_ {j}}
  

           terminar si 
           para $${\ displaystyle j \ obtiene i + 2, i + 3, \ dots, n-1}
  

               $${\ displaystyle s_ {j} \ gets k-1}
  

       fin si 
   fin

Enumeración sin bucle [ editar ]

Un algoritmo de generación que toma $${\ displaystyle O (1)}el peor de los casos se llama loopless ya que la complejidad del tiempo no puede involucrar un loop o recursividad. Enumeración Loopless de m- árboles ary se dice que es loopless si después de la inicialización, se genera objetos de árbol en sucesivas$${\ displaystyle O (1)}. Para un determinado una m- árbol ary T con$${\ displaystyle a} siendo uno de sus nodos y $${\ displaystyle d} sus $${\ displaystyle t ^ {th}}niño, una rotación izquierda-t en$${\ displaystyle a} se hace haciendo $${\ displaystyle d} el nodo raíz, y haciendo $${\ displaystyle b} y todos sus subárboles son hijos de $${\ displaystyle a}, adicionalmente asignamos el $${\ displaystyle m-1} dejó la mayoría de los niños de $${\ displaystyle d} a $${\ displaystyle a} y el hijo más adecuado de $${\ displaystyle d} permanece unido a él mientras $${\ displaystyle d} se promociona a root, como se muestra a continuación:

   Convierta un árbol m-ary en árbol izquierdo 
       para$${\ displaystyle i = 1 \ puntos n}
  
:
           para $${\ displaystyle t = 2 ... m}
  
:
               mientras t hijo del nodo en profundidad $${\ displaystyle i \ neq 1}
  
:
                   Lt reotación en nodos a profundidad i
               terminar mientras
           fin de
       fin de

Una rotación derecha-t en d es la inversa de esta operación. La cadena izquierda de T es una secuencia de$${\ displaystyle x_ {1}, x_ {2}, \ dots, x_ {n}} nodos tales que $${\ displaystyle x_ {1}} es la raíz y todos los nodos excepto $${\ displaystyle x_ {n}} tener un niño conectado a su izquierda más (es decir, $${\ displaystyle m [1]}) puntero. Cualquier m- árbol ary puede ser transformado a una cadena izquierda árbol usando secuencia de finitos izquierda-t rotaciones para t de 2 a m . Específicamente, esto se puede hacer realizando rotaciones t-izquierda en cada nodo$${\ displaystyle x_ {i}} hasta que todo su $${\ displaystyle m-1}el subárbol se vuelve nulo en cada profundidad. Luego, la secuencia del número de rotaciones a la izquierda-t realizadas a profundidad i se denota por$${\ displaystyle c_ {i}}define una palabra de código de un m- árbol ary que pueden ser recuperados mediante la realización de la misma secuencia de derecha-t rotaciones.

Deja el $${\ displaystyle m-1} tupla de $${\ displaystyle c_ {1}, c_ {2}, \ dots, c_ {m-1}}representan el número de rotaciones L-2 , rotaciones L-3 , ..., rotaciones Lm que se han producido en la raíz (es decir, i = 1).$${\ displaystyle c _ {(i-1) (m-1) + t-1}}es el número de rotaciones de Lt requeridas a profundidad i .

La captura de cargos de rotaciones a la izquierda en cada profundidad es una forma de codificar un m árbol ary. Por lo tanto, la enumeración de todos los posibles codificación legal sería nos ayuda a generar todos los m árboles ary para un determinado m y n . Pero no todos$${\ displaystyle c_ {i}}Las secuencias de m enteros no negativos representan un árbol m-ario válido. Una secuencia de$${\ displaystyle (n-1) {\ dot {(}} m-1) +1}enteros no negativos es una representación válida de un m- árbol ary si y sólo si ^[5]

$$$${\ displaystyle \ sum _ {i = j} ^ {n} \ sum _ {t = 2} ^ {m} c _ {(i-1) (m-1) + t-1} \ qquad \ leq nj \ qquad, \ forall j \ en 0 \ puntos n.}

La representación de palabras de código lexicográficamente más pequeña de un m-ario con n nodos es todo ceros y el más grande es n-1 seguido de m-1 cero a su derecha.

   Inicialización 
       c [i] a cero para todo i de 1 a$${\ displaystyle n {\ dot {(}} k-1)}
  

       p [i] establecido en $${\ displaystyle n-1}
  
 para i de 1 a n
       $${\ displaystyle sum \ gets 0}
  

       $${\ displaystyle j \ gets m-1}
  

   Condición de terminación
       Terminar cuando c [1] = n-1
   Procedimiento SIGUIENTE [5]
       $${\ displaystyle sum \ obtiene sum + 1-c [j + 1]}
  

       $${\ displaystyle c [j] \ gets c [j] +1}
  

       Si {\ displaystyle p [q ​​[j]]> p [q ​​[j + 1]] + 1}
  
 luego
           $${\ displaystyle p [q ​​[j]] \ gets p [q ​​[j + 1]] + 1}
  

       terminara si
       $${\ displaystyle p [q ​​[j + c [j]]] \ gets p [q ​​[j]]}
  

       $${\ displaystyle c [j + 1] \ gets 0}
  

       Si $${\ displaystyle sum = p [q ​​[j]]}
  
 luego
           $${\ displaystyle j \ gets j-1}
  

       más
           $${\ displaystyle p [n] \ gets sum}
  

           $${\ displaystyle j \ gets m-1}
  

       fin si 
   fin

Solicitud [ editar ]

Una de las aplicaciones de m -ary tree es crear un diccionario para la validación de cadenas aceptables. Para hacer eso, que m sea ​​igual al número de alfabetos válidos (por ejemplo, número de letras del alfabeto inglés ) con la raíz del árbol que representa el punto de partida. Del mismo modo, cada uno de los niños puede tener hasta mhijos que representan el siguiente personaje posible en la cadena. Por lo tanto, los caracteres a lo largo de las rutas pueden representar claves válidas marcando el carácter final de las claves como "nodo terminal". Por ejemplo, en el ejemplo a continuación, "at" y "y" son cadenas de teclas válidas con "t" y "d" marcadas como nodos terminales. Los nodos terminales pueden almacenar información adicional para asociarla con una clave determinada. Hay formas similares de construir dicho diccionario usando B-tree , Octree y / o trie .