Algo 2 séance 6 Arbres binaires de recherche (ABR (suite

NB: selon la mise en oeuvre de l’arbre binaire de recherche, on pourra interdire ou non des cl es de valeur egale Exemple 1: v eri er que l’arbre de la gure 1 est un arbre binaire de recherche: Figure 1: Arbre binaire de recherche Exemple 2: Dessiner un arbre binaire de recherche contenant les valeurs 11, 13, 14, 15, 17, 18,

ARBRES BINAIRES DE RECHERCHE

Def ´ Un arbre binaire est un arbre de recherche ssi les nœuds sont enumer´ es lors´ d’un parcours inﬁxe en ordre croissant de cles ´ Thm Soit x un nœud dans un arbre binaire de recherche Si y est un nœud dans le sous-arbre gauche de x, alors cle(y) ≤cle(x) Si y est un nœud dans le sous-arbre droit de x, alors cle(y) ≥ (x)

ARBRES BINAIRES DE RECHERCHE

Def ´ Un arbre binaire est un arbre de recherche ssi les nœuds sont enumer´ es lors´ d’un parcours inﬁxe en ordre croissant de cles ´ Thm Soit xun nœud dans un arbre binaire de recherche Si yest un nœud dans le sous-arbre gauche de x, alors cle(y) cle(x) Si yest un nœud dans le sous-arbre droit de x, alors cle(y) cle(x)

Arbres binaires de recherche

Le nombre total de noeuds d’un arbre binaire complet de h niveaux est h−1 i=0 2i =2h −1 On en d´eduit que la hauteur ht(A) (le nombre de niveaux) d’un arbre binaire A contenant n noeuds est au moins ´egale a log 2n+1 Preuve Si A est arbre de hauteur h et comportant n noeuds, pour tout entier m, on a : h ≤ m−1 ⇒ n

Arbres binaires de recherche

On a un arbre binaire de recherche déﬁni par les variables N key (clé), N parent, N left et N right (enfants gauche et droit) à tout nœud interne N; null représente un nœud externe On considère la recherche d’une clé s : ESEARCH(N,s) // recherche de s dans le sous-arbre du nœud N E1 if N = null then return null // recherche

Arbres binaires de recherche - Inria

l’arbre pass´e en argument est vide, vous l`everez une ex-ception value max tree : 0a tree →0a 2 Arbres binaires de recherche Un arbre binaire de recherche est un arbre binaire v´eriﬁant la propri´et´e suivante : Pour tout nœud ⁄(g,x,d), les ´etiquettes apparaissant dans le sous-arbre gauche g sont strictement inf´erieures `a x

ARBRE BINAIRE DE RECHERCHE - WordPresscom

Soit xun nœud interne dans un arbre binaire de recherche Si y6= xest un nœud interne dans le sous-arbre gauche de x, alors y:key x:key Preuve Le parcours inﬁxe visite les nœuds du sous-arbre gauche avant, et les nœuds du sous-arbre droit après la racine

TP 8 : Arbres binaires de recherche

en argument à l'aide d'un arbre binaire de recherche Remarque : on pourra écrire une fonction auxiliaire récursive qui, à partir d'un sous-arbre d'un ABR et d'une position dans le tableau, remplit le tableau, à partir de la position donnée, avec les aleursv contenues dans ce sous-arbre binaire et renvoie le nombre de aleursv du sous-arbre