Thème 1

Arbre binaire de recherche

ABR

A la recherche du nombre perdu

Des arbres un peu spéciaux

Dans ce chapitre on va travailler sur un type d'arbre dans lequel toutes les valeurs dans le sous-arbre gauche d'un nœud sont inférieures à la valeur à la racine de l'arbre et toutes les valeurs dans le sous-arbre droit d'un noeud sont supérieures ou égales à la valeur à la racine de l'arbre.
Rechercher le nombre 13 dans cet arbre binaire de recherche
54
26
72
13
48
66
103
Rechercher la lettre M dans cet arbre
K
H
O
A
J
M
S

Défie

Insérer la clé 43 et la clé 68 dans l'arbre suivant.

Définitions

Arbre binaire parfait

Un arbre est dit parfait si tous les niveaux sont remplis et dont toutes les feuilles sont à la même profondeur (le dernier niveau est complètement occupé).

Taille et hauteur d'un arbre parfait

On considère un arbre parfait dont h la hauteur de l'arbre et t sa taille, alors :
t = 2^{h-1} \text{ ou } h = \log_2(t) + 1

Arbre binaire complet

Un arbre binaire est complet tous les niveaux de l’arbre sont remplis, sauf éventuellement le dernier, sur lequel les nœuds (feuilles) sont à gauche.

Arbre binaire équilibré

Un arbre binaire est équilibré si tous les chemins de la racine aux feuilles ont la même longueur.

Arbre binaire dégénéré

Un arbre binaire est dégénéré si chacun de ses nœuds a au plus un fils.

Taille et hauteur d'un arbre dégénéré

On considère un arbre dégénéré dont h la hauteur de l'arbre et t sa taille, alors :
t = h

Taille et hauteur d'un arbre binaire

On considère un arbre dégénéré dont h la hauteur de l'arbre et t sa taille, alors :
\log_2(t) + 1 \leq h \leq t

Titre du popup

Message du popup !