Árbol binario aleatorio

En informática y teoría de la probabilidad , un árbol binario aleatorio es un árbol binario seleccionado al azar de alguna distribución de probabilidad sobre árboles binarios. Se han utilizado diferentes distribuciones, lo que ha dado lugar a diferentes propiedades para estos árboles.

Los árboles binarios aleatorios se han utilizado para analizar la complejidad promedio de estructuras de datos basadas en árboles de búsqueda binaria . Para esta aplicación, es común usar árboles aleatorios formados insertando nodos uno a uno según una permutación aleatoria . ^{[ 1 ]} Es muy probable que los árboles resultantes tengan una profundidad logarítmica y un número de Strahler logarítmico . El treap y los árboles de búsqueda binaria balanceados relacionados utilizan operaciones de actualización que mantienen esta estructura aleatoria incluso cuando la secuencia de actualización no es aleatoria.

Otras distribuciones en árboles binarios aleatorios incluyen la distribución discreta uniforme en la que todos los árboles distintos tienen la misma probabilidad, distribuciones en un número dado de nodos obtenidas por división repetida, árboles binarios y árboles radix para datos aleatorios, y árboles de tamaño variable generados por procesos de ramificación .

Para árboles aleatorios que no son necesariamente binarios, consulte árbol aleatorio .

Fondo

Un árbol binario es un árbol con raíz en el que cada nodo puede tener hasta dos hijos (los nodos que se encuentran directamente debajo de él en el árbol), y estos hijos se designan como izquierdos o derechos. A veces resulta conveniente considerar árboles binarios extendidos, en los que cada nodo es un nodo externo con cero hijos o un nodo interno con exactamente dos hijos. Un árbol binario que no está en forma extendida puede convertirse en un árbol binario extendido tratando todos sus nodos como internos y añadiendo un nodo externo por cada hijo que falte en un nodo interno. En sentido contrario, un árbol binario extendido con al menos un nodo interno puede convertirse de nuevo en un árbol binario no extendido eliminando todos sus nodos externos. De esta forma, estas dos formas son casi totalmente equivalentes a efectos de análisis matemático, salvo que la forma extendida permite un árbol que consta de un único nodo externo, lo cual no se corresponde con nada en la forma no extendida. A efectos de estructuras de datos informáticas, las dos formas difieren, ya que los nodos externos de la primera forma pueden representarse explícitamente como objetos en una estructura de datos. ^{[ 2 ]}

En un árbol de búsqueda binaria, los nodos internos se etiquetan con números u otros valores ordenados, llamados claves , dispuestos de manera que un recorrido en orden del árbol muestra las claves en orden ascendente. Los nodos externos permanecen sin etiquetar. ^{[ 3 ]} Los árboles binarios también pueden estudiarse con todos los nodos sin etiquetar, o con etiquetas que no se dan en orden ascendente. Por ejemplo, la estructura de datos de árbol cartesiano utiliza árboles binarios etiquetados que no son necesariamente árboles de búsqueda binaria. ^{[ 4 ]}

Un árbol binario aleatorio es un árbol aleatorio extraído de una determinada distribución de probabilidad sobre árboles binarios. En muchos casos, estas distribuciones de probabilidad se definen utilizando un conjunto dado de claves y describen las probabilidades de que los árboles de búsqueda binaria contengan dichas claves. Sin embargo, son posibles otras distribuciones, que no necesariamente generan árboles de búsqueda binaria ni dan como resultado un número fijo de nodos. ^{[ 5 ]}

A partir de permutaciones aleatorias

Árbol binario generado a partir de una permutación aleatoria de 100 elementos.

Para cualquier secuencia de claves ordenadas distintas, se puede formar un árbol de búsqueda binaria en el que cada clave se inserta secuencialmente como una hoja del árbol, sin modificar la estructura de las claves insertadas previamente. La posición de cada inserción se puede encontrar mediante una búsqueda binaria en el árbol anterior. El modelo de permutación aleatoria , para un conjunto dado de claves, se define eligiendo la secuencia aleatoriamente entre las permutaciones del conjunto, con igual probabilidad para cada permutación. ^{[ 6 ]}

Por ejemplo, si las tres claves 1, 3 y 2 se insertan en un árbol de búsqueda binaria en esa secuencia, el número 1 se ubicará en la raíz del árbol, el número 3 se colocará como su hijo derecho y el número 2 como el hijo izquierdo del número 3. Hay seis permutaciones diferentes de las claves 1, 2 y 3, pero solo se pueden construir cinco árboles a partir de ellas. Esto se debe a que las permutaciones 2, 1, 3 y 2, 3, 1 forman el mismo árbol. Por lo tanto, este árbol tiene probabilidad ${\tfrac {2}{6}}={\tfrac {1}{3}}$ de ser generados, mientras que los otros cuatro árboles tienen cada uno una probabilidad ${\tfrac {1}{6}}$ . ^{[ 5 ]}

Profundidad esperada de un nodo

