Árbol binario aleatorio

En informática y teoría de la probabilidad , un árbol binario aleatorio es un árbol binario seleccionado al azar a partir de alguna distribución de probabilidad en á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 del caso promedio de las estructuras de datos basadas en árboles binarios de búsqueda . Para esta aplicación, es común utilizar árboles aleatorios formados mediante la inserción de nodos de a uno por vez de acuerdo con 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 binarios de búsqueda 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 son igualmente probables, distribuciones en un número dado de nodos obtenidos por división repetida, intentos binarios y árboles de base 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 directamente debajo de él en el árbol), y esos hijos se designan como izquierdos o derechos. A veces es conveniente considerar en cambio á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 se puede convertir en un árbol binario extendido tratando todos sus nodos como internos y agregando un nodo externo por cada hijo faltante de un nodo interno. En la otra dirección, un árbol binario extendido con al menos un nodo interno se puede convertir nuevamente en un árbol binario no extendido eliminando todos sus nodos externos. De esta manera, estas dos formas son casi completamente equivalentes para los fines del análisis matemático, excepto que la forma extendida permite un árbol que consiste en un solo nodo externo, que no corresponde a nada en la forma no extendida. Para los fines de las estructuras de datos de computadora, las dos formas difieren, ya que los nodos externos de la primera forma se pueden representar explícitamente como objetos en una estructura de datos. ^[2]

En un árbol binario de búsqueda, los nodos internos se etiquetan con números u otros valores ordenados, llamados claves , dispuestos de modo que un recorrido inordenado del árbol enumere las claves en orden ordenado. 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 ordenado. Por ejemplo, la estructura de datos del árbol cartesiano utiliza árboles binarios etiquetados que no son necesariamente árboles binarios de búsqueda. ^[4]

Un árbol binario aleatorio es un árbol aleatorio extraído a partir de una determinada distribución de probabilidad en á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 binarios de búsqueda tengan esas claves. Sin embargo, son posibles otras distribuciones que no necesariamente generen árboles binarios de búsqueda ni proporcionen necesariamente un número fijo de nodos. ^[5]

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 binario de búsqueda en el que cada clave se inserta en secuencia como una hoja del árbol, sin cambiar 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 de las permutaciones del conjunto, teniendo cada permutación la misma probabilidad. ^[6]

Por ejemplo, si se insertan las tres claves 1,3,2 en un árbol binario de búsqueda 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 de ser generado, mientras que los otros cuatro árboles tienen cada uno probabilidad . ^[5] ${\tfrac {2}{6}}={\tfrac {1}{3}}$ ${\frac {1}{6}}$

Profundidad esperada de un nodo

Para cualquier clave en un conjunto dado de claves, el valor esperado de la longitud de la ruta desde la raíz hasta en un árbol binario de búsqueda aleatorio es como máximo , donde " " denota la función de logaritmo natural y la introduce la notación O mayúscula . Por linealidad de la expectativa , el número esperado de ancestros de es igual a la suma, sobre otras claves , de la probabilidad de que sea un ancestro de . Una clave es un ancestro de exactamente cuándo es la primera clave que se inserta desde el intervalo . 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 en la secuencia ordenada de claves tienen probabilidad de ser un ancestro de , las claves un paso más allá tienen probabilidad , etc. La suma de estas probabilidades forma dos copias de la serie armónica que se extienden desde en ambas direcciones en la secuencia ordenada, dando el límite anterior. Este límite también se cumple para la longitud de la ruta de búsqueda esperada para un valor que es una de las claves dadas. ^[7] ${\estilo de visualización x}$ ${\estilo de visualización n}$ ${\estilo de visualización x}$ $2\log n+O(1)$ ${\estilo de visualización \log}$ ${\estilo de visualización O}$ ${\estilo de visualización x}$ ${\estilo de visualización y}$ ${\estilo de visualización y}$ ${\estilo de visualización x}$ ${\estilo de visualización y}$ ${\estilo de visualización x}$ ${\estilo de visualización y}$ ${\estilo de visualización [x,y]}$ ${\estilo de visualización x}$ ${\frac {1}{2}}$ ${\estilo de visualización x}$ ${\frac {1}{3}}$ ${\estilo de visualización x}$ $2\log n+O(1)$ ${\estilo de visualización x}$

