Balanceamento

[Rodrigo di Lorenzo Lopes <rlopes@linux.ime.usp.br>]

Oi pessoal,
	Pode parecer falta do que fazer da minha parte, mas eu andei pensando
num outro método de balanceamento que inventei.
	Na verdade, a idéia é MUITO elementar e intuiva, por isso resolvi
analisá-la.
	Para começar seria necessário manter o controle do tamanho da subárvore
e esquerda e direita. Isto seria bem simples: bastaria adicionar dois
int na estrutura ST e fazer com que as inserções retornassem valores .
Logo, ao inserir uma folha f a esquerda de uma raiz h, inserir
retornaria 1 para h guardaria este valor em por exemplo tamanho_esq. 
	Uma vez implementado isto, vem a melhor parte... Para balancear o
seguinte algoritmo:


void balancear (link h){
while (h->tamanho_esq > (h->tamanho_dir + 1))
	rotR (h);
while (h->tamanho_dir > (h->tamanho_esq + 1))
	rotL (h);
balancear(h->l);
balancear(h->r);
}

Fácil... chega a ser estúpido. Supondo que a árvore esteja muito
desbalanceada , digamos, como uma lista ligada.
O algoritmo iria demorar no primeiro passo (N-1)% 2. 
E para cada nivel abaixo (digamos nivel j), o algoritmo levaria
(N-1)%2^j permutações, tendo 2^(j-1) subárvores na mesma situacao.
Levando ao somátio de j=1 até j= lg N de (N-1)%2^j*2^(j-1)=
lgN(N-1)%2!!!!!!!!!!!!!!!

Atenção: alterar as funções rotR e rotL para alterarem corretamente o
valores dos tamanhos das sub-árvores.

-- 
Rodrigo di Lorenzo Lopes (Mineirinho) - ICQ 52982003