Apprendre Maple Arbres binaires

 
  Page d'accueilPage d'accueil   RechercherRechercher   Forum de discussionForum de discussion   ContactContact   SommaireSommaire 
  Cours MapleCours Maple   Travaux dirigésTravaux dirigés   Thèmes d'activitésThèmes d'activités   Thèmes d'activitésMaplets
Ecran MapleEcran Maple  TéléchargementTéléchargement  BibliographieBibliographie  LiensLiens  

 

 

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")  .

[Maple Plot]

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 [11, [8, [5, ``, ``], [10, ``, ``]], [14, [13, ``, ``], [15, ``, ``]]] .

>    restart;

Définition de l'arbre vide:

>    emptytree:=BINARYTREE();

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);

true

Déclaration du type correspondant à l'arbre vide:

>    `type/emptytree`:= e -> evalb( e = emptytree );

`type/emptytree` := proc (e) options operator, arrow; evalb(e = emptytree) end proc

>    `type/emptytree`(emptytree);

true

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()))));

[11, [8, [5, ``, ``], [10, ``, ``]], [14, [13, ``, ``], [15, ``, ``]]]

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);

[10, 135.0, 195.0, 225.0, 250], [15.0, 30, 60, 125.0, 125.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);

[11, [8, [5, ``, ``], [10, ``, ``]], [14, [13, ``, ``], [15, ``, ``]]]

[Maple Plot]

hauteur = 3, taille = 7

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

`13 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:
 
>    s:=subtree(tree1,14);

s := [14, [13, ``, ``], [15, ``, ``]]

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:
 
>    delete(s,13);

[14, ``, [15, ``, ``]]

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);

11, 8, 5, 10, 14, 13, 15

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:  
 
>    infixtraversal(tree1);

5, 8, 10, 11, 13, 14, 15

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);

5, 10, 8, 13, 15, 14, 11

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:
 
>    bftraversal(tree1);

11, 8, 14, 5, 10, 13, 15

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: abs(hauteur(fils_gauche)-hauteur(fils_droit)) <= 1.

>    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é:

>    isbalanced(tree1);

true

>    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);

[8, [5, ``, ``], [13, [11, [10, ``, ``], ``], [15, [14, ``, ``], ``]]]

[Maple Plot]

hauteur = 4, taille = 7

L'arbre-exemple tree2  n'est pas équilibré (il "penche" vers la droite):

>    isbalanced(tree2);

false

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 hauteur(fils_gauche) = hauteur(fils_droit)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.

[Maple Plot]

>    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);  

tree3 := [8, ``, ``]

true

tree3 := [8, [5, ``, ``], ``]

true

tree3 := [8, [5, ``, ``], [13, ``, ``]]

true

tree3 := [8, [5, ``, ``], [13, [11, ``, ``], ``]]

true

tree3 := [8, [5, ``, ``], [13, [11, ``, ``], [15, ``, ``]]]

true

tree3 := [13, [8, [5, ``, ``], [11, ``, ``]], [15, [14, ``, ``], ``]]

true

tree3 := [13, [8, [5, ``, ``], [11, [10, ``, ``], ``]], [15, [14, ``, ``], ``]]

true

[13, [8, [5, ``, ``], [11, [10, ``, ``], ``]], [15, [14, ``, ``], ``]]

[Maple Plot]

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:
 
>    lastchildren(tree1);

[15, ``, ``]

>    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;  

tree3 := [13, [8, ``, [11, [10, ``, ``], ``]], [15, [14, ``, ``], ``]]

true

tree3 := [13, [8, ``, [10, ``, ``]], [15, [14, ``, ``], ``]]

true

tree3 := [13, [8, ``, [10, ``, ``]], [15, ``, ``]]

true

tree3 := [13, [8, ``, ``], [15, ``, ``]]

true

tree3 := [8, ``, [15, ``, ``]]

true

tree3 := [15, ``, ``]

true

tree3 := ``

true

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".

[Maple Plot]

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)]);

11 = [1], 8 = [1, 1], 14 = [1, 0], 5 = [1, 1, 1], 10 = [1, 1, 0], 13 = [1, 0, 1], 15 = [1, 0, 0]

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)]);

[1] = 11, [1, 1] = 8, [1, 0] = 14, [1, 1, 1] = 5, [1, 1, 0] = 10, [1, 0, 1] = 13, [1, 0, 0] = 15

 

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);

14, FAIL

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);

1, 2, 3

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));

[11], [8, 14], [5, 10, 13, 15]

 

 

haut de cette page

 

 


©  - Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.