Parcours dun arbre binaire
l'ordre postfixe : on liste chaque sommet la dernière fois qu'on le rencontre. Ce qui donne ici : . . . 3. l'ordre infixe : on liste chaque sommet ayant un fils
Arbres binaires
Pères et fils : le sommet 3 est le père de 7 le sommet 6 est le fils de 2. Il est d'usage de dessiner un arbre en plaçant un père au dessus de ses.
Marches permutations et arbres binaires aléatoires
Les sommets sont nu- mérotés à partir de 0 par ordre de création. On commence avec un arbre réduit à un sommet (numéroté 0). Puis
TP 8 : Arbres binaires de recherche
d'un arbre binaire de manière à lire la structure de l'arbre. si le noeud à enlever a deux fils on le remplace par le sommet de plus petite valeur dans ...
Matrice de ramification des arbres binaires*
A tout sommet d'un arbre binaire on associe son nornbre de S/r-ah/et- puis on considkre une matrice dite de ramification
Arbres
simple : il n'existe pas d'arête reliant un sommet à lui-même et deux Dans un arbre binaire strict tout nœud interne a une arité égale à 2.
Arbres binaires
Dans ce contexte il est fréquent de parler de nœud au lieu de sommet. Autre exemple
Une bijection entre binaires et certaines Jacobi arbres matrices de
Arbres binaires. Dans un arbre binaire (enracine et ordonne) tout sommet different de la racine a un ascendant. Tout sommet interne 0 a deux descendants: un
Sur le nombre de registres nécessaires à lévaluation dune
d'une expression arithmétique» sur les arbres binaires est étudiée de façon Appelons point simple d'un arbre binaire tout sommet dont un seul fils.
Algorithmique et Structures de données
On appelle arbre binaire complet un arbre binaire tel que chaque sommet interne a exac- tement 2 fils. 1. Donner des exemples d'arbres binaires complets. 2.
[PDF] Parcours dun arbre binaire
A partir de ce contour on définit trois parcours des sommets de l'arbre : 1 l'ordre préfixe : on liste chaque sommet la première fois qu'on le rencontre
[PDF] Arbres binaires
Un arbre binaire de recherche (en abrégé : ABR) permet l'implémentation sous forme d'arbre binaire de certaines structures de données stockant des éléments
[PDF] Les arbres binaires — - Pascal Delahaye
16 mai 2019 · Chaque élément de l'arbre est appelé un sommet 2 Chaque sommet renvoyant sur d'autres données (intersection) est appelé un noeud On parle
[PDF] Cours 4 : Les arbres binaires
Un arbre binaire est constitué de nœuds • Chaque nœud « pointe » vers deux nœuds de l'étage inférieur ?Version récursive • Un arbre binaire peut être
[PDF] modification Arbre et arborescence Arbres binaires Parcours
23 oct 2014 · Théorème Théorème 4 2: Il existe une bijection qui transforme un arbre planaire ayant n sommet en un arbre binaire complet ayant 2n+1 sommets
[PDF] Feuille 5 : Arbres binaires
On appelle arbre binaire complet un arbre binaire tel que chaque sommet interne a exacte- ment 2 fils 1 Donner des exemples d'arbres binaires complets 2
[PDF] TP 8 : Arbres binaires de recherche - Cedric-Cnam
d'un arbre binaire de manière à lire la structure de l'arbre si le noeud à enlever a deux fils on le remplace par le sommet de plus petite valeur dans
[PDF] Arbres binaires de recherche - CNU 27 Marseille
On parle dans ce cas d'arbre non planté puisqu'il n'y a pas de sommet particulier qui joue le rôle de racine Les sommets sont voisins les uns des autres il n
[PDF] Structures de données et algorithmes
conventionnel et il est basé sur un arbre de recherche binaire malgré qu'ils aient le même nombre de sommet (7) leurs structures sont
[PDF] Structures de données: listes piles files arbres binaires
Les arbres binaires I41 : Types de données 58 dépiler(p) p v p v / sommet sommet arbre binaire de recherche d'une valeur relativement à une
C'est quoi le sommet d'un arbre binaire ?
Le sommet de l'arbre s'appelle la racine. Un nœud qui ne poss? pas d'enfant est appelé feuille. Les nœuds autre que la racine et les feuilles sont appelés nœuds internes. Une branche est une suite de nœud consécutifs de la racine vers une feuille.Comment connaître la hauteur d'un arbre binaire ?
La taille d'un arbre binaire non vide vaut : 1 + taille(sous-arbre gauche) + taille(sous-arbre droit). La hauteur d'un arbre binaire non vide vaut : 1 + max(hauteur(sous-arbre gauche), hauteur(sous-arbre droit)).Quelle est la complexité dans le pire cas de la recherche d'un élément dans un arbre binaire de recherche de hauteur H contenant n nœuds ?
La complexité en temps dans le pire des cas de l'algorithme de recherche d'une clé dans un arbre binaire de recherche équilibré est donc O(log2(n)).- En algorithmique, la rotation d'un arbre binaire de recherche permet de changer la structure d'un arbre binaire de recherche ou ABR sans invalider l'ordre des éléments. Une telle rotation consiste en fait à faire remonter un nœud dans l'arbre et à en faire redescendre un autre.
Arbres binaires
Jean-Pierre Becirspahic
Lycée Louis-Le-Grand
2015-2016
P age1/16
lycée louis-le-grando ptioni nformatiqueDéfinition d"un arbre binaire
Théoriedesgraphes:un
arbre estungrapheconnexeacycliqueenraciné.1 2 569103
74
8 1112
Pères et fils: le sommet 3 est le père de 7, le sommet 6 est le fils de 2. Il est d"usage de dessiner un arbre en plaçant un père au dessus de ses
fils!l"orientation du graphe devient implicite.Dans ce contexte, on parle denoeudau lieu de sommet. Un noeud qui n"a
pas de fils est une f euille ou noeud ext erne,les autr essont des noeuds internes .Chaque noeud est la racine d"un arbre constitué de lui-même et de l"en- sembledesesdescendants;onparlealorsde sous-arbre del"arbreinitial.JP Becirspahic
Arbr esbinair es
2015-2016
P age2/16
lycée louis-le-grando ptioni nformatiqueDéfinition d"un arbre binaire
Théoriedesgraphes:un
arbre estungrapheconnexeacycliqueenraciné.1 2 569103
74
8 1112
Pères et fils: le sommet 3 est le père de 7, le sommet 6 est le fils de 2. Il est d"usage de dessiner un arbre en plaçant un père au dessus de ses
fils!l"orientation du graphe devient implicite.Dans ce contexte, on parle denoeudau lieu de sommet. Un noeud qui n"a
pas de fils est une f euille ou noeud ext erne,les autr essont des noeuds internes .Chaque noeud est la racine d"un arbre constitué de lui-même et de l"en- sembledesesdescendants;onparlealorsde sous-arbre del"arbreinitial.JP Becirspahic
Arbr esbinair es
2015-2016
P age2/16
lycée louis-le-grando ptioni nformatiqueDéfinition d"un arbre binaire
Théoriedesgraphes:un
arbre estungrapheconnexeacycliqueenraciné.1 2 569103
74
8 1112
Pères et fils: le sommet 3 est le père de 7, le sommet 6 est le fils de 2. Il est d"usage de dessiner un arbre en plaçant un père au dessus de ses
fils!l"orientation du graphe devient implicite.Dans ce contexte, on parle denoeudau lieu de sommet. Un noeud qui n"a
pas de fils est une f euille ou noeud ext erne,les autr essont des noeuds internes .Chaque noeud est la racine d"un arbre constitué de lui-même et de l"en- sembledesesdescendants;onparlealorsde sous-arbre del"arbreinitial.JP Becirspahic
Arbr esbinair es
2015-2016
P age2/16
lycée louis-le-grando ptioni nformatiqueDéfinition d"un arbre binaire
Théoriedesgraphes:un
arbre estungrapheconnexeacycliqueenraciné.1 2 569103
74
8 1112
Pères et fils: le sommet 3 est le père de 7, le sommet 6 est le fils de 2. Il est d"usage de dessiner un arbre en plaçant un père au dessus de ses
fils!l"orientation du graphe devient implicite.Dans ce contexte, on parle denoeudau lieu de sommet. Un noeud qui n"a
pas de fils est une f euille ou noeud ext erne,les autr essont des noeuds internes .Chaque noeud est la racine d"un arbre constitué de lui-même et de l"en- sembledesesdescendants;onparlealorsde sous-arbre del"arbreinitial.JP Becirspahic
Arbr esbinair es
2015-2016
P age2/16
lycée louis-le-grando ptioni nformatiqueDéfinition d"un arbre binaire
arité d"un noeud (ou degr ésortant) : nombr ede branches qui en part ent. arbres binaires : chaque noeud a pour arit é0, 1 ou 2. Un ensembleEétant donné, on convient que : nil est un arbre binaire surEappelé l"arbre vide; six2Eet siFgetFdsont deux arbres binaires étiquetés parE, alors A= (Fg;x;Fd)est un arbre binaire étiqueté parE.0 1 1 nilnil2 3 nilnilnil2 nil0 nilnil0 1 12 3200 1 12 32
0
JP Becirspahic
Arbr esbinair es
2015-2016
P age2/16
lycée louis-le-grando ptioni nformatiqueDéfinition d"un arbre binaire
arité d"un noeud (ou degr ésortant) : nombr ede branches qui en part ent. arbres binaires : chaque noeud a pour arit é0, 1 ou 2. Un ensembleEétant donné, on convient que : nil est un arbre binaire surEappelé l"arbre vide; six2Eet siFgetFdsont deux arbres binaires étiquetés parE, alors A= (Fg;x;Fd)est un arbre binaire étiqueté parE.0 1 1 nilnil2 3 nilnilnil2 nil0 nilnil0 1 12 3200 1 12 32
0
JP Becirspahic
Arbr esbinair es
2015-2016
P age2/16
lycée louis-le-grando ptioni nformatiqueDéfinition d"un arbre binaire
arité d"un noeud (ou degr ésortant) : nombr ede branches qui en part ent. arbres binaires : chaque noeud a pour arit é0, 1 ou 2. Un ensembleEétant donné, on convient que : nil est un arbre binaire surEappelé l"arbre vide; six2Eet siFgetFdsont deux arbres binaires étiquetés parE, alors A= (Fg;x;Fd)est un arbre binaire étiqueté parE.0 1 1 nilnil2 3 nilnilnil2 nil0 nilnil0 1 12 3200 1 12 32
0
Suivant la représentation choisie une
f euille désignera l" arbrevide ( nil) ou un noeud dont les fils gauche et droit sont vides.JP Becirspahic
Arbr esbinair es
2015-2016
P age2/16
lycée louis-le-grando ptioni nformatiqueDéfinition d"un arbre binaire
arité d"un noeud (ou degr ésortant) : nombr ede branches qui en part ent. arbres binaires : chaque noeud a pour arit é0, 1 ou 2. Un ensembleEétant donné, on convient que : nil est un arbre binaire surEappelé l"arbre vide; six2Eet siFgetFdsont deux arbres binaires étiquetés parE, alors A= (Fg;x;Fd)est un arbre binaire étiqueté parE.0 1 1 nilnil2 3 nilnilnil2 nil0 nilnil0 1 12 3200 1 12 32
0
Arbre=nil+ArbrenoeudArbretype"a arbre = Nil | Noeudof("a arbre*"a*"a arbre) ;;JP Becirspahic- Arbr esbinair es- 2015-2016 - P age2/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleSoitRune assertion définie sur l"ensembleAdes arbres étiquetés par
E. On suppose que :
R(nil)est vraie;
8x2E,8(Fg;Fd)2A2, l"implicationR(Fg)etR(Fd)=)R(Fg;x;Fd)est vraie;
Alors la propriétéR(A)est vraie pour tout arbreAdeA.De nombreuses fonctionsf:A!Fse définissent par la donnée d"un
élémenta2F, d"une fonction':FEF!Fet les relations : f(nil) =a;8x2E,8(Fg;Fd)2A2,f(Fg;x;Fd) ='(f(Fg);x;f(Fd)).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age3/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleDe nombreuses fonctionsf:A!Fse définissent par la donnée d"un élémenta2F, d"une fonction':FEF!Fet les relations : f(nil) =a;8x2E,8(Fg;Fd)2A2,f(Fg;x;Fd) ='(f(Fg);x;f(Fd)).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age3/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleDe nombreuses fonctionsf:A!Fse définissent par la donnée d"un élémenta2F, d"une fonction':FEF!Fet les relations : f(nil) =a;8x2E,8(Fg;Fd)2A2,f(Fg;x;Fd) ='(f(Fg);x;f(Fd)).
La taille jAjd"un arbreAest définie inductivement par les relations : jnilj=0; SiA= (Fg;x;Fd)alorsjAj=1+jFgj+jFdj.letrec taille =function | Nil> 0| Noeud (fg, _, fd)> 1 + taille fg + taille fd ;;jAjest le nombre de noeuds d"un arbre.JP Becirspahic- Arbr esbinair es- 2015-2016 - P age3/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleDe nombreuses fonctionsf:A!Fse définissent par la donnée d"un élémenta2F, d"une fonction':FEF!Fet les relations : f(nil) =a;8x2E,8(Fg;Fd)2A2,f(Fg;x;Fd) ='(f(Fg);x;f(Fd)).
La haut eurh(A)d"un arbreAse définit inductivement par les relations : h(nil) =1; SiA= (Fg;x;Fd)alorsh(A) =1+max(h(Fg);h(Fd)).letrec hauteur =function | Nil>1| Noeud (fg, _, fd)> 1 + max (hauteur fg) (hauteur fd) ;;h(A)est la longueur du plus long chemin entre la racine et une feuille (la
profondeur maximale d"un noeud).JP Becirspahic
Arbr esbinair es
2015-2016
P age3/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleSoitAun arbre binaire. Alorsh(A)+16jAj62h(A)+11.On raisonne par induction structurelle.
SiA=nil,jAj=0 eth(A) =1; le résultat annoncé est bien vérifié.• SiA= (Fg;x;Fd), supposons le résultat acquis pourFgetFd.jAj=1+jFgj+jFdj>1+h(Fg)+1+h(Fd)+1 >2+max(h(Fg);h(Fd)) =1+h(A)jAj=1+jFgj+jFdj62h(Fg)+1+2h(Fd)+11622max(h(Fg);h(Fd))+11=2h(A)+11JP Becirspahic- Arbr esbinair es- 2015-2016 - P age3/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleSoitAun arbre binaire. Alorsh(A)+16jAj62h(A)+11.On raisonne par induction structurelle.
SiA=nil,jAj=0 eth(A) =1; le résultat annoncé est bien vérifié.• SiA= (Fg;x;Fd), supposons le résultat acquis pourFgetFd.jAj=1+jFgj+jFdj>1+h(Fg)+1+h(Fd)+1 >2+max(h(Fg);h(Fd)) =1+h(A)jAj=1+jFgj+jFdj62h(Fg)+1+2h(Fd)+11622max(h(Fg);h(Fd))+11=2h(A)+11JP Becirspahic- Arbr esbinair es- 2015-2016 - P age3/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleSoitAun arbre binaire. Alorsh(A)+16jAj62h(A)+11.On raisonne par induction structurelle.
SiA=nil,jAj=0 eth(A) =1; le résultat annoncé est bien vérifié.• SiA= (Fg;x;Fd), supposons le résultat acquis pourFgetFd.jAj=1+jFgj+jFdj>1+h(Fg)+1+h(Fd)+1 >2+max(h(Fg);h(Fd)) =1+h(A)jAj=1+jFgj+jFdj62h(Fg)+1+2h(Fd)+11622max(h(Fg);h(Fd))+11=2h(A)+11JP Becirspahic- Arbr esbinair es- 2015-2016 - P age3/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleSoitAun arbre binaire. Alorsh(A)+16jAj62h(A)+11.On raisonne par induction structurelle.
SiA=nil,jAj=0 eth(A) =1; le résultat annoncé est bien vérifié.• SiA= (Fg;x;Fd), supposons le résultat acquis pourFgetFd.jAj=1+jFgj+jFdj>1+h(Fg)+1+h(Fd)+1 >2+max(h(Fg);h(Fd)) =1+h(A)jAj=1+jFgj+jFdj62h(Fg)+1+2h(Fd)+11622max(h(Fg);h(Fd))+11=2h(A)+11JP Becirspahic- Arbr esbinair es- 2015-2016 - P age3/16
lycée louis-le-grando ptioni nformatiqueFonctions inductives
Preuve par induction structurelleSoitAun arbre binaire. Alorsh(A)+16jAj62h(A)+11.On raisonne par induction structurelle.
SiA=nil,jAj=0 eth(A) =1; le résultat annoncé est bien vérifié.• SiA= (Fg;x;Fd), supposons le résultat acquis pourFgetFd.jAj=1+jFgj+jFdj>1+h(Fg)+1+h(Fd)+1 >2+max(h(Fg);h(Fd)) =1+h(A)jAj=1+jFgj+jFdj62h(Fg)+1+2h(Fd)+11622max(h(Fg);h(Fd))+11=2h(A)+11JP Becirspahic- Arbr esbinair es- 2015-2016 - P age3/16
lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn.
On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn.
On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).
Cas optimal:h(A) =log(jAj+1)1!arbres binairescomplets . Pour queA= (Fg;x;Fd)soit complet il faut et il suffit queFgetFdsoient complets et de même hauteur. Un arbre binaire est complet si et seulement si toutes ses feuilles sont à la même profondeur.0 1 1 402322
8 510
37
jAj=15 eth(A) =3:On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn. On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•
SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).
Certaines catégories d"arbres garantissent l"équilibrage : arbres rouge- noir, arbres AVL, etc.On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn. On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).
Le déséquilibr ed"un arbr eA= (Fg;x;Fd)est égal àh(Fg)h(Fd).Un arbre binaireAest un arbreAVLlorsqu"il est vide ou égal à(Fg;x;Fd)
avec :FgetFdsont des arbres AVL;
le déséquilibre deAest égal à1, 0 ou 1.Le déséquilibre de chaque sous-arbre est égal à1, 0 ou 1.0
0 0 001 01 10000 0 001 02
10On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn.
On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).Tout arbre AVL est équilibré.
On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn. On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).Tout arbre AVL est équilibré.
On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn. On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).Tout arbre AVL est équilibré.
On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn. On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).Tout arbre AVL est équilibré.
On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn. On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires équilibréssiAest un arbre binaire alors log(jAj+1)16h(A)6jAj1.Un arbre binaireAest ditéquilibr élorsque h(A) =O(log(jAj)).Tout arbre AVL est équilibré.
On considère la suite deFibonaccif0=0,f1=1 etfn+2=fn+1+fn. On prouve par induction structurelle que tout arbre AVLAde hauteurh contient au moinsfhnoeuds.•SiA=nil alorsjAj=0=f0.•
SiA= (Fg;x;Fd), l"un des deux sous-arbresFgouFdest de hauteur h1 donc contient au moinsfh1noeuds, l"autre est au moins de hauteurh2 donc contient au moinsfh2noeuds. DoncAcontient au moinsfh1+fh2+1=fh+1 noeuds.Sachant que'h=O(fh)avec'=1+p5 2 on en déduit :'h(A)=O(jAj), soith(A) =O(logjAj).JP Becirspahic- Arbr esbinair es- 2015-2016 - P age4/16 lycée louis-le-grando ptioni nformatiqueArbres binaires de recherche
On considère un ensemble ordonné de clésCet un ensemble de valeurs V, et on utilise des arbres binaires étiquetés parE=CV. un arbre binaireAest un arbre binaire de recherche s"il est vide ou égal à (Fg;(c;v);Fd)où :FgetFdsont des arbres binaires de recherche;
toute clé deFgest inférieure ou égale àc; toute clé deFdest supérieure ou égale àc.15 6 4 2 35713 919
17 1820
Tout noeud est associé à une clé supérieure ou égale à toute clé de son fils gauche, et inférieure ou égale à toute clé de son fils droit.
JP Becirspahic
Arbr esbinair es
2015-2016
P age5/16
lycée louis-le-grando ptioni nformatiqueArbres binaires de recherche
On considère un ensemble ordonné de clésCet un ensemble de valeurs V, et on utilise des arbres binaires étiquetés parE=CV. un arbre binaireAest un arbre binaire de recherche s"il est vide ou égal à (Fg;(c;v);Fd)où :FgetFdsont des arbres binaires de recherche;
toute clé deFgest inférieure ou égale àc; toute clé deFdest supérieure ou égale àc.Dans la suite du cours, on utilisera le type :type("a, "b) data = {Key : "a; Value : "b} ;;et les ABR seront représentés par le type("a, "b) data arbre.JP Becirspahic- Arbr esbinair es- 2015-2016 - P age5/16
quotesdbs_dbs44.pdfusesText_44[PDF] retour ? l'unité proportionnalité
[PDF] le timbre d'un son
[PDF] psychologie criminelle cours pdf
[PDF] passage ? l'acte psychologie
[PDF] cours de criminologie générale pdf
[PDF] livre criminologie pdf
[PDF] tétraèdre régulier propriétés
[PDF] passage ? l'acte
[PDF] tétraèdre propriétés
[PDF] grille d'estimation de la dangerosité d'un passage ? l'acte suicidaire pondération
[PDF] intervenir auprès de la personne suicidaire ? l'aide de bonnes pratiques
[PDF] grille estimation dangerosité suicidaire
[PDF] grille d'évaluation de l'urgence suicidaire
[PDF] rapport d'intervention auprès de la personne suicidaire