Para cualquier clave $x$ en un conjunto dado de $n$ claves, el valor esperado de la longitud del camino desde la raíz hasta $x$ en un árbol de búsqueda binaria aleatorio es como máximo $2\log n+O(1)$ , dónde " $\log$ " denota la función logaritmo natural y el $O$ introduce la notación de la gran O. Por linealidad de la esperanza , el número esperado de ancestros de $x$ es igual a la suma, sobre otras claves $y$ , de la probabilidad de que $y$ es un antepasado de $x$ Una clave $y$ es un antepasado de $x$ exactamente cuando $y$ es la primera clave que se insertará desde el intervalo $[x,y]$ . Debido a que cada clave en el intervalo tiene la misma probabilidad de ser la primera, esto sucede con una probabilidad inversa a la longitud del intervalo. Por lo tanto, las claves que son adyacentes a $x$ en la secuencia ordenada de claves tienen probabilidad ${\tfrac {1}{2}}$ de ser un antepasado de $x$ , las llaves a un paso de distancia tienen probabilidad ${\tfrac {1}{3}}$ , etc. La suma de estas probabilidades forma dos copias de la serie armónica que se extiende desde $x$ en ambas direcciones en la secuencia ordenada, dando como resultado la $2\log n+O(1)$ límite anterior. Este límite también se cumple para la longitud esperada de la ruta de búsqueda para un valor. $x$ Esa es una de las claves dadas. ^{[ 7 ]}

El camino más largo

El camino más largo de raíz a hoja, en un árbol de búsqueda binaria aleatorio, es más largo que la longitud de camino esperada, pero solo por un factor constante. Su longitud, para un árbol con $n$ nodos, es con alta probabilidad aproximadamente

\displaystyle {\frac {1}{\beta }}\log n\approx 4.311\log n,

dónde $\beta$ es el número único en el rango $0<\beta <1$ satisfaciendo la ecuación

\displaystyle 2\beta e^{1-\beta }=1.

^{[ 8 ]}

Número esperado de hojas

En el modelo de permutación aleatoria, cada clave, excepto la más pequeña y la más grande, tiene probabilidad ${\tfrac {1}{3}}$ de ser una hoja en el árbol. Esto se debe a que es una hoja cuando se inserta después de sus dos vecinos, lo que ocurre en dos de las seis permutaciones de ella y sus dos vecinos, todas las cuales son igualmente probables. Por un razonamiento similar, la clave más pequeña y la más grande tienen probabilidad ${\tfrac {1}{2}}$ de ser una hoja. Por lo tanto, el número esperado de hojas es la suma de estas probabilidades, que para $n\geq 2$ es exactamente $(n+1)/3$ . ^{[ 9 ]}

Número de Strahler

El número de Strahler de los vértices de cualquier árbol es una medida de la complejidad de los subárboles que se encuentran bajo esos vértices. Una hoja (nodo externo) tiene un número de Strahler de uno. Para cualquier otro nodo, el número de Strahler se define recursivamente a partir de los números de Strahler de sus hijos. En un árbol binario, si dos hijos tienen números de Strahler diferentes, el número de Strahler de su padre es el mayor de los dos números de los hijos. Pero si dos hijos tienen números de Strahler iguales, su padre tiene un número que es uno mayor. El número de Strahler de todo el árbol es el número en el nodo raíz. $n$ árboles de búsqueda binaria aleatorios de -nodos, las simulaciones sugieren que el número de Strahler esperado es $\log _{3}n+O(1)$ Un límite superior más débil $\log _{3}n+o(\log n)$ Se ha demostrado. ^{[ 10 ]}

Treaps y árboles de búsqueda binaria aleatorios

En las aplicaciones de estructuras de datos de árboles de búsqueda binaria, es raro que las claves se inserten sin eliminación en un orden aleatorio, lo que limita las aplicaciones directas de los árboles binarios aleatorios. Sin embargo, los diseñadores de algoritmos han ideado estructuras de datos que permiten inserciones y eliminaciones arbitrarias para preservar la propiedad de que la forma del árbol sea aleatoria, como si las claves se hubieran insertado al azar. ^{[ 11 ]}

Si a un conjunto dado de claves se le asignan prioridades numéricas (independientes de sus valores), estas prioridades pueden usarse para construir un árbol cartesiano para los números, el árbol de búsqueda binaria que resultaría de insertar las claves en orden de prioridad. Al elegir prioridades como números reales aleatorios independientes en el intervalo unitario, y al mantener la estructura del árbol cartesiano mediante rotaciones de árbol después de cualquier inserción o eliminación de un nodo, es posible mantener una estructura de datos que se comporta como un árbol de búsqueda binaria aleatorio. Dicha estructura de datos se conoce como treap o árbol de búsqueda binaria aleatorio. ^{[ 11 ]}

Las variantes del treap, incluyendo el árbol zip y el árbol zip-zip, reemplazan las rotaciones del árbol por operaciones de "zipping" que dividen y fusionan árboles, y que limitan la cantidad de bits aleatorios que deben generarse y almacenarse junto con las claves. El resultado de estas optimizaciones sigue siendo un árbol con una estructura aleatoria, pero que no coincide exactamente con el modelo de permutación aleatoria. ^{[ 12 ]}

Árboles binarios aleatorios uniformes

