Árvore AVL em C++

Aqui está um código em C++ para uma Árvore AVL visando fins mais educacionais do que práticos. Apesar da teoria ser muito importante, não adianta nada ler pseudo-algorítmos sem saber como a teoria pode ser, de fato, aplicada. Ainda mais quando a maioria dos livros-texto deixa o método de remoção como exercício. Que mania!

A Árvore apresentada abaixo utiliza apenas uma técnica que pode parecer estranha, a primeira vista, para quem está acostumado a tratar com árvores em algoritmo puro. As subárvores esquerda e direita, presentes em cada nó, estão dispostas em um vetor de dois elementos. Isto traz uma vantagem imensa na hora de rotacionar a árvore, pois corta a necessidade de métodos auxiliares pela metade. Ao invés de termos de implementar rotações à esquerda e depois a direita, por exemplo, aproveitamos um mesmo método para realizar a operação de rotação em ambas as direções.

Fora este recurso adicional, o restante da implementação é bem similar aos textbooks que encontramos por aí. O nó não precisa de uma referência adicional ao seu pai (que é desnecessária, por sinal) e guarda apenas seu fator de balancemento (outras implementações guardam sua altura). O código é orientado a objetos (nada de código C disfarçado), e não está sobrecarregado com templates, embora qualquer um possa modificar o código de forma a suportá-los facilmente.

Continue reading →

Função Pseudo-Aleatoria rand() Completa

Quem já precisou gerar números aleatórios relativamente grandes em C/C++ se deparou com uma situação no mínimo frustrante.

Como uma implementação de função pseudo-aleatória gera números apenas até 32,767?

Até perceber que a função rand não gerava números com mais de 16 bits, perdi um bom tempo procurando um erro inexistente em meu programa. O pior é que este problema é específico apenas à algumas implementações da stdlib, que pude confirmar ocorrer no Visual Studio e no Mingw, que utiliza uma versão do gcc.

Para gerar números aleatórios até máximo que um inteiro (de 32 bits) agüenta, podemos utilizar o seguinte código (que gera números num intervalo fechado de i até j):

int rand_int(const int i, const int j)
{
    return i + ( ((rand() << 15) | rand()) % (j – i + 1) );
}

O que o código acima faz é gerar dois números aleatórios, deslocar um 15 bits para a esquerda (o primeiro bit em um inteiro deverá ser de sinal) e mesclar os dois num mesmo número de 32 bits. Analogamente, é possível formar números aleatórios de 32, 64, ou quantos mais bits se desejar deslocando distâncias suficientes e combinando todos números em um só.

Mais detalhes sobre implementações e aprimoramentos da função pseudo-aleatória podem ser encontrados neste site. É possível até gerar distribuições razoavelmente distribuídas com alguns truques apenas utilizando a função rand().

Outro detalhe interessante é que a sequência aleatória gerada pela função rand(), ao menos nas implementações em que testei, parece se repetir sempre a cada 2,147,483,648 chamadas. Ou seja, a função é capaz de gerar 231 (cerca de 2 bilhões) números aparentemente aleatórios até que o primeiro número seja gerado novamente e a sequência passada recomece exatamente em mesma ordem. Isto é natural de algorítmos para geração de números aleatórios pois um algorítmo é, por definição, um conjunto de passos específicos e finitos, portanto sempre possuindo uma saída previsível sem espaço para incertezas. Daí os algorítmos serem denominados, na verdade, pseudo-aleatórios, pois obedecem um conjunto de regras complexas, mas finitas, para gerar suas saídas.