3.3.1. Operación de inserción en un AVL.

type

Arbol_avl = ^nodo_avl;

Nodo_avl = record

elemento: Tipo_elemento;

izq: Arbol_avl;

der: Arbol_avl;

altura: integer;

end;

function Altura (p: Arbol_avl): integer;

begin

if p = nil then

return -1

else

return p^.altura;

end;

procedure Insertar (x: Tipo_elemento; var A: Arbol_avl);

begin

if A = nil then begin

new (A);

A^.elemento:= x;

A^.izq:= nil;

A^.der:= nil;

A^.altura:= 0;

end

else if x < A^.elemento then begin

insertar(x, A^.izq);

if Altura(A^.izq)-Altura(A^.der)=2 then

if x < A^.izq^.elemento then

Rotar_simple_izq (A) { CASO II }

else

Rotar_doble_izq (A) { CASO ID }

else

A^.altura:= 1+ max (Altura (A^.izq),

Altura (A^.der));

end

else if x > A^.elemento then begin

{ Caso simétrico para el subárbol derecho }

end;

end; { Si x=A^.elemento, no hacer nada }

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica