Árvore binária aleatória

Em ciência da computação e teoria da probabilidade, uma árvore binária aleatória refere-se a uma árvore binária selecionada aleatoriamente a partir de uma distribuição de probabilidade em árvores binárias. Duas distribuições diferentes são comumente utilizadas: árvores binárias formadas por inserção de nós um de cada vez, de acordo com uma permutação aleatória, e árvores binárias escolhidas a partir de uma distribuição uniforme discreta, nas quais, todas as árvores distintas são igualmente prováveis. Também é possível formar outras distribuições, por exemplo, repetindo-se o particionamento. Adicionar e remover nós diretamente em uma árvore binária aleatória, em geral, irá interromper sua estrutura aleatória, mas outras estruturas de dados árvore de busca binária usam o princípio de árvores binárias formadas a partir de uma permutação aleatória, a fim de manter uma árvore de busca binária balanceada de forma dinâmica, ao inserir e remover nós.

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

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

Para qualquer conjunto de números (ou, mais geralmente, valores de uma certa ordem total), pode-se formar uma árvore de busca binária na qual, cada número é inserido na sequência como uma folha de árvore, sem alterar a estrutura dos números inseridos anteriormente. A posição em que cada número deve ser inserido é exclusivamente determinada por uma busca 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 sequencialmente, o número 1, será alocado à raiz da árvore, o número 3 será colocado como o seu direito de filho, e o número 2 como filho à esquerda do número 3. Existem seis diferentes permutações dos números (1,2,3), mas apenas cinco árvores podem ser construídos a partir deles. O motivo é simples: as permutações (2,1,3) e (2,3,1) formam uma mesma árvore.

Profundidade esperada de um nó

Para qualquer escolha fixa de um valor x em um dado conjunto de n números, se permutarmos os números aleatoriamente e as formarmos uma árvore binária 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 o logaritmo natural da função e O introduz big O notation. O número esperado de antepassados de x é dado pela linearidade da expectativa igual a soma, sobre todos os outros valores de y no conjunto, da probabilidade de que y é um ancestral de x. E, um valor y é um ancestral de x

exatamente quando y é o primeiro elemento a ser inserido a partir de elementos no intervalo [x,y]. Assim, os valores que são adjacentes a x a ordenada seqüência de valores de probabilidade 1/2 de ser um ancestral de x, os valores de a um passo de ter probabilidade 1/3, etc. Adicionando-se estas probabilidades para todas as posições na sequência ordenada resulta no dobro de um número harmônico, levando ao limite acima. Tal limite também vale para a busca esperada do tamanho de um caminho para um valor fixo de x, que não é parte do conjunto dado.

The longest path

Apesar de não ser tão fácil analisar a média de comprimento de caminho, existe muita pesquisa sobre a determinação da expectativa (ou alta probabilidade de limites) do comprimento do maior caminho em uma árvore de busca binária gerada a partir da inserção em ordem aleatória. Sabe-se que esse comprimento, para uma árvore com n nós, é quase certamente

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

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

$\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 para o menor e o maior, têm probabilidade 1/3 de ser uma folha de árvore. Este número é uma folha quando é inserido depois de seus dois vizinhos, e qualquer uma das seis permutações desses dois vizinhos e são igualmente prováveis. Por raciocínio semelhante, o menor e o maior de todos os 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 ≥ 2 é exatamente (n + 1)/3.

Treaps e árvores de busca binária aleatórias

Em aplicações de estruturas de dados de árvore de busca binária, é raro para os valores em a árvore serem inseridos sem exclusão em uma ordem aleatória, limitando as aplicações diretas de árvores binárias aleatórias. No entanto, designers de algoritmos criam estruturas de dados que permitem inserções e exclusões serem executadas em uma árvore de busca binária em cada etapa de manutenção como uma invariante. A propriedade que forma a árvore é uma variável aleatória com a distribuição de uma árvore de busca binária aleatória.

Se um determinado conjunto números ordenados é atribuído de prioridades numéricas (números distintos relacionados aos seus valores), essas prioridades podem ser usadas para a construção de um árvore cartesiana para os números: uma árvore binária que tem como sequência de percurso transversal, a sequência ordenada de números e é a pilha ordenada por prioridades. Apesar de algoritmos mais eficientes de construção serem conhecidos, é útil pensar em uma árvore cartesiana como sendo construída ao inserir os números em uma árvore de busca binária em ordem de prioridade. Assim, ao escolher as prioridades para ser um conjunto de números reais aleatórios independentes na unidade do intervalo, 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 do heap usando uma árvore de rotações depois de qualquer inserção ou exclusão de um nó, é possível manter uma estrutura de dados que se comporta como uma árvore de busca binária aleatória. Tal estrutura de dados é conhecida como um treap ou uma árvore de busca binária aleatória.