El número de árboles binarios con $n$ nodos es un número catalán . ^{[ 13 ]} Para $n=1,2,3,\dots$ estas cantidades de árboles son

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... (secuencia A000108 en el OEIS ).

Así, si se selecciona uno de estos árboles uniformemente al azar, su probabilidad es el recíproco de un número de Catalan. Los árboles generados a partir de un modelo en esta distribución a veces se denominan árboles de Catalan binarios aleatorios . ^{[ 14 ]} Tienen una profundidad esperada proporcional a la raíz cuadrada de $n$ , en lugar de al logaritmo. ^{[ 15 ]} Más precisamente, la profundidad esperada de un nodo elegido al azar en un $n$ -árbol de nodos de este tipo es

{\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)

. ^{[ 16 ]}

El número de Strahler esperado de una muestra aleatoria uniforme $n$ -el árbol binario de nodos es $\log _{4}n+O(1)$ , inferior al número de Strahler esperado de árboles de búsqueda binaria aleatorios. ^{[ 17 ]}

Debido a su gran altura, este modelo de árboles aleatorios equiprobables no se utiliza generalmente para árboles de búsqueda binaria. Sin embargo, tiene otras aplicaciones, entre las que se incluyen:

Modelado de los árboles de análisis sintáctico de expresiones algebraicas en el diseño de compiladores . ^{[ 18 ]} Aquí, los nodos internos del árbol representan operaciones binarias en una expresión y los nodos externos representan las variables o constantes sobre las que operan las expresiones. El límite del número de Strahler se traduce en el número de registros necesarios para evaluar una expresión. ^{[ 19 ]}
Modelado de redes fluviales , la aplicación original para la cual se desarrolló el número de Strahler. ^{[ 20 ]}
Modelado de posibles árboles evolutivos para un número fijo de especies. En esta aplicación, se utiliza un árbol binario extendido, con las especies en sus nodos externos. ^{[ 21 ]}

Un algoritmo de Jean-Luc Rémy genera un árbol binario aleatorio uniforme de un tamaño específico en un tiempo lineal con respecto al tamaño, mediante el siguiente proceso: Se parte de un árbol compuesto por un único nodo externo. Luego, mientras el árbol actual no haya alcanzado el tamaño objetivo, se elige repetidamente uno de sus nodos (interno o externo) de forma aleatoria y uniforme. El nodo elegido se reemplaza por un nuevo nodo interno, teniendo el nodo elegido como uno de sus hijos (con igual probabilidad a la izquierda o a la derecha), y un nuevo nodo externo como su otro hijo. El proceso se detiene cuando se alcanza el tamaño objetivo. ^{[ 22 ]}

Procesos de ramificación

El proceso de Galton-Watson describe una familia de distribuciones en árboles en las que el número de hijos en cada nodo se elige aleatoriamente, independientemente de los demás nodos. Para árboles binarios, se utilizan dos versiones del proceso de Galton-Watson, que difieren únicamente en si se permite un árbol binario extendido con un solo nodo, un nodo raíz externo:

En la versión donde el nodo raíz puede ser externo, se elige que sea interno con una probabilidad especificada. $p$ o externo con probabilidad $1-p$ . Si es interno, sus dos hijos son árboles generados recursivamente por el mismo proceso.
En la versión donde el nodo raíz debe ser interno, sus hijos izquierdo y derecho se determinan como internos con probabilidad $p$ o externo con probabilidad $1-p$ , independientemente unas de otras. En el caso de que sean internas, son las raíces de árboles que se generan recursivamente mediante el mismo proceso.

Los árboles generados de esta manera se han denominado árboles binarios de Galton-Watson . En el caso especial donde $p={\tfrac {1}{2}}$ Se les llama árboles binarios críticos de Galton-Watson . ^{[ 23 ]}

Análisis

La probabilidad $p={\tfrac {1}{2}}$ marca una transición de fase para el proceso binario de Galton-Watson: para $p\leq {\tfrac {1}{2}}$ El árbol resultante es casi con certeza finito, mientras que para $p>{\tfrac {1}{2}}$ es infinito con probabilidad positiva. Más precisamente, para cualquier $p$ , la probabilidad de que el árbol permanezca finito es

\displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}

. ^{[ 24 ]}

Otra forma de generar los mismos árboles es realizar una secuencia de lanzamientos de moneda , con probabilidad $p$ de caras y probabilidad $1-p$ de cruces, hasta el primer lanzamiento en el que el número de cruces supere el número de caras (para el modelo en el que se permite una raíz externa) o supere uno más el número de caras (cuando la raíz debe ser interna), y luego utilice esta secuencia de lanzamientos de moneda para determinar las elecciones realizadas por el proceso de generación recursiva, en orden de primera profundidad. ^{[ 25 ]}