El camino más largo

La ruta más larga de raíz a hoja, en un árbol binario de búsqueda aleatorio, es más larga que la longitud de ruta esperada, pero solo por un factor constante. Su longitud, para un árbol con nodos, es con alta probabilidad aproximadamente ${\estilo de visualización n}$

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

¿Dónde está el número único en el rango que satisface la ecuación? $\beta$ $0<\beta <1$

\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 de ser una hoja en el árbol. Esto se debe a que es una hoja cuando se inserta después de sus dos vecinas, lo que sucede para dos de las seis permutaciones de ella y sus dos vecinas, todas las cuales son igualmente probables. Por un razonamiento similar, la clave más pequeña y la más grande tienen probabilidad de ser una hoja. Por lo tanto, el número esperado de hojas es la suma de estas probabilidades, que para es exactamente . ^[9] ${\tfrac {1}{3}}$ ${\tfrac {1}{2}}$ $n\geq 2$ $(n+1)/3$

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 bajo esos vértices. Una hoja (nodo externo) tiene el número de Strahler 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 diferentes números de Strahler, el número de Strahler de su padre es el mayor de los dos números de hijos. Pero si dos hijos tienen números de Strahler iguales, su padre tiene un número que es mayor en uno. El número de Strahler de todo el árbol es el número en el nodo raíz. Para árboles binarios de búsqueda aleatoria de nodos, las simulaciones sugieren que el número de Strahler esperado es . Se ha demostrado un límite superior más débil . ^[10] $n$ $\log _{3}n+O(1)$ $\log _{3}n+o(\log n)$

Árboles de búsqueda binarios aleatorios y treaps

En las aplicaciones de estructuras de datos de árboles binarios de búsqueda, es raro que las claves se inserten sin eliminarlas en un orden aleatorio, lo que limita las aplicaciones directas de á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 es aleatoria, como si las claves se hubieran insertado aleatoriamente. ^[11]

Si a un conjunto dado de claves se le asignan prioridades numéricas (no relacionadas con sus valores), estas prioridades pueden usarse para construir un árbol cartesiano para los números, el árbol binario de búsqueda que resultaría de insertar las claves en orden de prioridad. Al elegir las prioridades como números reales aleatorios independientes en el intervalo unitario, y al mantener la estructura del árbol cartesiano utilizando 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 binario de búsqueda aleatorio. Una estructura de datos de este tipo se conoce como treap o árbol binario de búsqueda aleatorio. ^[11]

Las variantes del treap, que incluyen el árbol zip y el árbol zip-zip, reemplazan las rotaciones de árboles mediante operaciones de "compresión" que dividen y fusionan los árboles y que limitan la cantidad de bits aleatorios que se deben generar y almacenar 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 uniformemente aleatorios

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

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

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

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

. ^[16]

El número de Strahler esperado de un árbol binario de nodos uniformemente aleatorio es , menor que el número de Strahler esperado de árboles binarios de búsqueda aleatorios. ^[17] $n$ $\log _{4}n+O(1)$

Debido a sus grandes alturas, este modelo de árboles aleatorios equiprobables no se suele utilizar para árboles binarios de búsqueda. Sin embargo, tiene otras aplicaciones, entre ellas:

Modelado de árboles de análisis 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 , aplicación original para la que 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 uniformemente aleatorio de un tamaño especificado en el tiempo lineal en el tamaño, mediante el siguiente proceso. Comienza con un árbol que consiste en un solo nodo externo. Luego, mientras el árbol actual no haya alcanzado el tamaño objetivo, elige repetidamente uno de sus nodos (interno o externo) de manera uniforme y aleatoria. Reemplaza el nodo elegido por un nuevo nodo interno, teniendo el nodo elegido como uno de sus hijos (igualmente probable izquierdo o derecho), y teniendo un nuevo nodo externo como su otro hijo. Detente 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 los que el número de hijos en cada nodo se elige aleatoriamente, independientemente de los demás nodos. Para los á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 en la que el nodo raíz puede ser externo, se elige que sea interno con una probabilidad especificada o externo con una probabilidad . Si es interno, sus dos hijos son árboles generados recursivamente por el mismo proceso. $p$ $1-p$
En la versión donde el nodo raíz debe ser interno, sus hijos izquierdo y derecho se determinan como internos con probabilidad o externos con probabilidad , independientemente uno del otro. En el caso en que sean internos, son las raíces de árboles que se generan recursivamente por el mismo proceso. $p$ $1-p$

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