Árvores binárias uniformemente aleatórias 

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

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, … (sequência A000108 na OEIS).

Assim, se uma dessas árvores é selecionada uniformemente ao acaso, a sua probabilidade é a recíproca de um número de Catalan. Árvores neste modelo têm profundidade esperada proporcional à raiz quadrada de n, em vez de ser proporcional ao logaritmo. No entanto, o número de Strahler de uma árvore binária uniformemente aleatória, é uma maneira mais sensível de medir a distância a partir de uma folha em que um nó tem o número de Strahler i, sempre que ele tem um filho com esse número ou dois filhos, com o número de i − 1, com alta probabilidade logarítmica.

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

Árvores de divisão aleatórias

Devroye & Kruszewski (1996) gera árvores binárias aleatórias com n nós, gerando uma variável aleatória de valor real  x na unidade de intervalo (0,1), atribuindo o primeiro xn nós (arredondado para um número inteiro de nós) para a sub-árvore esquerda, o próximo nó para a raiz, e os nós restantes da sub-árvore direita, e, assim, continua recursivamente em cada sub-árvore. Se x é escolhido uniformemente ao acaso no intervalo, o resultado é o mesmo para a árvore de busca binária aleatória gerada por uma permutação aleatória dos nós. Qualquer nó tem a mesma probabilidade de ser escolhido como raiz; no entanto, esta formulação permite que outras distribuições serem usadas em vez disso. Por exemplo, na árvore binária uniformemente aleatória do modelo, uma vez que uma raiz é fixa, cada uma das duas sub-árvores também devem ser uniformemente aleatórias. Assim, o modelo uniformemente aleatório também pode ser gerado por uma escolha diferente da distribuição de x. Como Devroye e Kruszewski mostram, escolhendo uma distribuição beta em x e usando uma escolha adequada, de forma a desenhar cada um dos ramos, as árvores matemáticas geradas por este processo podem ser usadas para criar árvores botânicas que parecem realistas.

Notas

Em ciência da computação e teoria da probabilidade, uma árvore binária aleatória refere-se a uma árvore binária selecionada aleatoriamente a partir de uma distribuição de probabilidade em árvores binárias. Duas distribuições diferentes são comumente utilizadas: árvores binárias formadas por inserção de nós um de cada vez, de acordo com uma permutação aleatória, e árvores binárias escolhidas a partir de uma distribuição uniforme discreta, nas quais, todas as árvores distintas são igualmente prováveis. Também é possível formar outras distribuições, por exemplo, repetindo-se o particionamento. Adicionar e remover nós diretamente em uma árvore binária aleatória, em geral, irá interromper sua estrutura aleatória, mas outras estruturas de dados árvore de busca binária usam o princípio de árvores binárias formadas a partir de uma permutação aleatória, a fim de manter uma árvore de busca binária balanceada de forma dinâmica, ao inserir e remover nós.

Referências

• Aldous, David (1996), «Probability distributions on cladograms», in: Aldous, David; Pemantle, Robin, 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), «The botanical beauty of random binary trees», in: Brandenburg, Franz J., Graph Drawing: 3rd Int. Symp., GD'95, Passau, Germany, September 20-22, 1995, ISBN 3-540-60723-4, Lecture Notes in Computer Science, 1027, Springer-Verlag, pp. 166–177, doi:10.1007/BFb0021801 .
• Drmota, Michael (2009), Random Trees : An Interplay between Combinatorics and Probability, ISBN 978-3-211-75355-2, Springer-Verlag .
• Flajolet, P.; Raoult, J. C.; Vuillemin, J. (1979), «The number of registers required for evaluating arithmetic expressions», Theoretical Computer Science, 9 (1): 99–125, doi:10.1016/0304-3975(79)90009-4 .
• Hibbard, Thomas N. (1962), "Some combinatorial properties of certain trees with applications to searching and sorting", Journal of the ACM 9 (1): 13–28, doi:10.1145/321105.321108
   .
• Knuth, Donald M. (1973), «6.2.2 Binary Tree Searching», The Art of Computer Programming, III, Addison-Wesley, pp. 422–451 .
• Knuth, Donald M. (2005), «Draft of Section 7.2.1.6: Generating All Trees», The Art of Computer Programming, IV .
• Mahmoud, Hosam M. (1992), Evolution of Random Search Trees, John Wiley & Sons .
• Martinez, Conrado; Roura, Salvador (1998), «Randomized binary search trees», ACM Press, Journal of the ACM, 45 (2): 288–323, 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, J. M. (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 .

Ligações externas

• «Open Data Structures - Chapter 7 - Random Binary Search Trees». opendatastructures.org