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 en árboles binarios. Se utilizan comúnmente dos distribuciones diferentes: árboles binarios formados insertando nodos uno a la vez de acuerdo con una permutación aleatoria , y árboles binarios elegidos de una distribución discreta uniforme en la que todos los árboles distintos son igualmente probables. También es posible formar otras distribuciones, por ejemplo, dividiendo repetidamente. Agregar y eliminar nodos directamente en un árbol binario aleatorio interrumpirá en general su estructura aleatoria, pero el trucoy las estructuras de datos de árbol de búsqueda binaria aleatorias relacionadas utilizan el principio de árboles binarios formados a partir de una permutación aleatoria para mantener un árbol de búsqueda binario equilibrado dinámicamente a medida que se insertan y eliminan nodos.
Para árboles aleatorios que no son necesariamente binarios, consulte árbol aleatorio .
Árboles binarios de permutaciones aleatorias
Para cualquier conjunto de números (o, más generalmente, valores de algún orden total ), se puede formar un árbol de búsqueda binario en el que cada número se inserta en secuencia como una hoja del árbol, sin cambiar la estructura de los números previamente insertados. La posición en la que debe insertarse cada número se determina de forma única mediante una búsqueda binaria en el árbol formado por los números anteriores. Por ejemplo, si los tres números (1,3,2) se insertan en un árbol en esa secuencia, el número 1 se sentará 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 los números (1, 2, 3), pero solo se pueden construir cinco árboles a partir de ellos. Eso es porque las permutaciones (2,1,3) y (2,3,1) forman el mismo árbol.
Profundidad esperada de un nodo
Para cualquier elección fija de un valor x en un conjunto dado de n números, si uno permuta aleatoriamente los números y forma un árbol binario a partir de ellos como se describió anteriormente, el valor esperado de la longitud del camino desde la raíz del árbol hasta x es como máximo 2 log n + O (1) , donde " log " denota la función logaritmo natural y O introduce la notación O grande . Porque, el número esperado de antepasados de x es por linealidad de la expectativa igual a la suma, sobre todos los demás valores y en el conjunto, de la probabilidad de que y sea un antepasado de x . Y un valor y es un antepasado de x exactamente cuando y es el primer elemento que se inserta de los elementos en el intervalo [ x , y ] . Por lo tanto, los valores adyacentes ax en la secuencia ordenada de valores tienen probabilidad 1/2 de ser un antepasado de x , los valores a un paso tienen probabilidad 1/3 , etc. Sumando estas probabilidades para todas las posiciones en la secuencia ordenada da el doble de un número armónico , lo que lleva al límite anterior. Un límite de esta forma también es válido para la longitud de búsqueda esperada de una ruta a un valor fijo x que no es parte del conjunto dado. [1]
El camino mas largo
Aunque no es tan fácil de analizar como la longitud de ruta promedio, también se han realizado muchas investigaciones para determinar la expectativa (o límites de alta probabilidad) de la longitud de la ruta más larga en un árbol de búsqueda binario generado a partir de un orden de inserción aleatorio. Ahora se sabe que esta longitud, para un árbol con n nodos, es casi seguro
donde β es el número único en el rango 0 < β <1 que satisface la ecuación
Número esperado de hojas
En el modelo de permutación aleatoria, cada uno de los números del conjunto de números usados para formar el árbol, excepto el más pequeño y el más grande de los números, tiene una probabilidad de 1/3 de ser una hoja en el árbol, ya que es una hoja cuando insertó después de sus dos vecinos, y cualquiera de las seis permutaciones de estos dos vecinos y es igualmente probable. Con un razonamiento similar, el menor y el mayor de los números tienen una probabilidad de 1/2 de ser una hoja. Por tanto, el número esperado de hojas es la suma de estas probabilidades, que para n ≥ 2 es exactamente ( n + 1) / 3 .
Número de Strahler
El número de Strahler de un árbol es una medida más sensible de la distancia desde una hoja en la que un nodo tiene el número de Strahler i siempre que tenga un hijo con ese número o dos hijos con el número i - 1 . Para árboles de búsqueda binaria aleatoria de n nodos, las simulaciones sugieren que el número de Strahler esperado es. Sin embargo, solo el límite superiorrealmente ha sido probado. [3]
Treaps y árboles de búsqueda binarios aleatorios
En aplicaciones de estructuras de datos de árbol de búsqueda binaria, es raro que los valores en el árbol se inserten sin borrar 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 realizar inserciones y eliminaciones en un árbol de búsqueda binaria, manteniendo en cada paso como invariante la propiedad de que la forma del árbol es una variable aleatoria con la misma distribución que una búsqueda binaria aleatoria. árbol.
Si a un conjunto dado de números ordenados se le asignan prioridades numéricas (números distintos no relacionados con sus valores), estas prioridades pueden usarse para construir un árbol cartesiano para los números, un árbol binario que tiene como secuencia transversal en orden la secuencia ordenada de los números. y eso está ordenado por prioridades. Aunque se conocen algoritmos de construcción más eficientes, es útil pensar que un árbol cartesiano se construye insertando los números dados en un árbol de búsqueda binaria en orden de prioridad. Por lo tanto, por la elección de las prioridades o bien ser un conjunto de números reales aleatorios independientes en el intervalo de la unidad, o por la elección de ellos para ser una permutación aleatoria de los números de 1 a n (donde n es el número de nodos en el árbol), y manteniendo la propiedad de ordenación del montón usando 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 binario aleatorio. Dicha estructura de datos se conoce como treap o árbol de búsqueda binaria aleatoria. [4]
Árboles binarios uniformemente aleatorios
El número de árboles binarios con n nodos es un número catalán : para n = 1, 2, 3, ... estos números de árboles son
Así, si uno de estos árboles se selecciona de forma uniforme al azar, su probabilidad es el recíproco de un número catalán. Los árboles en este modelo tienen una profundidad esperada proporcional a la raíz cuadrada de n , en lugar de al logaritmo. [5] Sin embargo, el número de Strahler esperado de un árbol binario de n nodos uniformemente aleatorio es[6] menor que el número esperado de Strahler de árboles de búsqueda binaria aleatoria.
Debido a sus grandes alturas, este modelo de árboles aleatorios equiprobables no se utiliza generalmente para árboles de búsqueda binarios, pero se ha aplicado a problemas de modelado de árboles de análisis sintáctico de expresiones algebraicas en el diseño de compiladores [7] (donde el límite antes mencionado en El número de Strahler se traduce en el número de registros necesarios para evaluar una expresión [8] ) y para modelar árboles evolutivos . [9] En algunos casos, el análisis de árboles binarios aleatorios bajo el modelo de permutación aleatoria se puede transferir automáticamente al modelo uniforme. [10]
Árboles divididos aleatoriamente
Devroye y Kruszewski (1996) generan árboles binarios aleatorios con n nodos generando una variable aleatoria de valor real x en el intervalo unitario (0,1) , asignando los primeros xn nodos (redondeados hacia abajo a un número entero de nodos) a la izquierda subárbol, el siguiente nodo a la raíz y los nodos restantes al subárbol derecho, y continúan recursivamente en cada subárbol. Si x se elige uniformemente al azar en el intervalo, el resultado es el mismo que el del árbol de búsqueda binario aleatorio generado por una permutación aleatoria de los nodos, ya que es igualmente probable que cualquier nodo sea 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 para x . Como muestran Devroye y Kruszewski , al elegir una distribución beta en x y al usar una opción adecuada de forma para dibujar cada una de las ramas, los árboles matemáticos generados por este proceso se pueden usar para crear árboles botánicos de apariencia realista.
Notas
- ^ Hibbard (1962) ; Knuth (1973) ; Mahmoud (1992) , pág. 75.
- ^ Robson (1979) ; Pittel (1985) ; Devroye (1986) ; Mahmoud (1992) , págs. 91-99; Reed (2003) .
- ^ Kruszewski (1999)
- ^ Martínez y Roura (1998) ; Seidel y Aragon (1996) .
- ^ Knuth (2005) , p. 15.
- ^ , Devroye y Kruszewski (1995)
- ^ Mahmoud (1992) , p. 63.
- ^ Flajolet, Raoult y Vuillemin (1979) .
- ^ Aldous (1996) .
- ^ Mahmoud (1992) , p. 70.
Referencias
- Aldous, David (1996), "Distribuciones de probabilidad en cladogramas", en Aldous, David; Pemantle, Robin (eds.), Estructuras discretas aleatorias , Los volúmenes de IMA en matemáticas y sus aplicaciones, 76 , Springer-Verlag, págs. 1-18.
- Devroye, Luc (1986), "Una nota sobre la altura de los árboles de búsqueda binaria", Journal of the ACM , 33 (3): 489–498, doi : 10.1145 / 5925.5930.
- Devroye, Luc; Kruszewski, Paul (1995), "A note on the Horton-Strahler number for random trees", 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", 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, 1027 , Springer-Verlag, págs. 166-177, doi : 10.1007 / BFb0021801 , ISBN 978-3-540-60723-6.
- Drmota, Michael (2009), Árboles aleatorios: una interacción entre combinatoria y probabilidad , Springer-Verlag, ISBN 978-3-211-75355-2.
- Flajolet, P .; Raoult, JC; Vuillemin, J. (1979), "El número de registros necesarios para evaluar expresiones aritméticas", Informática teórica , 9 (1): 99-125, doi : 10.1016 / 0304-3975 (79) 90009-4.
- Hibbard, Thomas N. (1962), "Algunas propiedades combinatorias de ciertos árboles con aplicaciones a la búsqueda y clasificación", Journal of the ACM , 9 (1): 13-28, doi : 10.1145 / 321105.321108.
- Knuth, Donald E. (1973), "6.2.2 Búsqueda de árboles binarios", El arte de la programación informática , III , Addison-Wesley, págs. 422–451.
- Knuth, Donald E. (2005), "Borrador de la sección 7.2.1.6: Generación de todos los árboles" , El arte de la programación informática , IV.
- Kruszewski, Paul (1999), "A note on the Horton-Strahler number for random binary search trees", Information Processing Letters , 69 (1): 47–51, doi : 10.1016 / S0020-0190 (98) 00192-6.
- Mahmoud, Hosam M. (1992), Evolución de los árboles de búsqueda aleatoria , John Wiley & Sons.
- Martínez, Conrado; Roura, Salvador (1998), "Árboles de búsqueda binarios aleatorios" , Journal of the ACM , 45 (2): 288–323, CiteSeerX 10.1.1.17.243 , doi : 10.1145 / 274787.274812.
- Pittel, B. (1985), "Crecimiento asintótico de una clase de árboles aleatorios", Annals of Probability , 13 (2): 414–427, doi : 10.1214 / aop / 1176993000.
- Reed, Bruce (2003), "The height of a random binary search tree", Journal of the ACM , 50 (3): 306–332, doi : 10.1145 / 765568.765571.
- 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.
enlaces externos
- Estructuras de datos abiertos - Capítulo 7 - Árboles de búsqueda binaria aleatoria , Pat Morin