Debido a que el número de nodos internos es igual al número de caras en esta secuencia de lanzamiento de moneda, todos los árboles con un número dado $n$ de nodos se generan a partir de secuencias de lanzamiento de moneda (únicas) de la misma longitud, y son igualmente probables, independientemente de $p$ . Es decir, la elección de $p$ afecta la variación en el tamaño de los árboles generados por este proceso, pero para un tamaño dado los árboles se generan uniformemente al azar. ^{[ 26 ]} Para valores de $p$ por debajo de la probabilidad crítica $p={\tfrac {1}{2}}$ , valores más pequeños de $p$ producirá árboles con un tamaño esperado menor , mientras que valores mayores de $p$ producirá árboles con un tamaño esperado mayor. En la probabilidad crítica $p={\tfrac {1}{2}}$ No existe un límite finito en el tamaño esperado de los árboles generados por este proceso. Más precisamente, para cualquier $p$ , el número esperado de nodos a profundidad $i$ en el árbol está $(2p)^{i}$ y el tamaño esperado del árbol se puede obtener sumando el número esperado de nodos en cada profundidad. Para $p<{\tfrac {1}{2}}$ Esto da como resultado una serie geométrica.

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

,

para el tamaño esperado del árbol, pero para $p={\tfrac {1}{2}}$ Esto da como resultado 1 + 1 + 1 + 1 + ⋯ , una serie divergente . ^{[ 27 ]}

Para $p={\tfrac {1}{2}}$ , cualquier árbol en particular con $n$ Los nodos internos se generan con probabilidad $1/2^{2n+1}$ y la probabilidad de que un árbol aleatorio tenga este tamaño es esta probabilidad multiplicada por un número de Catalan,

{\frac {C_{n}}{2^{2n+1}}}={\frac {1}{2n+1}}{\binom {2n+1}{n}}{\frac {1}{2^{2n+1}}}\approx {\frac {1}{{\sqrt {4\pi }}\,n^{3/2}}}\displaystyle

. ^{[ 28 ]}

Aplicaciones

Los procesos de Galton-Watson se desarrollaron originalmente para estudiar la propagación y extinción de apellidos humanos , y se han aplicado ampliamente de manera más general a la dinámica de poblaciones humanas o animales. Estos procesos se han generalizado a modelos donde la probabilidad de ser un nodo interno o externo en un nivel dado del árbol (una generación , en la aplicación de dinámica de poblaciones ) no es fija, sino que depende del número de nodos en el nivel anterior. ^{[ 29 ]} Una versión de este proceso, con la probabilidad crítica ${\tfrac {1}{2}}$ Se ha estudiado como modelo de especiación , donde se conoce como el proceso de ramificación crítica . En este proceso, cada especie tiene una vida útil con distribución exponencial y, a lo largo de su vida , produce especies descendientes a una tasa igual a su vida útil. Cuando se produce un descendiente, el progenitor continúa como la rama izquierda del árbol evolutivo y el descendiente se convierte en la rama derecha. ^{[ 30 ]}

Otra aplicación de los árboles críticos de Galton-Watson (en la versión donde la raíz debe ser interna) surge en el algoritmo de Karger-Stein para encontrar cortes mínimos en grafos, utilizando un proceso recursivo de contracción de aristas . Este algoritmo se llama a sí mismo dos veces recursivamente, con cada llamada teniendo una probabilidad al menos ${\tfrac {1}{2}}$ de preservar el valor correcto de la solución. El árbol aleatorio modela el subárbol de llamadas recursivas correctas. El algoritmo tiene éxito en un grafo de $n$ vértices siempre que este árbol aleatorio de llamadas recursivas correctas tenga una rama de profundidad al menos $2\log _{2}n$ , alcanzando el caso base de su recursión. La probabilidad de éxito es $\Omega (1/\log n)$ , produciendo uno de los factores logarítmicos en el algoritmo. $O(n^{2}\log ^{3}n)$ tiempo de ejecución. ^{[ 31 ]}

Proceso de Yule

Devroye y Robson consideran un proceso aleatorio de tiempo continuo relacionado, en el que cada nodo externo es reemplazado eventualmente por un nodo interno con dos hijos externos, en un tiempo distribuido exponencialmente después de su primera aparición como nodo externo. El número de nodos externos en el árbol, en cualquier momento, se modela mediante un proceso de nacimiento simple o proceso de Yule, en el que los miembros de una población se reproducen a una tasa constante: en el proceso de Yule, nacer un hijo corresponde a ser reemplazado por dos hijos en el modelo de Devroye y Robson. Si este proceso se detiene en un tiempo fijo, el resultado es un árbol binario de tamaño aleatorio (que depende del tiempo de parada ), distribuido según el modelo de permutación aleatoria para ese tamaño. Devroye y Robson utilizan este modelo como parte de un algoritmo para generar rápidamente árboles en el modelo de permutación aleatoria, descritos por el número de nodos en cada profundidad en lugar de por su estructura exacta. ^{[ 32 ]} Una variante discreta de este proceso comienza con un árbol que consta de un único nodo externo y reemplaza repetidamente un nodo externo elegido al azar por un nodo interno con dos hijos externos. Nuevamente, si esto se detiene en un tiempo fijo (con un tamaño fijo), el árbol resultante se distribuye según el modelo de permutación aleatoria para ese tamaño. ^{[ 1 ]}

Intentar binario

