Page d'accueil
Thèmes d'activités
<< Thème précédent
Thème suivant >>
Un
arbre binaire
est constitué de nœuds
(représentés ici par des disques gris), et de
feuilles
(représentées ici par des disques verts).
On appelle
racine
le nœud
qui est le père de tous les nœuds (ici le nœud "11").
Un nœud donne naissance à deux
descendants: un fils gauche
et un fils droite
, qui peuvent être des nœuds ou des feuilles:
par exemple le nœud "14" a pour fils gauche le nœud "13" et pour fils
droit le nœud "15".
Une feuille est un nœud qui n'a pas de fils (ici les nœuds
"5","10","13","15") .
Pour représenter un arbre binaire,
nous utiliserons une fonction non évaluée de la forme
BINARYTREE(clef, fils_gauche, fils_droite)
.
L'arbre vide, qui est un cas particulier d'arbre binaire, sera
représenté par BINARYTREE( )
.
L'arbre binaire précédent sera donc représenté par:
BINARYTREE(11,BINARYTREE(8,BINARYTREE(5,BINARYTREE(),BINARYTREE()),BINARYTREE(10,BINARYTREE(),BINARYTREE())),
BINARYTREE(14,BINARYTREE(13,BINARYTREE(),BINARYTREE()),BINARYTREE(15,BINARYTREE(),BINARYTREE())))
qui sera affiché plus simplement
sous la forme
.
Définition de l'arbre vide:
> |
emptytree:=BINARYTREE();
|
Déclaration du type correspondant
à un arbre binaire:
> |
`type/binarytree`:=proc(x)
if type( x, 'specfunc(anything,BINARYTREE)' ) then
if (nargs = 1 or x = emptytree or (
type( leftchild(x), 'binarytree'(args[2]) ) and
type( rightchild(x), 'binarytree'(args[2]) ) and
type( op(2,x),args[2]))
) then
true
else
false
end if
else
false
end if
end proc:
|
> |
`type/binarytree`(emptytree);
|
Déclaration du type correspondant
à l'arbre vide:
> |
`type/emptytree`:= e -> evalb( e = emptytree );
|
> |
`type/emptytree`(emptytree);
|
Définition des fils gauche et
droit d'un arbre binaire:
> |
leftchild:=proc(tree)
if tree = emptytree then
error "leftchild operation is invalid on an empty tree";
end if;
op(2,tree)
end proc:
|
> |
rightchild:=proc(tree)
if tree = emptytree then
error "rightchild operation is invalid on an empty tree";
end if;
op(3,tree)
end proc:
|
Procédure retournant le nombre de
fils d'un arbre:
> |
numberofchildren:=proc(tree::binarytree)
local nb;
nb:=2;
if leftchild(tree) = emptytree then nb:=nb-1 end if;
if rightchild(tree) = emptytree then nb:=nb-1 end if;
nb
end proc:
|
Fonction d'impression d'un arbre
binaire:
> |
`print/BINARYTREE`:=proc()
`if`( nargs > 0, [args], `` )
end proc:
|
> |
print(BINARYTREE(11,BINARYTREE(8,BINARYTREE(5,BINARYTREE(),BINARYTREE()),
BINARYTREE(10,BINARYTREE(),BINARYTREE())),BINARYTREE(14,BINARYTREE(13,BINARYTREE(),
BINARYTREE()),BINARYTREE(15,BINARYTREE(),BINARYTREE()))));
|
Fonctions de représentation
graphique d'un arbre binaire:
> |
with(plottools): with(plots):
|
Warning, the names arrow and changecoords have been redefined
feuille (disque vert), nœud (disque gris), branche (en noir).
> |
leafplot:=proc(x,y,r,car)
disk([x,y],r,color=green),textplot([x,y,car],font=[HELVETICA,BOLD,12])
end proc:
|
> |
nodeplot:=proc(x,y,r,car)
disk([x,y],r,color=gray),textplot([x,y,car],font=[HELVETICA,BOLD,12])
end proc:
|
> |
branchplot:=proc(x,y,dx,dy)
local r,a;
r:=dy/4: a:=arctan(dy/dx):
line([x+r*cos(a),y-r*sin(a)], [x+dx-r*cos(a),y-dy+r*sin(a)],
color=black, linestyle=1),
line([x-r*cos(a),y-r*sin(a)], [x-dx+r*cos(a),y-dy+r*sin(a)],
color=black, linestyle=1)
end proc:
|
Liste des largeurs et déplacements
relatifs utilisés en fonction du rayon r
des disques représentant les nœud
s :
> |
widthlist:=proc(r::numeric)
[r,13.5*r,19.5*r,22.5*r,25*r]
end proc:
deplist:=proc(r::numeric)
[1.5*r,3*r,6*r,12.5*r,12.51*r]
end proc:
|
> |
widthlist(10), deplist(10);
|
La procédure
drawtree utilise
les procédures précédentes pour représenter graphiquement un arbre
binaire.
> |
drawtree:=proc(tree::binarytree)
local rep,wl,h,dl,dx,w,r,P;
rep := proc(element,x,y,r,w,dx)
local d,g,h,m,w1,w2,dx1,dx2;
if element<>emptytree then
d:=rightchild(element): g:=leftchild(element):
member(dx,deplist(r),'m'):
if m>1 then dx1:=dl[m-1] else dx1:=dx end if;
if d=emptytree and g=emptytree then
P:=P,leafplot(x,y,r,op(1,element))
else
P:=P,nodeplot(x,y,r,op(1,element)),branchplot(x,y,dx1,4*r)
end if:
if g<>emptytree then
rep(g,x-dx1,y-4*r,r,w1,dx1)
end if:
if d<>emptytree then
rep(d,x+dx1,y-4*r,r,w1,dx1)
end if:
end if:
end proc:
if tree=empytree then return end if;
r:=10: wl:=widthlist(r): dl:=deplist(r): h:=height(tree):
if h>5 then w:=ls[5] else w:=wl[h] end if:
if h>5 then dx:=dl[5] else dx:=dl[h] end if:
P:=NULL:
rep(tree,0,0,r,w,dx):
display(P,scaling=constrained,axes=none);
end proc:
|
Opérations sur les arbres
binaires
Hauteur
d'un arbre (l'arbre vide a une hauteur nulle,
l'arbre-exemple a une hauteur de 3)
> |
height:=proc(tree::binarytree)
local ng,nd;
if tree = emptytree then 0
else
ng:=procname(leftchild(tree)):
nd:=procname(rightchild(tree)):
`if`(ng>nd,ng+1,nd+1)
end if
end proc:
|
Calcul de la
taille , c'est à
dire du nombre de noeuds d'un arbre:
> |
size:=proc(tree::binarytree)
if tree = emptytree then 0
else procname(leftchild(tree))+procname(rightchild(tree))+1
end if
end proc:
|
Insertion d'un nœud étiqueté par
une clef numérique key
. Deux nœuds ne peuvent avoir la même clef.
L'insertion se fait récursivement par une comparaison de la valeur de la
clef avec la valeur de la clef du nœud racine.
> |
insert:=proc(tree::binarytree, key::numeric)
if tree = emptytree then
'BINARYTREE'(key,emptytree,emptytree)
elif key > op(1,tree) then
'BINARYTREE'(op(1..2,tree),procname(rightchild(tree),key));
elif key < op(1,tree) then
'BINARYTREE'(op(1,tree),procname(leftchild(tree),key),
rightchild(tree))
else
error "duplicate keys in binary tree"
end if
end proc:
|
Création de l'arbre-exemple
tree1
par
insertion successives des clefs:
> |
tree1:=emptytree: keys:=[11,8,14,5,10,15,13]:
for key in keys do tree1:=insert(tree1,key) od:
tree1; drawtree(tree1); hauteur=height(tree1),taille=size(tree1);
|
Recherche récursive d'une clef
key
dans un arbre binaire:
> |
find:=proc(tree::binarytree, key::numeric)
if tree = emptytree then
error "key not found in binary tree"
elif key < op(1,tree) then
procname(leftchild(tree),key)
elif key > op(1,tree) then
procname(rightchild(tree),key)
else
cat(op(1,tree),` found in binary tree`)
end if
end proc:
|
|
find(tree1,12); find(tree1,13);
|
Error, (in find) key not found in binary tree
Procédure retournant le sous-arbre
dont la racine a pour clef key
:
> |
subtree:=proc(tree::binarytree, key::numeric)
if tree = emptytree then
error "key not found in binary tree"
elif key < op(1,tree) then
procname(leftchild(tree),key)
elif key > op(1,tree) then
procname(rightchild(tree),key)
else
tree
end if
end proc:
|
Suppression d'un nœud étiqueté par
une clef numérique key
.
> |
delete:=proc(tree::binarytree, key::numeric)
local child;
if tree = emptytree then
error "key not found in binary tree";
elif key < op(1,tree) then
BINARYTREE(op(1,tree),procname(leftchild(tree),key),
rightchild(tree));
elif key > op(1,tree) then
BINARYTREE(op(1..2,tree),procname(rightchild(tree),key));
elif leftchild(tree) = emptytree then
rightchild(tree);
elif rightchild(tree) = emptytree then
leftchild(tree);
else
child:= leftchild(tree);
while(rightchild(child) != emptytree) do
child:= rightchild(child);
end do;
BINARYTREE(op(1,child),
procname(leftchild(tree),op(1,child)),
rightchild(tree));
end if;
end proc:
|
Parcours en profondeur d'un
arbre binaire:
Parcours récursif préfixé: dans
le sens nœud - fils gauche - fils droit:
> |
prefixtraversal:=proc(tree::binarytree)
local path, disp;
disp:=proc(tree::binarytree)
if tree = emptytree then return end if;
path:= path, op(1,tree);
procname(leftchild(tree));
procname(rightchild(tree))
end proc;
path:=NULL;
disp(tree);
path
end proc:
|
> |
prefixtraversal(tree1);
|
Parcours récursif infixé: dans
le sens fils gauche - nœud - fils droit:
on s'aperçoit que ce parcours correspond à un tri des valeurs des clefs
dans l'ordre croissant.
> |
infixtraversal:=proc(tree::binarytree)
local path, disp;
disp:=proc(tree::binarytree)
if tree = emptytree then return end if;
procname(leftchild(tree));
path:= path, op(1,tree);
procname(rightchild(tree))
end proc;
path:=NULL;
disp(tree);
path
end proc:
|
Parcours récursif postfixé: dans
le sens fils gauche - fils droit - nœud:
> |
postfixtraversal:=proc(tree::binarytree)
local path, disp;
disp:=proc(tree::binarytree)
if tree = emptytree then return end if;
procname(leftchild(tree));
procname(rightchild(tree));
path:= path, op(1,tree)
end proc;
path:=NULL;
disp(tree);
path
end proc:
|
> |
postfixtraversal(tree1);
|
Parcours en largeur d'un arbre
binaire:
Parcours récursif (
breadth first traversal
) en largeur: on parcourt les nœuds de niveau 1
(racine "11"), ceux de niveau 2 ("8","14"), puis ceux de niveau
3
("5","10","13","15") etc... jusqu'à atteindre le niveau de la
hauteur de l'arbre:
> |
bftraversal:=proc(tree::binarytree)
local path, disp, i;
disp:=proc(tree::binarytree, currentlevel::nonnegint,
level::nonnegint)
if tree = emptytree then return end if;
if currentlevel=level then path:=path,op(1,tree)
else
procname(leftchild(tree),currentlevel+1,level);
procname(rightchild(tree),currentlevel+1,level);
end if
end proc;
path:=NULL;
if tree = emptytree then return NULL end if;
for i to height(tree) do
disp(tree,1,i)
end do;
path
end proc:
|
Arbre équilibré
( balanced tree
):
Un arbre binaire est dit équilibré
si tout nœud est équilibré, ce qui signifie que
l'écart entre les hauteurs de ses fils gauche et droit ne peut dépasser
1 en valeur absolue:
.
> |
isbalanced:=proc(tree::binarytree)
local l,r,nl,nr;
if tree = emptytree then true
else
l:=leftchild(tree): r:=rightchild(tree):
nl:= height(l): nr:=height(r):
if abs(nl-nr)>1 then return false
else
procname(l): procname(r):
end if
end if
end proc:
|
L'arbre-exemple
tree1 est
équilibré:
> |
tree2:=emptytree: keys:=[8,5,13,11,15,14,10]:
for key in keys do tree2:=insert(tree2,key) od:
tree2; drawtree(tree2); hauteur=height(tree2),taille=size(tree2);
|
L'arbre-exemple
tree2 n'est pas
équilibré (il "penche" vers la droite):
La complexité des opérations sur
un tel arbre binaire dépendant de la hauteur de l'arbre, il est
important qu'il reste aussi proche que possible d'un arbre binaire
parfait,
c'est à dire tel que
pour
tout nœud, de manière à ce que la hauteur soit minimum.
L'équilibrage d'un arbre binaire
peut-être obtenue par un algorithme faisant appel à des rotations gauche
ou droite.
> |
leftrotation:=proc(tree::binarytree)
local b,c;
b:=rightchild(tree);
c:='BINARYTREE'(op(1,tree),leftchild(tree),leftchild(b));
'BINARYTREE'(op(1,b),c,rightchild(b))
end proc:
|
> |
rightrotation:=proc(tree::binarytree)
local b,c;
b:=leftchild(tree);
c:='BINARYTREE'(op(1,tree),rightchild(b),rightchild(tree));
'BINARYTREE'(op(1,b),leftchild(b),c)
end proc:
|
La procédure d'équilibrage:
> |
balance:=proc(tree::binarytree)
local t,l,r,hl,hr;
t:=tree;
l:=leftchild(t); r:=rightchild(t);
hl:=height(l): hr:=height(r):
if hl-hr=2 then
if height(rightchild(l))<=height(leftchild(l)) then
return rightrotation(t)
else
t:='BINARYTREE'(op(1,t),leftrotation(l),r);
return rightrotation(t)
end if
elif hl-hr=-2 then
if height(rightchild(r))>=height(leftchild(r)) then
return leftrotation(t)
else
t:='BINARYTREE'(op(1,t),l,rightrotation(r));
return leftrotation(t)
end if
end if;
t
end proc:
|
Nous modifions maintenant la
procédure d'insertion de façon à ce qu'à chaque nouvelle clef insérée,
l'équilibre de l'arbre soit préservé:
> |
insertbalanced:=proc(tree::binarytree, key::numeric)
local a;
if tree = emptytree then
a:='BINARYTREE'(key,emptytree,emptytree)
elif key >= op(1,tree) then
a:='BINARYTREE'(op(1..2,tree),procname(rightchild(tree),key));
elif key < op(1,tree) then
a:='BINARYTREE'(op(1,tree),procname(leftchild(tree),key),rightchild(tree))
else
error "duplicate keys in binary tree"
end if;
balance(a)
end proc:
|
On reprend des insertions avec les
mêmes données que tree2
mais en appliquant cette fois la procédure
insertbalanced
à la place de insert
:
> |
tree3:=emptytree: keys:=[8,5,13,11,15,14,10]:
for key in keys do tree3:=insertbalanced(tree3,key):
isbalanced(tree3) od;
tree3; drawtree(tree3); |
L'arbre
tree3 obtenu est
cette fois équilibré.
Nous modifions maintenant la
procédure de suppression de façon à ce qu'à chaque nouvelle clef
supprimée, l'équilibre de l'arbre soit préservé. Pour cela, écrivons deux
procédures auxiliaires:
> |
lastchildren:=proc(tree::binarytree)
if rightchild(tree)=emptytree then return tree
else return lastchildren(rightchild(tree)) end if
end proc:
|
> |
deleteroot:=proc(tree::binarytree)
local a,b;
if leftchild(tree)=emptytree and rightchild(tree)=emptytree then
return emptytree end if;
if leftchild(tree)=emptytree then return balance(rightchild(tree))
end if;
if rightchild(tree)=emptytree then return balance(leftchild(tree))
end if;
b:=lastchildren(leftchild(tree));
a:='BINARYTREE'(op(1,b),leftchild(tree),rightchild(tree));
a:='BINARYTREE'(op(1,a),deletebalanced(leftchild(tree),op(1,a)),rightchild(a));
return balance(a)
end proc:
|
> |
deletebalanced:=proc(tree::binarytree, key::numeric)
local a;
if tree=emptytree then return tree end if;
if key=op(1,tree) then return deleteroot(tree) end if;
if key<op(1,tree) then
a:='BINARYTREE'(op(1,tree),procname(leftchild(tree),key),rightchild(tree))
else
a:='BINARYTREE'(op(1..2,tree),procname(rightchild(tree),key))
end if;
a
end proc:
|
On applique cette fois la
procédure deletebalanced
à la place de
delete :
L'équilibre de
tree3 est
préservé lors des suppressions successives des clefs.
> |
keys:=[5,11,14,10,13,8,15]:
for key in keys do tree3:=deletebalanced(tree3,key);
isbalanced(tree3); od; |
Ancêtres et niveau d'un nœud
On peut associer à chaque nœud
d'un arbre binaire un code sous forme d'une liste de 0 et de 1, de la
manière suivante:
la racine a pour code [1], ensuite dans la liste on ajoute à droite un 1
si l'on parcourt la branche gauche et 0 si l'on parcourt la branche
droite.
Si nous reprenons l'arbre tree1
, nous obtenons donc les codes [1] pour "11",
[1,1] pour "8", [1,0] pour "14", etc...jusqu'à [1,0,0] pour "15".
La procédure
keytocode
calcule récursivement le code d'une clef key :
> |
keytocode:=proc(tree::binarytree, key::numeric)
local code,c;
code:=proc(tree::binarytree, key::numeric)
if tree = emptytree then
error "key not found in binary tree"
elif key < op(1,tree) then
c:=c,1: procname(leftchild(tree),key)
elif key > op(1,tree) then
c:=c,0: procname(rightchild(tree),key)
else
c:=1,c
end if
end proc:
c:=NULL: [code(tree,key)]
end proc:
|
> |
seq(k=keytocode(tree1,k),k=[bftraversal(tree1)]);
|
La procédure
codetokey
effectue le travail inverse:
> |
codetokey:=proc(tree::binarytree, code::list)
if tree = emptytree then return
elif nops(code)=1 then op(1,tree)
else
if op(2,code)=0 then
procname(rightchild(tree),code[2..nops(code)])
else procname(leftchild(tree),code[2..nops(code)]) end if
end if
end proc:
|
> |
seq(keytocode(tree1,k)=codetokey(tree1,keytocode(tree1,k)),k=[bftraversal(tree1)]);
|
Pour trouver le nœud-parent d'un
nœud défini par sa clef key
, il suffit maintenant de calculer son code,
d'enlever l'élément le plus à droite dans cette liste,
et de calculer la clef coorespondant à cette nouvelle liste.
Par exemple, le code de "15" étant [1,0,0], on obtient la nouvelle liste
[1,0] qui est le code du nœud-parent "14" .
La racine d'un arbre binaire n'a pas de nœud-parent (résultat
FAIL
pour la
clef "11").
> |
ancestor:=proc(tree::binarytree, key::numeric)
local c;
c:=keytocode(tree,key):
if c=[1] then FAIL # key is root in binary tree"
else
codetokey(tree,c[1..nops(c)-1])
end if
end proc:
|
> |
ancestor(tree1,15), ancestor(tree1,11);
|
La procédure
level permet de
calculer le niveau auquel se situe un nœud de clef key
dans l'arbre:
> |
level:=proc(tree::binarytree, key::numeric)
local c,k,n,x;
x:=0: c:=keytocode(tree,key): n:=nops(c):
for k to n do x:=x+2^(n-k)*c[k] od;
1+trunc(log[2](x))
end proc:
|
Le nœud "11" (racine) est au
niveau 1, le nœud "8" est au niveau 2 tandis que le nœud "15" est au
niveau 3 (qui est aussi la hauteur de l'arbre):
> |
level(tree1,11),level(tree1,8),level(tree1,15);
|
Liste des nœuds de niveau donné
lv :
> |
haslevel:=proc(tree::binarytree, lv::posint)
local L,l,key;
L:=NULL:
for key in [bftraversal(tree)] do
l:=level(tree,key):
if l>lv then return [L]
elif l=lv then L:=L,key
end if
end do:
[L]
end proc:
|
Liste des nœuds de niveau 1,2,3 de
l'arbre binaire tree1
:
> |
seq(haslevel(tree1,k),k=1..height(tree1));
|
|