Exercices (pc 6) Corrigé

Exercice 1

function max(i,j: integer):integer;
begin
if i<j then max :=j else max:=i
end;
function hauteur(a: Arbre): integer;
begin
if a= nil then
hauteur:= 0
else
hauteur:= a^.h
end;
procedure rotD(var a: Arbre);
var b : Arbre;
begin
b:=a;
a:=a^.filsG;
b^.filsG:=a^.filsD;
a^.filsD:=b;
b^.h:=max(hauteur(b^.filsG),hauteur(b^.filsD))+1;
a^.h:=max(hauteur(a^.filsG),hauteur(a^.filsD))+1;
end;
procedure rotG(var a: Arbre);
var b: Arbre;
begin
b:= a;
a:= a^.filsD;
b^.filsD:= a^.filsG;
a^.filsG:= b;
b^.h:=max(hauteur(b^.filsG),hauteur(b^.filsD))+1;
a^.h:=max(hauteur(a^.filsG),hauteur(a^.filsD))+1;
end;

Exercice 2

procedure drotD(var a: Arbre);

begin
rotG(a^.filsG);
rotD(a);
end;
procedure drotG(var a: Arbre);
begin
rotD(a^.filsD);
rotG(a);
end;

Exercice 3

function delta(a: Arbre):integer;
begin
delta:=hauteur(a^.filsD)-hauteur(a^.filsG)
end;
procedure Reequilibre(var a: Arbre);
begin
if (delta(a)=2) and (delta(a^.filsD)>=0) then
  rotG(a)
else if (delta(a)=2) and (delta(a^.filsD))=-1) then
   drotG(a)
else if (delta(a)=-2) and (delta(a^.filsG)<=0) then
 rotD(a)
else if (delta(a)=-2) and (delta(a^.filsG)=1) then
 drotD(a)
else a^.h:=max(hauteur(a^.filsG),hauteur(a^.filsD))+1
end;
procedure Inserer(x: Element;var a: Arbre);
begin
if a=nil then a:=Nouvelarbre(x,nil,nil)
else if x< a^.contenu then begin
   Inserer(x,a^.filsG);
   Reequilibre(a)
   end
else if x> a^.contenu then begin
   Inserer(x,a^.filsD);
   Reequilibre(a)
   end
end;