Árvore binária aleatória - Random binary tree

Na ciência da computação e na teoria da probabilidade , uma árvore binária aleatória é uma árvore binária selecionada aleatoriamente de alguma distribuição de probabilidade em árvores binárias. Duas distribuições diferentes são comumente usadas: árvores binárias formadas pela inserção de nós um por vez de acordo com uma permutação aleatória , e árvores binárias escolhidas de uma distribuição discreta uniforme em que todas as árvores distintas são igualmente prováveis. Também é possível formar outras distribuições, por exemplo, por divisão repetida. Adicionar e remover nós diretamente em uma árvore binária aleatória em geral interromperá sua estrutura aleatória, mas o treap e as estruturas de dados da árvore de pesquisa binária aleatória relacionadas usam o princípio de árvores binárias formadas a partir de uma permutação aleatória para manter uma árvore de pesquisa binária balanceada dinamicamente conforme os nós são inseridos e excluídos.

Para árvores aleatórias que não são necessariamente binárias, consulte árvore aleatória .

Árvores binárias de permutações aleatórias

Para qualquer conjunto de números (ou, mais geralmente, valores de alguma ordem total ), pode-se formar uma árvore de busca binária na qual cada número é inserido em seqüência como uma folha da árvore, sem alterar a estrutura dos números inseridos anteriormente. A posição em que cada número deve ser inserido é determinada exclusivamente por uma pesquisa binária na árvore formada pelos números anteriores. Por exemplo, se os três números (1,3,2) são inseridos em uma árvore nessa sequência, o número 1 ficará na raiz da árvore, o número 3 será colocado como seu filho certo, e o número 2 como o filho esquerdo do número 3. Existem seis diferentes permutações dos números (1,2,3), mas apenas cinco árvores podem ser construídas a partir delas. Isso porque as permutações (2,1,3) e (2,3,1) formam a mesma árvore.

Profundidade esperada de um nó

Para qualquer escolha fixa de um valor $x$ em um determinado conjunto de $n$ números, se alguém permutar os números aleatoriamente e formar uma árvore binária a partir deles como descrito acima, o valor esperado do comprimento do caminho da raiz da árvore até $x$ é no máximo $2 log n + O (1)$ , onde " $log$ " denota a função de logaritmo natural e o $O$ introduz a notação de O grande . Pois, o número esperado de ancestrais de $x$ é pela linearidade da expectativa igual à soma, sobre todos os outros valores $y$ no conjunto, da probabilidade de que $y$ seja um ancestral de $x$ . E um valor $y$ é um ancestral de $x$ exatamente quando $y$ é o primeiro elemento a ser inserido a partir dos elementos no intervalo $[x, y]$ . Assim, os valores que são adjacentes $ax$ na sequência ordenada de valores têm probabilidade $1/2$ de serem ancestrais de $x$ , os valores a um passo têm probabilidade $1/3$ , etc. Adicionando estas probabilidades para todas as posições na sequência ordenada dá duas vezes um número Harmônico , levando ao limite acima. Um limite dessa forma vale também para o comprimento de pesquisa esperado de um caminho para um valor fixo $x$ que não faz parte do conjunto fornecido.

Para entender isso usando registros mín-máx. O número em uma permutação aleatória é o registro min (max) significa que é o valor min (max) da primeira posição para sua posição. Considere um exemplo simples $l$ = (2, 4, 3, 6, 5, 1). Os registros mínimos em $l$ são 2, 1 pesquisando o valor mínimo do início ao fim. Da mesma forma, as recodificações máximas em $l$ são 2, 4, 6. O número esperado de registros mín (máx.) É toda a probabilidade de cada número em uma permutação aleatória. Para a posição $i$ , tem probabilidade de 1 / $i$ . Portanto, o número esperado de registros mínimo (máximo) é um número harmônico. Para pesquisar 3 em $l$ , todos os números em (2, 1) são menores que 3 e (4, 6, 5, 1) é maior que 3. A pesquisa na árvore binária aleatória de $l$ conta apenas o máximo de registros em (2 , 1) e registros mínimos em (4, 6, 5, 1) - é por isso que é duas vezes um número Harmônico.

O caminho mais longo

Embora não seja tão fácil de analisar quanto o comprimento médio do caminho, também houve muitas pesquisas sobre a determinação da expectativa (ou limites de alta probabilidade) do comprimento do caminho mais longo em uma árvore de pesquisa binária gerada a partir de uma ordem de inserção aleatória. Sabe-se agora que este comprimento, para uma árvore com $n$ nós, é quase certo

{\ displaystyle {\ frac {1} {\ beta}} \ log n \ aprox. 4.311 \ log n,}

onde $β$ é o número único no intervalo $0 < β <1$ satisfazendo a equação

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

Número esperado de folhas

No modelo de permutação aleatória, cada um dos números do conjunto de números usados para formar a árvore, exceto o menor e o maior dos números, tem probabilidade de $1/3$ de ser uma folha na árvore, pois é uma folha quando ele é inserido após seus dois vizinhos e qualquer uma das seis permutações desses dois vizinhos e é igualmente provável. Por raciocínio semelhante, o menor e o maior dos números têm probabilidade $1/2$ de ser uma folha. Portanto, o número esperado de folhas é a soma dessas probabilidades, que para $n \geq 2$ é exatamente $(n + 1) / 3$ .

Número Strahler

O número de Strahler de uma árvore é uma medida mais sensível da distância de uma folha na qual um nó tem o número de Strahler $i$ sempre que tem um filho com esse número ou dois filhos com o número $i - 1$ . Para árvores de busca binária aleatória de n- nós, as simulações sugerem que o número de Strahler esperado é . No entanto, apenas o limite superior foi realmente comprovado. ${\ displaystyle \ log _ {3} n + o (\ log n)}$ ${\ displaystyle \ log _ {3} n + O (1)}$

Treaps e árvores de pesquisa binárias aleatórias

Em aplicações de estruturas de dados de árvore de pesquisa binária, é raro que os valores na árvore sejam inseridos sem exclusão em uma ordem aleatória, limitando as aplicações diretas de árvores binárias aleatórias. No entanto, os designers de algoritmos desenvolveram estruturas de dados que permitem que inserções e exclusões sejam realizadas em uma árvore de pesquisa binária, em cada etapa mantendo como uma propriedade invariante de que a forma da árvore é uma variável aleatória com a mesma distribuição de uma pesquisa binária aleatória árvore.

Se um determinado conjunto de números ordenados é atribuído a prioridades numéricas (números distintos não relacionados aos seus valores), essas prioridades podem ser usadas para construir uma árvore cartesiana para os números, uma árvore binária que tem como sua sequência transversal de ordem a sequência classificada dos números e isso é ordenado por heap por prioridades. Embora algoritmos de construção mais eficientes sejam conhecidos, é útil pensar em uma árvore cartesiana como sendo construída inserindo os números dados em uma árvore de busca binária em ordem de prioridade. Assim, escolhendo as prioridades como um conjunto de números reais aleatórios independentes no intervalo de unidade, ou escolhendo-os como uma permutação aleatória dos números de $1$ a $n$ (onde $n$ é o número de nós na árvore), e mantendo a propriedade de ordenação de heap usando rotações de árvore após qualquer inserção ou exclusão de um nó, é possível manter uma estrutura de dados que se comporta como uma árvore de pesquisa binária aleatória. Essa estrutura de dados é conhecida como treap ou árvore de pesquisa binária aleatória.

Árvores binárias uniformemente aleatórias

O número de árvores binárias com n nós é um número catalão : para $n = 1, 2, 3, ...$ esses números de árvores são

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...

(sequência A000108 no OEIS ).

Assim, se uma dessas árvores for selecionada uniformemente ao acaso, sua probabilidade será a recíproca de um número catalão. As árvores neste modelo têm uma profundidade esperada proporcional à raiz quadrada de $n$ , ao invés do logaritmo. No entanto, o número de Strahler esperado de uma árvore binária de n- nós uniformemente aleatória é menor do que o número de Strahler esperado de árvores de pesquisa binárias aleatórias. ${\ displaystyle \ log _ {4} n + O (1)}$

