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 árboles m -ary
- 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]
- Un árbol m -ary perfecto es un árbol completo [1] m -ary en el que todos los nodos de las hojas están a la misma profundidad. [2]
Propiedades de los árboles m -ary
- Para un árbol de m con altura h , el límite superior para el número máximo de hojas es.
- 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 del árbol.
- El número total de nodos en un perfecto árbol de m -ary es, mientras que la altura h es
- Según la definición de Big-Ω, la profundidad máxima
- La altura de un árbol completo de m- arios con n nodos es.
- El número total de posibles árboles m -ary con n nodos es(que es un número catalán ). [3]
Métodos transversales para árboles marinos
Atravesar un árbol m -ary es muy similar a atravesar un árbol binario. El recorrido de la preorden va al padre, al subárbol izquierdo y al subárbol derecho, y para atravesar la orden posterior, pasa por el subárbol izquierdo, el subárbol derecho y el nodo principal. Para atravesar en orden, dado que hay más de dos hijos por nodo para m> 2 , se 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, la primera los nodos constituirían el subárbol izquierdo y los nodos constituirían el subárbol derecho.
Convertir un árbol m -ary en un árbol binario
El uso de una matriz para representar un árbol m es ineficaz, porque la mayoría de los nodos en las aplicaciones prácticas contienen menos de m elementos secundarios. 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, desde .
Primero, enlazamos 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 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 del árbol de m dado .
Métodos para almacenar árboles m -ary
Matrices
Los árboles m -ary también se pueden almacenar en orden de amplitud como una estructura de datos implícita en matrices , y si el árbol es un árbol m -ary completo, este método no desperdicia 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, mientras que su padre (si lo hay) se encuentra en el índice (asumiendo que la raíz tiene un índice cero, es decir, 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 de preorden. La complejidad espacial de este método es.
Basado en puntero
Cada nodo tendría una matriz interna para almacenar punteros a cada uno de sus niños:
En comparación con la implementación basada en matrices, este método de implementación tiene una complejidad de espacio superior de .
La enumeración de m- árboles ary
Enumerar todos los árboles m -ary posibles es útil en muchas disciplinas como una forma de verificar 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. Se puede construir una representación de secuencia de bits usando la búsqueda en profundidad de un árbol m -ary con n nodos que indican la presencia de un nodo en un índice dado usando valores binarios. Por ejemplo, la secuencia de bits x = 1110000100010001000 representa un árbol tripartito 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 entera que indica el número de ceros entre unos sucesivos, conocida como Secuencia de Cero Simple . es una secuencia cero simple correspondiente a la secuencia de bits donde j es el número de ceros necesarios al final de la secuencia para que la cadena tenga la longitud adecuada. Por ejemplo,es la representación de secuencia cero simple de la figura anterior. Una representación más compacta de 00433 es, que se llama secuencia cero , cuyas bases duplicadas no pueden ser adyacentes. Esta nueva representación permite construir una siguiente secuencia válida en. Una secuencia cero simple es válida si
La siguiente tabla muestra la lista de todas las secuencias cero simples válidas de todos los árboles de 3 arios con 4 nodos:
A partir de la parte inferior derecha de la tabla (es decir, "000"), hay una plantilla de red troncal que gobierna la generación de los posibles árboles ordenados desde "000" a "006". La plantilla de la columna vertebral para este grupo ("00X") se muestra a continuación, donde se agrega un nodo adicional en las posiciones etiquetadas "x".
Una vez que se han agotado todas las posiciones posibles en la plantilla de la columna vertebral, se construirá una nueva plantilla desplazando el tercer nodo una posición a la derecha como se muestra a continuación, y se produciría la misma enumeración hasta que se agoten todas las posiciones posibles etiquetadas con "X".
Volviendo a la tabla de enumeración de todos los árboles m -ary, donde y , podemos observar fácilmente que el salto aparente de "006" a "010" se puede explicar trivialmente de una manera algorítmica como se muestra a continuación:
El pseudocódigo para esta enumeración se da a continuación: [4]
Procedimiento SIGUIENTE () si por todo lo que entonces terminado demás si ientonces terminar si por finaliza si finaliza
Enumeración sin bucles
Un algoritmo de generación que toma El tiempo en el peor de los casos se denomina sin bucle porque la complejidad del tiempo no puede implicar un bucle o recursividad. Se dice que la enumeración sin bucle de m- ary trees es sin bucle si después de la inicialización, genera objetos de árbol sucesivos en. Para un árbol ma- ario dado T con siendo uno de sus nodos y su niño, una rotación izquierda-t en se hace haciendo el nodo raíz, y haciendo y todos sus subárboles un hijo de , adicionalmente asignamos el dejó a la mayoría de los niños de a y el hijo más adecuado de permanece unido a él mientras se promueve a root, como se muestra a continuación:
Convert an m-ary tree to left-tree
for : for : while t child of node at depth : L-t rotation at nodes at depth i end while end for end for
Una rotación derecha-t en d es la inversa de esta operación. La cadena izquierda de T es una secuencia de nodos tales que es la raíz y todos los nodos excepto tiene un hijo conectado a su izquierda más (es decir, ) 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 hasta que todos sus el subárbol se vuelve nulo en cada profundidad. Entonces, la secuencia del número de rotaciones t izquierda realizadas a la profundidad i denotada pordefine 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 tupla de 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).es el número de rotaciones de Lt necesarias en la profundidad i .
La captura de recuentos de rotaciones a la izquierda en cada profundidad es una forma de codificar un árbol m -ary. Por lo tanto, enumerar todas las codificaciones legales posibles nos ayudaría a generar todos los árboles m -ary para una m y una n dadas . Pero no todosLas secuencias de m enteros no negativos representan un árbol m-ario válido. Una secuencia denúmeros enteros no negativos es una representación válida de un árbol m- ary si y solo si [5]
La representación lexicográficamente más pequeña de palabra de código de un m-ario con n nodos es todo ceros y el más grande es n-1 unos seguidos por m-1 cero a su derecha.
Initialization
c[i] to zero for all i from 1 to p[i] set to for i from 1 to n Termination Condition Terminate when c[1] = n-1Procedure NEXT [5] if then end if if then else end ifend
Solicitud
Una de las aplicaciones de m -ary tree es la creación de un diccionario para la validación de cadenas aceptables. Para hacer eso, sea m igual al número de alfabetos válidos (por ejemplo, número de letras del alfabeto inglés ) con la raíz del árbol representando el punto de partida. De manera similar, cada uno de los hijos puede tener hasta m hijos que representen el siguiente carácter posible de 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 siguiente ejemplo, "at" y "y" son cadenas de claves 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 un diccionario de este tipo usando B-tree , Octree y / o trie .
Ver también
Referencias
- ^ a b "Árboles ordenados" . Consultado el 19 de noviembre de 2012 .
- ^ Black, Paul E. (20 de abril de 2011). "perfecto árbol de k-ario" . Instituto Nacional de Estándares y Tecnología de EE. UU . Consultado el 10 de octubre de 2011 .
- ^ Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). Matemáticas concretas: una base para la informática (segunda edición) . AIP.
- ^ a b Baronaigien, Dominique Roelants van (2000). "Generación libre de bucles de árboles K-ary". Revista de algoritmos . 35 (1): 100–107. doi : 10.1006 / jagm.1999.1073 .
- ^ a b Korsh, James F (1994). "Generación sin bucles de secuencias de árboles k-arios". Cartas de procesamiento de información . Elsevier. 52 (5): 243–247. doi : 10.1016 / 0020-0190 (94) 00149-9 .
- Storer, James A. (2001). Introducción a las estructuras de datos y los algoritmos . Birkhäuser Boston. ISBN 3-7643-4253-6.