Algoritmo para Insercao em AVL

Prévia do material em texto

// Algoritmo para Inserção em AVL 
// Insere um nó contendo a chave x na árvore apontada por p. 
// h verdadeiro se, e somente se, a altura da árvore com raiz p foi (alterada) aumentada com a inserção 
InsereAVL(x, p, h) 
 se p = NULO 
 então 
 InsereNo(p,x); 
 h  verdadeiro; 
 senão se x < Info(p) 
 então 
 InsereAVL(x, Eprox(p), h); 
 se h 
 então // a sub-árvore à esquerda de p foi alterada 
 caso Bal(p) seja 
 1: Bal(p)  0; 
 h  falso; 
 0: Bal(p)  -1; 
 -1: RotacaoDireita(p, h); 
 fimCaso 
 fimSe 
 senão se x > Info(p) 
 então 
 InsereAVL(x, Dprox(p), h); 
 se h 
 então // a sub-árvore à direita de p foi alterada 
 caso Bal(p) seja 
 -1: Bal(p)  0; 
 h  falso; 
 0: Bal(p)  1; 
 1: RotacaoEsquerda(p, h); 
 fimCaso 
 fimSe 
 fimSe 
 fimSe 
 fimSe 
fimInsereAVL 
 
InsereNo(p, x) 
 p  Aloca(); 
 Info(p)  x; 
 Eprox(p)  NULO; 
 Dprox(p)  NULO; 
 Bal(p)  0; 
fimInsereNo 
 
RotacaoDireita(p, h) // caso 1 
 u  Eprox(p); 
 se Bal(u) = -1 
 então // caso 1.1 - rotação a direita 
 Eprox(p)  Dprox(u); 
 Dprox(u)  p; 
 Bal(p)  0; 
 p  u ; 
 senão // caso 1.2 - Bal(u) = 1, rotação dupla-direita 
 v  Dprox(u); 
 Dprox(u)  Eprox(v); 
 Eprox(v)  u; 
 Eprox(p)  Dprox(v); 
 Dprox(v)  p; 
 se Bal(v) = 0 
 então 
 Bal(u)  0; 
 Bal(p)  0; 
 senão se Bal(v) = -1 
 então 
 Bal(u)  0; 
 Bal(p)  1; 
 senão 
 Bal(u)  -1; 
 Bal(p)  0; 
 fimSe 
 fimSe 
 p  v; 
 fimSe 
 Bal(p)  0; 
 h  falso; 
fimRotacaoDireita 
 
RotacaoEsquerda(p, h) // caso 2: hd(p) - he(p) = 2 
 z  Dprox(p); 
 se Bal(z) = 1 
 então //caso 2.1 - rotação à esquerda 
 Dprox(p)  Eprox(z); 
 Eprox(z)  p; 
 Bal(p)  0; 
 p  z; 
 senão // caso 2.2, Bal(z) = -1: rotação dupla à esquerda 
 y  Eprox(z); 
 Eprox(z)  Dprox(y); 
 Dprox(y)  z; 
 Dprox(p)  Eprox(y); 
 Eprox(y)  p; 
 se Bal(y) = 1 
 então 
 Bal(p)  -1; 
 Bal(z)  0; 
 senão se Bal(y) = 0 
 então 
 Bal(p)  0; 
 Bal(z)  0; 
 senão 
 Bal(p)  0; 
 Bal(z)  1; 
 fimSe 
 fimSe 
 p  y; 
 fimSe 
 Bal(p)  0; 
 h  falso; 
fimRotacaoEsquerda