Análisis

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

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

. ^[24]

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

Como 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 de nodos se generan a partir de secuencias de lanzamiento de moneda (únicas) de la misma longitud, y son igualmente probables, independientemente de . Es decir, la elección de 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 de manera uniforme al azar. ^[26] Para valores de por debajo de la probabilidad crítica , valores más pequeños de producirán árboles con un tamaño esperado más pequeño , mientras que valores más grandes de producirán árboles con un tamaño esperado más grande. En la probabilidad crítica no hay un límite finito en el tamaño esperado de los árboles generados por este proceso. Más precisamente, para cualquier , el número esperado de nodos en la profundidad del árbol es , y el tamaño esperado del árbol se puede obtener sumando los números esperados de nodos en cada profundidad. Para esto se obtiene una serie geométrica $n$ $p$ $p$ $p$ $p={\tfrac {1}{2}}$ $p$ $p$ $p={\tfrac {1}{2}}$ $p$ $i$ $(2p)^{i}$ $p<{\tfrac {1}{2}}$

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

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

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

{\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 los apellidos humanos , y se han aplicado ampliamente de manera más general a la dinámica de las 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 un modelo para la especiación , donde se conoce como el proceso de ramificación crítica . En este proceso, cada especie tiene una vida útil distribuida exponencialmente y, a lo largo de su vida, produce especies hijas a una tasa igual a la vida útil. Cuando se produce un hijo, el padre continúa como la rama izquierda del árbol evolutivo y el hijo 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, y cada llamada tiene una probabilidad de al menos preservar el valor de solución correcto. El árbol aleatorio modela el subárbol de llamadas recursivas correctas. El algoritmo tiene éxito en un grafo de vértices siempre que este árbol aleatorio de llamadas recursivas correctas tenga una rama de profundidad al menos , alcanzando el caso base de su recursión. La probabilidad de éxito es , lo que produce uno de los factores logarítmicos en el tiempo de ejecución del algoritmo. ^[31] ${\tfrac {1}{2}}$ $n$ $2\log _{2}n$ $\Omega (1/\log n)$ $O(n^{2}\log ^{3}n)$

Proceso de Yule

Devroye y Robson consideran un proceso aleatorio de tiempo continuo relacionado en el que cada nodo externo es eventualmente reemplazado 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 dan a luz a una tasa constante: dar a luz a un hijo, en el proceso de Yule, corresponde a ser reemplazado por dos hijos, en el modelo de Devroye y Robson. Si este proceso se detiene en cualquier momento fijo, el resultado es un árbol binario de un tamaño aleatorio (dependiendo del tiempo de detención), distribuido de acuerdo con 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 sus números 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 solo nodo externo y reemplaza repetidamente un nodo externo elegido aleatoriamente por un nodo interno con dos hijos externos. Nuevamente, si esto se detiene en un momento fijo (con un tamaño fijo), el árbol resultante se distribuye de acuerdo con el modelo de permutación aleatoria para ese tamaño. ^[1]

Intentos binarios

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 compartidas por dos o más de los números. Los hijos izquierdo y derecho de un nodo interno se obtienen extendiendo el prefijo correspondiente por 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. Los tries binarios aleatorios se han estudiado, por ejemplo, para conjuntos de números reales aleatorios generados independientemente en el intervalo unitario . A pesar del hecho de que estos árboles pueden tener algunos nodos externos vacíos, tienden a estar mejor equilibrados que los árboles binarios de búsqueda aleatorios. Para números reales uniformemente aleatorios en el intervalo unitario, o más generalmente para cualquier distribución de probabilidad integrable al cuadrado en el intervalo unitario, la profundidad promedio de un nodo es asintóticamente , y la altura promedio de todo el árbol es asintóticamente . El análisis de estos árboles se puede aplicar a la complejidad computacional de los algoritmos de ordenamiento basados en trie . ^[33] $n$ $\log _{2}n$ $2\log _{2}n$

Una variante del trie, el árbol de base o trie comprimido, elimina los nodos externos vacíos y sus nodos internos padre. 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 de base para números binarios distribuidos uniformemente, el camino más corto a raíz de hoja tiene longitud y el más largo a raíz de hoja tiene longitud, ambos con alta probabilidad . ^[34] $n$ $\log _{2}n-\log _{2}\log n+o(\log \log n)$ $\log _{2}n+{\sqrt {2\log _{2}n}}+o({\sqrt {\log n}}),$

Árboles divididos aleatoriamente

Luc Devroye y Paul Kruszewski describen un proceso recursivo para construir árboles binarios aleatorios con nodos. Genera una variable aleatoria de valor real en el intervalo unitario , asigna los primeros 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 se elige uniformemente al azar en el intervalo, el resultado es el mismo que el árbol binario de búsqueda 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 uniformemente aleatorio, 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 uniformemente aleatorio también puede generarse mediante una elección diferente de distribución (dependiendo de ) para . Como muestran, al elegir una distribución beta y utilizar una elección apropiada de forma para dibujar cada una de las ramas, los árboles matemáticos generados por este proceso se pueden utilizar para crear árboles botánicos de aspecto realista. ^[35] $n$ $x$ $(0,1)$ $xn$ $x$ $n$ $x$ $x$

Notas

^ desde Drmota (2009), pág. 19.
^ Knuth (1997).
^ Knuth (1973).
^ Vuillemin (1980).
^ desde 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).
^ ab 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$ donde es la función generadora de probabilidad de la distribución sobre el número de hijos, aquí . 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. $g$ $g(x)=(1-p)+px^{2}$
^ Para la conexión entre los árboles y los paseos aleatorios (generados por lanzamientos aleatorios de monedas), véase, por ejemplo, la Sección 6, "Paseos y árboles", págs. 483-486, de Harris (1952).
^ Broutin, Devroye y Fraiman (2020). En términos más generales, todo proceso de Galton-Watson, condicionado a la producción de árboles de un cierto tamaño, produce la misma distribución de probabilidad que un proceso de Galton-Watson crítico: véase la sección 2 de Kennedy (1975).
^ Para 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 regresar primero a cero después de los 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. $2n+2$
^ Cazadores (2011).
^ Popović (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.), Random Discrete Structures, The IMA Volumes in Mathematics and its Applications, vol. 76, Springer-Verlag, págs. 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", Matemáticas de la investigación de operaciones , 9 : 43–65, doi :10.1287/moor.9.1.43
Broutin, Nicolas; Devroye, Luc ; Fraiman, Nicolas (abril de 2020), "Funciones recursivas en árboles condicionales de Galton-Watson" (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), "Un análisis probabilístico de la altura de los 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 binarios de búsqueda" (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 los árboles 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 la combinatoria y la 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.), Algorithms and Data Structures – 18th International Symposium, WADS 2023, Montreal, QC, Canadá, 31 de julio – 2 de agosto de 2023, Actas , Lecture Notes in Computer Science, vol. 14079, Springer, págs. 474–492, arXiv : 2307.07660 , doi :10.1007/978-3-031-38906-1_31, ISBN 978-3-031-38905-4
Harris, TE (1952), "Distribuciones de primer paso y 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 ordenació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 para el problema del corte mínimo" (PDF) , Journal of the ACM , 43 (4): 601, doi :10.1145/234533.234534
Kennedy, Douglas P. (1975), "El proceso 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 árboles binarios", 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 desde el original el 2023-01-02 , consultado el 2009-03-31
Kruszewski, Paul (1999), "Una nota sobre el número de Horton-Strahler para árboles de búsqueda binaria aleatoria", 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 aleatoria , John Wiley & Sons
Martínez, Conrado; Roura, Salvador (1998), "Árboles binarios de búsqueda aleatorizados", 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 aleatoria", Open Data Structures (en pseudocódigo) (PDF) (edición 0.1Gβ), 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 aleatoria", 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 binarios", Australian Computer Journal , 11 : 151–153
Seidel, Raimund ; Aragon, Cecilia R. (1996), "Árboles de búsqueda aleatorizados", Algorithmica , 16 (4–5): 464–497, doi :10.1007/s004539900061 (inactivo 2024-11-05){{citation}}: CS1 maint: DOI inactive as of November 2024 (link)
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 de los números de corrientes", 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