Otra forma de árbol binario, el trie binario o árbol de búsqueda digital, tiene una colección de números binarios que etiquetan algunos de sus nodos externos. Los nodos internos del árbol representan prefijos de sus representaciones binarias que son compartidos por dos o más de los números. Los hijos izquierdo y derecho de un nodo interno se obtienen extendiendo el prefijo correspondiente con un bit más, un cero o un uno respectivamente. Si esta extensión no coincide con ninguno de los números dados, o coincide solo con uno de ellos, el resultado es un nodo externo; de lo contrario, es otro nodo interno. Se han estudiado tries binarios aleatorios, por ejemplo, para conjuntos de números reales aleatorios generados independientemente en el intervalo unitario . A pesar de que estos árboles pueden tener algunos nodos externos vacíos, tienden a estar mejor equilibrados que los árboles de búsqueda binaria aleatorios. Para $n$ números reales aleatorios uniformes en el intervalo unitario, o más generalmente para cualquier distribución de probabilidad de cuadrado integrable en el intervalo unitario, la profundidad promedio de un nodo es asintóticamente $\log _{2}n$ y la altura promedio de todo el árbol es asintóticamente $2\log _{2}n$ . El análisis de estos árboles se puede aplicar a la complejidad computacional de los algoritmos de ordenación basados en tries . ^{[ 33 ]}

Una variante del trie, el árbol radix o trie comprimido, elimina los nodos externos vacíos y sus nodos internos padres. Los nodos internos restantes corresponden a prefijos para los cuales ambas extensiones posibles, por un bit cero o uno, son utilizadas por al menos uno de los números elegidos aleatoriamente. Para un árbol radix para $n$ números binarios distribuidos uniformemente, el camino hoja-raíz más corto tiene longitud $\log _{2}n-\log _{2}\log n+o(\log \log n)$ y el camino hoja-raíz más largo tiene longitud $\log _{2}n+{\sqrt {2\log _{2}n}}+o({\sqrt {\log n}}),$ ambos con alta probabilidad . ^{[ 34 ]}

árboles de división aleatoria

Luc Devroye y Paul Kruszewski describen un proceso recursivo para construir árboles binarios aleatorios con $n$ nodos. Genera una variable aleatoria de valor real. $x$ en el intervalo unitario $(0,1)$ , asigna el primero $xn$ nodos (redondeados hacia abajo a un número entero de nodos) al subárbol izquierdo, el siguiente nodo a la raíz y los nodos restantes al subárbol derecho. Luego, continúa recursivamente utilizando el mismo proceso en los subárboles izquierdo y derecho. Si $x$ Si se elige uniformemente al azar en el intervalo, el resultado es el mismo que el árbol de búsqueda binaria aleatorio generado por una permutación aleatoria de los nodos, ya que cualquier nodo tiene la misma probabilidad de ser elegido como raíz. Sin embargo, esta formulación permite utilizar otras distribuciones en su lugar. Por ejemplo, en el modelo de árbol binario aleatorio uniforme, una vez que se fija una raíz, cada uno de sus dos subárboles también debe ser uniformemente aleatorio, por lo que el modelo aleatorio uniforme también puede generarse mediante una elección diferente de distribución (dependiendo de $n$ ) para $x$ Como muestran, al elegir una distribución beta en $x$ y mediante la elección adecuada de la forma para dibujar cada una de las ramas, los árboles matemáticos generados por este proceso pueden utilizarse para crear árboles botánicos de aspecto realista. ^{[ 35 ]}

Notas

1 2 Drmota (2009) , pág. 19.
↑ Knuth (1997) .
↑ Knuth (1973) .
↑ Vuillemin (1980) .
1 2 Sedgewick y Flajolet (2013) , pág. 286.
↑ Morin (2014) .
↑ Hibbard (1962) ; Knuth (1973) ; Mahmoud (1992) , pág. 75.
↑ Robson (1979) ; Pittel (1985) ; Devroye (1986) ; Mahmoud (1992) , págs. 91–99; Reed (2003) .
↑ Brown y Shubert (1984) .
↑ Kruszewski (1999) .
1 2 Martínez y Roura (1998) ; Seidel y Aragón (1996) ; Morín (2014) .
^ Tarjan, Levy y Timmel (2021) ; Gila, Goodrich y Tarjan (2023) .
↑ Drmota (2009) , pág. 26.
↑ Sedgewick y Flajolet (2013) , pág. 287.
↑ Knuth (2005) , pág. 15.
↑ Sedgewick y Flajolet (2013) , pág. 288.
↑ Devroye y Kruszewski (1995) .
↑ Mahmoud (1992) , pág. 63.
↑ Flajolet, Raoult y Vuillemin (1979) .
↑ Shreve (1966) .
↑ Aldous (1996) .
↑ Rémy (1985) ; Makinen y Siltaneva (2003) ; Knuth (2005) , págs. 16-17.
↑ Burd, Waymire y Winn (2000) .
↑ Este es un caso especial de un teorema general sobre criticidad y probabilidades de extinción en procesos de Galton-Watson, según el cual la probabilidad de extinción es la raíz positiva más pequeña de la fórmula $g(r)=r$ , dónde $g$ es la función generadora de probabilidad de la distribución sobre el número de hijos, aquí $g(x)=(1-p)+px^{2}$ Véase, por ejemplo, Jagers (2011) , Teorema 2.1, pág. 92. Jagers realiza el cálculo de esta raíz para el caso binario en la pág. 97.
↑ Para la conexión entre árboles y caminatas aleatorias (como las generadas por lanzamientos de monedas aleatorios) véase, por ejemplo, la Sección 6, "Caminatas y árboles", págs. 483-486, de Harris (1952) .
↑ Broutin, Devroye y Fraiman (2020) . De manera más general, todo proceso de Galton-Watson, condicionado a producir árboles de cierto tamaño, produce la misma distribución de probabilidad que un proceso crítico de Galton-Watson: véase la sección 2 de Kennedy (1975) .
↑ Para conocer el número esperado de nodos en cada nivel del árbol, véase, por ejemplo, Athreya y Ney (1972) , Sección IA2: Momentos, pág. 4.
↑ Por la equivalencia entre árboles y caminatas aleatorias, esto es lo mismo que la probabilidad de volver a cero por primera vez después $2n+2$ pasos en una caminata aleatoria simple , para lo cual véase, por ejemplo, Bertin (2021) , 2.5.1 Estadísticas de los tiempos de primer retorno al origen de una caminata aleatoria, págs. 70-72.
↑ Jagers (2011) .
↑ Popovic (2004) .
↑ Karger y Stein (1996) .
↑ Devroye y Robson (1995) .
↑ Devroye (1984) .
↑ Devroye (1992) .
↑ Devroye y Kruszewski (1996) .