Devido às suas grandes alturas, este modelo de árvores aleatórias equiprováveis geralmente não é usado para árvores de pesquisa binárias, mas tem sido aplicado a problemas de modelagem de árvores de análise de expressões algébricas no projeto do compilador (onde o limite acima mencionado no número de Strahler se traduz no número de registros necessários para avaliar uma expressão) e para modelar árvores evolutivas . Em alguns casos, a análise de árvores binárias aleatórias sob o modelo de permutação aleatória pode ser automaticamente transferida para o modelo uniforme.

Árvores divididas aleatoriamente

Devroye & Kruszewski (1996) geram árvores binárias aleatórias com $n$ nós, gerando uma variável aleatória de valor real $x$ no intervalo de unidade $(0,1)$ , atribuindo os primeiros $xn$ nós (arredondados para um número inteiro de nós) à esquerda subárvore, o próximo nó para a raiz e os nós restantes para a subárvore direita, e continuando recursivamente em cada subárvore. Se $x$ é escolhido uniformemente ao acaso no intervalo, o resultado é o mesmo que a árvore de pesquisa binária aleatória gerada por uma permutação aleatória dos nós, já que qualquer nó tem a mesma probabilidade de ser escolhido como raiz; no entanto, esta formulação permite que outras distribuições sejam usadas em seu lugar. Por exemplo, no modelo de árvore binária uniformemente aleatório, uma vez que uma raiz é fixada, cada uma de suas duas subárvores também deve ser uniformemente aleatória, então o modelo uniformemente aleatório também pode ser gerado por uma escolha diferente de distribuição para $x$ . Como Devroye e Kruszewski mostram, escolhendo uma distribuição beta em $xe$ usando uma escolha apropriada de forma para desenhar cada um dos ramos, as árvores matemáticas geradas por este processo podem ser usadas para criar árvores botânicas de aparência realista.

Notas

Referências

Aldous, David (1996), "Probability distributions on cladograms", in Aldous, David; Pemantle, Robin (eds.), Random Discrete Structures , The IMA Volumes in Mathematics and its Applications, 76 , Springer-Verlag, pp. 1-18.
Devroye, Luc (1986), "A note on the height of binary search trees", 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), "A beleza botânica das árvores binárias aleatórias", em Brandenburg, Franz J. (ed.), Graph Drawing: 3rd Int. Symp., GD'95, Passau, Germany, September 20-22, 1995 , Lecture Notes in Computer Science, 1027 , Springer-Verlag, pp. 166-177, doi : 10.1007 / BFb0021801 , ISBN 978-3-540-60723-6.
Drmota, Michael (2009), Random Trees: An Interplay between Combinatorics and Probability , Springer-Verlag, ISBN 978-3-211-75355-2.
Flajolet, P .; Raoult, JC; Vuillemin, J. (1979), "O número de registros necessários para avaliar expressões aritméticas", Theoretical Computer Science , 9 (1): 99–125, doi : 10.1016 / 0304-3975 (79) 90009-4.
Hibbard, Thomas N. (1962), "Algumas propriedades combinatórias de certas árvores com aplicações para pesquisa e classificação", Journal of the ACM , 9 (1): 13-28, doi : 10.1145 / 321105.321108.
Knuth, Donald E. (1973), "6.2.2 Binary Tree Searching", The Art of Computer Programming , III , Addison-Wesley, pp. 422-451.
Knuth, Donald E. (2005), "Rascunho da Seção 7.2.1.6: Gerando Todas as Árvores" , The Art of Computer Programming , 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), Evolution of Random Search Trees , John Wiley & Sons.
Martinez, Conrado; Roura, Salvador (1998), "Randomized binary search trees" , Journal of the ACM , 45 (2): 288-323, CiteSeerX 10.1.1.17.243 , doi : 10.1145 / 274787.274812.
Pittel, B. (1985), "Asymptotical growth of a class of random trees", 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), "The height of binary search trees", Australian Computer Journal , 11 : 151-153.
Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees" , Algorithmica , 16 (4/5): 464–497, doi : 10.1007 / s004539900061.

links externos

Estruturas de dados abertas - Capítulo 7 - Árvores de pesquisa binárias aleatórias , Pat Morin

Languages

In other projects