Inserção de muitas chaves em arvore binária

[marcel.mc]

Pessoal tenho de inserir as chaves (de forma crescente) de um vetor de 100.000 posições numa árvore binária. Acontece que por volta da 40.000ª inserção o programa trava e para. Acontece que se inserir as chaves (dispostas de forma randômica) do vetor de 100.000 ou mesmo 1.000.000 de posições funciona sem problemas. Todos os meus colegas estão com problemas semelhantes (os códigos são praticamente idênticos), mas meu professor insiste que não há problemas e que esse código deveria funcionar.  Não consigo entender o motivo desse problema, se alguém puder me ajudar ficarei agradecido.

 

Segue o código:

No* abCria (int val){    No *ab = NULL;    ab= (No *) (malloc(sizeof(No)));    if (ab!=NULL)    {        ab->val=val;        ab->esq=ab->dir=NULL;        return ab;    }    printf("Nao foi possivel alocar memoria");}void abInsere (int c, No** n){    if (*n==NULL)    {        No* n2=abCria(c);        *n=n2;    }    else if (c < (*n)->val)        abInsere(c, &((*n)->esq));    else if (c>(*n)->val)        abInsere(c, &((*n)->dir));    else        printf("Essa chave %d, ja foi inserida anteriormente\n\n", c);}

[RafaelCLP]

O programa dá erro em tempo de execução porque estoura a pilha da recursão.

Afinal, se você insere números de forma crescente em uma árvore binária, cada novo nó inserido é inserido como filho direito da única folha da árvore. Assim, você cria um "caminho" linear (se inseriu n nós, a altura da árvore é n-1).

Veja o que acontece a cada inserção:

a) 1 nó:1b) 2 nós:1 \  2c) 3 nós:1 \  2   \    3d) 4 nós:1 \  2   \    3     \      4E assim vai... note que à medida que você insere os nós, a altura da árvore vai ficando enorme; para inserir um nó seguinte, seu algoritmo vai rodar essa altura toda até chegar na folha e inserir.

Inserir 100.000 de nós de forma crescente em uma árvore vai tomar cerca de 2 a 20 minutos, dependendo da "eficiência" de sua implementação, ou causar erro em tempo de execução, se a pilha da recursão estourar (depende de seu computador).

Mas como assim, estourar a pilha da recursão?

Note que quando você chama uma função, todas as variáveis da função anterior ficam armazenadas, e são "recuperadas" quando você dá o return (se não ficassem armazenadas, ao dar return pra essa função você não teria mais essas variáveis, certo?). Agora, imagine você chamar uma função X(i), dentro dela chamar X(i+1), dentro desta X(i+2), etc, enquanto i<=100.000 (é basicamente o que sua inserção vai fazer). Isso significa que você vai armazenar as variáveis de 100.000 funções ao mesmo tempo em uma pilha (à medida que você for dando return vai liberando, mas até isso acontecer você já usou memória "demais" e seu programa causou erro). Não é muita memória, mas a pilha da recursão é pequena e geralmente não aguenta mais do que 50.000 recursões.

Então, você tem duas soluções:

1) Implementar a inserção iterativamente (sem recursão);

2) Não inserir os elementos de forma crescente (ponha num array, randomize, e insira OU monte uma função que consiga inserir N elementos consecutivos de forma ótima -- a ideia pra implementação é bastante similar ao mergesort).

Você poderia também optar por implementar uma árvore AVL, árvore rubro-negra (red-black) ou uma treap, a não ser que o exercício seja apenas "implementa uma árvore de busca binária"... nesse caso, você terá que seguir as outras duas soluções.

[marcel.mc]

Olá RafaelCLP, obrigado pela resposta. Inserir esses elementos dessa forma faz parte do trabalho que consiste em contar o tempo de inserçao e pesquisa de bases crescente e randômicas em árvores binárias e AVL. Ja imaginava o estouro de pilha conforme a altura crescia, você acabou confirmando. O que não entendo é porque meu professor insiste em dizer que o algoritmo funciona nessas condições e meus colegas e eu estamos tendo esse problema. Vou tentar implementar o algoritmo de forma iterativa. Até mais e muito obrigado.