Referencias

Aldous, David (1996), "Distribuciones de probabilidad en cladogramas", en Aldous, David; Pemantle, Robin (eds.), Estructuras discretas aleatorias , The IMA Volumes in Mathematics and its Applications, vol. 76, Springer-Verlag, pp. 1–18 , doi : 10.1007/978-1-4612-0719-1_1 , ISBN 978-1-4612-6881-9
Athreya, Krishna B.; Ney, Peter E. (1972), Procesos de ramificación , Berlín: Springer-Verlag, págs. 199-206 , doi : 10.1007/978-3-642-65371-1 , ISBN 978-3-642-65371-1
Bertin, Eric (2021), Física estadística de sistemas complejos: una introducción concisa , Springer Series in Synergetics (3.ª ed.), Springer International Publishing, Bibcode : 2021spcs.book.....B , doi : 10.1007/978-3-030-79949-6 , ISBN 9783030799496
Brown, Gerald G.; Shubert, Bruno O. (1984), "Sobre árboles binarios aleatorios" , Mathematics of Operations Research , 9 : 43–65 , doi : 10.1287/moor.9.1.43
Broutin, Nicolas; Devroye, Luc ; Fraiman, Nicolas (abril de 2020), "Funciones recursivas en árboles de Galton-Watson condicionales" (PDF) , Random Structures & Algorithms , 57 (2), Wiley: 304–316 , arXiv : 1805.09425 , doi : 10.1002/rsa.20921
Burd, Gregory A.; Waymire, Edward C.; Winn, Ronald D. (febrero de 2000), "Una invariancia autosimilar de árboles binarios críticos de Galton-Watson" , Bernoulli , 6 (1): 1–21 , doi : 10.2307/3318630 , JSTOR 3318630
Devroye, Luc (1984), "Análisis probabilístico de la altura de tries y de la complejidad de triesort" (PDF) , Acta Informatica , 21 (3): 229–237 , doi : 10.1007/BF00264248
Devroye, Luc (1986), "Una nota sobre la altura de los árboles de búsqueda binaria" (PDF) , Journal of the ACM , 33 (3): 489–498 , doi : 10.1145/5925.5930
Devroye, Luc (enero de 1992), "Una nota sobre el análisis probabilístico de árboles de Patricia" (PDF) , Random Structures & Algorithms , 3 (2): 203–214 , doi : 10.1002/rsa.3240030209
Devroye, Luc ; Kruszewski, Paul (1995), "Una nota sobre el número de Horton-Strahler para árboles aleatorios" (PDF) , Information Processing Letters , 56 (2): 95–99 , doi : 10.1016/0020-0190(95)00114-R
Devroye, Luc ; Kruszewski, Paul (1996), "La belleza botánica de los árboles binarios aleatorios" (PDF) , en Brandenburg, Franz J. (ed.), Graph Drawing: 3rd Int. Symp., GD'95, Passau, Alemania, 20-22 de septiembre de 1995 , Lecture Notes in Computer Science, vol. 1027, Springer-Verlag, pp. 166-177 , doi : 10.1007/BFb0021801 , ISBN 978-3-540-60723-6
Devroye, Luc ; Robson, John Michael (diciembre de 1995), "Sobre la generación de árboles de búsqueda binarios aleatorios" (PDF) , SIAM Journal on Computing , 24 (6): 1141–1156 , doi : 10.1137/s0097539792224954
Drmota, Michael (2009), Árboles aleatorios: una interacción entre combinatoria y probabilidad , Springer-Verlag, doi : 10.1007/978-3-211-75357-6 , ISBN 978-3-211-75355-2
Flajolet, P .; Raoult, JC; Vuillemin, J. (1979), "El número de registros necesarios para evaluar expresiones aritméticas" (PDF) , Theoretical Computer Science , 9 (1): 99–125 , doi : 10.1016/0304-3975(79)90009-4
Gila, Ofek; Goodrich, Michael T .; Tarjan, Robert E. (2023), "Árboles zip-zip: cómo hacer que los árboles zip sean más equilibrados, sesgados, compactos o persistentes", en Morin, Pat ; Suri, Subhash (eds.), Algoritmos y estructuras de datos – 18.º Simposio Internacional, WADS 2023, Montreal, QC, Canadá, 31 de julio – 2 de agosto de 2023, Actas , Lecture Notes in Computer Science, vol. 14079, Springer, pp. 474–492 , arXiv : 2307.07660 , doi : 10.1007/978-3-031-38906-1_31 , ISBN 978-3-031-38905-4
Harris, TE (1952), "Primer paso y distribuciones de recurrencia", Transactions of the American Mathematical Society , 73 (3): 471– 486, doi : 10.1090/s0002-9947-1952-0052057-2
Hibbard, Thomas N. (1962), "Algunas propiedades combinatorias de ciertos árboles con aplicaciones a la búsqueda y la clasificación", Journal of the ACM , 9 (1): 13– 28, doi : 10.1145/321105.321108
Jagers, Peter (2011), «Extinción, persistencia y evolución», en Chalub, Fabio ACC; Rodrigues, José Francisco (eds.), Las matemáticas del legado de Darwin , Matemáticas y biociencias en interacción, Basilea: Birkhäuser, pp. 91–104 , doi : 10.1007/978-3-0348-0122-5_5 , ISBN 9783034801225
Karger, David R.; Stein , Clifford (1996), "Un nuevo enfoque al problema del corte mínimo" (PDF) , Journal of the ACM , 43 (4): 601, doi : 10.1145/234533.234534
Kennedy, Douglas P. (1975), "El proceso de Galton-Watson condicionado a la progenie total", Journal of Applied Probability , 12 (4): 800–806 , doi : 10.2307/3212730 , JSTOR 3212730
Knuth, Donald E. ( 1973), "6.2.2 Búsqueda en árbol binario", El arte de la programación informática, vol. III: Ordenación y búsqueda , Addison-Wesley, págs. 422–451
Knuth, Donald E. (1997), "2.3.4.5 Longitud de ruta", El arte de la programación informática, vol. I: Algoritmos seminuméricos (3.ª ed.), Addison-Wesley, págs . 399–406
Knuth, Donald E. (2005), "Borrador de la Sección 7.2.1.6: Generación de todos los árboles" , The Art of Computer Programming , vol. IV, archivado del original el 2 de enero de 2023 , recuperado el 31 de marzo de 2009.
Kruszewski, Paul (1999), "Una nota sobre el número de Horton-Strahler para árboles de búsqueda binaria aleatorios", Information Processing Letters , 69 (1): 47–51 , doi : 10.1016/S0020-0190(98)00192-6
Mäkinen, Erkki; Siltaneva, Jarmo (2003), "Una nota sobre el algoritmo de Rémy para generar árboles binarios aleatorios", Missouri Journal of Mathematical Sciences , 15 (2): 103– 109, doi : 10.35834/2003/1502103
Mahmoud, Hosam M. (1992), Evolución de árboles de búsqueda aleatorios , John Wiley & Sons
Martínez, Conrado; Roura, Salvador (1998), "Árboles de búsqueda binaria aleatorios", Journal of the ACM , 45 (2): 288–323 , CiteSeerX 10.1.1.17.243 , doi : 10.1145/274787.274812
Morin, Pat (22 de marzo de 2014), "Capítulo 7: Árboles de búsqueda binaria aleatorios", Estructuras de datos abiertas (en pseudocódigo) (PDF) ( ed. 0,1 GB), págs . 145–164
Pittel, B. (1985), "Crecimiento asintótico de una clase de árboles aleatorios", Annals of Probability , 13 (2): 414–427 , doi : 10.1214/aop/1176993000
Popovic, Lea (noviembre de 2004), "Genealogía asintótica de un proceso de ramificación crítico", Annals of Applied Probability , 14 (4), arXiv : math/0503577 , doi : 10.1214/105051604000000486
Reed, Bruce (2003), "La altura de un árbol de búsqueda binaria aleatorio", Journal of the ACM , 50 (3): 306– 332, doi : 10.1145/765568.765571
Rémy, Jean-Luc (1985), "Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire" , RAIRO Informatique théorique (en francés), 19 (2): 179– 195, doi : 10.1051/ita/1985190201791
Robson, JM (1979), "La altura de los árboles de búsqueda binaria", Australian Computer Journal , 11 : 151–153
Seidel, Raimund ; Aragon, Cecilia R. (1996), "Árboles de búsqueda aleatorios", Algorithmica , 16 ( 4–5 ): 464–497 , doi : 10.1007/s004539900061 (inactivo el 12 de julio de 2025){{citation}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
Sedgewick, Robert ; Flajolet, Philippe (2013), «Capítulo 6: Árboles», Introducción al análisis de algoritmos (2.ª ed.), Addison-Wesley, ISBN 9780133373486
Shreve, Ronald L. (enero de 1966), "Ley estadística del número de arroyos", The Journal of Geology , 74 (1): 17–37 , Bibcode : 1966JG.....74...17S , doi : 10.1086/627137 , JSTOR 30075174
Tarjan, Robert E.; Levy, Caleb C.; Timmel, Stephen (2021), "Árboles Zip", ACM Transactions on Algorithms , 17 (4): 34:1–34:12, arXiv : 1806.06726 , doi : 10.1145/3476830
Vuillemin, Jean (1980), "Una mirada unificadora a las estructuras de datos", Communications of the ACM , 23 (4): 229– 239, doi : 10.1145/358841.358852

[FOOTNOTEDrmota200919-1] 1 2 Drmota (2009) , pág. 19.

[FOOTNOTEKnuth1997-2] Knuth (1997) .

[FOOTNOTEKnuth1973-3] Knuth (1973) .

[FOOTNOTEVuillemin1980-4] Vuillemin (1980) .

[FOOTNOTESedgewickFlajolet2013286-5] 1 2 Sedgewick y Flajolet (2013) , pág. 286.

[FOOTNOTEMorin2014-6] Morin (2014) .

[7] Hibbard (1962) ; Knuth (1973) ; Mahmoud (1992) , pág. 75.

[8] Robson (1979) ; Pittel (1985) ; Devroye (1986) ; Mahmoud (1992) , págs. 91–99; Reed (2003) .

[FOOTNOTEBrownShubert1984-9] Brown y Shubert (1984) .

[FOOTNOTEKruszewski1999-10] Kruszewski (1999) .

[treap-11] 1 2 Martínez y Roura (1998) ; Seidel y Aragón (1996) ; Morín (2014) .

[12] Tarjan, Levy y Timmel (2021) ; Gila, Goodrich y Tarjan (2023) .

[FOOTNOTEDrmota200926-13] Drmota (2009) , pág. 26.

[FOOTNOTESedgewickFlajolet2013287-14] Sedgewick y Flajolet (2013) , pág. 287.

[FOOTNOTEKnuth200515-15] Knuth (2005) , pág. 15.

[FOOTNOTESedgewickFlajolet2013288-16] Sedgewick y Flajolet (2013) , pág. 288.

[FOOTNOTEDevroyeKruszewski1995-17] Devroye y Kruszewski (1995) .

[FOOTNOTEMahmoud199263-18] Mahmoud (1992) , pág. 63.

[FOOTNOTEFlajoletRaoultVuillemin1979-19] Flajolet, Raoult y Vuillemin (1979) .

[FOOTNOTEShreve1966-20] Shreve (1966) .

[FOOTNOTEAldous1996-21] Aldous (1996) .

[22] Rémy (1985) ; Makinen y Siltaneva (2003) ; Knuth (2005) , págs. 16-17.

[FOOTNOTEBurdWaymireWinn2000-23] Burd, Waymire y Winn (2000) .

[extinction-24] Este es un caso especial de un teorema general sobre criticidad y probabilidades de extinción en procesos de Galton-Watson, según el cual la probabilidad de extinción es la raíz positiva más pequeña de la fórmula $g(r)=r$ , dónde $g$ es la función generadora de probabilidad de la distribución sobre el número de hijos, aquí $g(x)=(1-p)+px^{2}$ Véase, por ejemplo, Jagers (2011) , Teorema 2.1, pág. 92. Jagers realiza el cálculo de esta raíz para el caso binario en la pág. 97.

[25] Para la conexión entre árboles y caminatas aleatorias (como las generadas por lanzamientos de monedas aleatorios) véase, por ejemplo, la Sección 6, "Caminatas y árboles", págs. 483-486, de Harris (1952) .

[26] Broutin, Devroye y Fraiman (2020) . De manera más general, todo proceso de Galton-Watson, condicionado a producir árboles de cierto tamaño, produce la misma distribución de probabilidad que un proceso crítico de Galton-Watson: véase la sección 2 de Kennedy (1975) .

[27] Para conocer el número esperado de nodos en cada nivel del árbol, véase, por ejemplo, Athreya y Ney (1972) , Sección IA2: Momentos, pág. 4.

[28] Por la equivalencia entre árboles y caminatas aleatorias, esto es lo mismo que la probabilidad de volver a cero por primera vez después $2n+2$ pasos en una caminata aleatoria simple , para lo cual véase, por ejemplo, Bertin (2021) , 2.5.1 Estadísticas de los tiempos de primer retorno al origen de una caminata aleatoria, págs. 70-72.

[FOOTNOTEJagers2011-29] Jagers (2011) .

[FOOTNOTEPopovic2004-30] Popovic (2004) .

[FOOTNOTEKargerStein1996-31] Karger y Stein (1996) .

[FOOTNOTEDevroyeRobson1995-32] Devroye y Robson (1995) .

[FOOTNOTEDevroye1984-33] Devroye (1984) .

[FOOTNOTEDevroye1992-34] Devroye (1992) .

[FOOTNOTEDevroyeKruszewski1996-35] Devroye y Kruszewski (1996) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]