TNSI 6 ARBRES
Principe d'arborescence
Les arbres sont une sructure de données que l'on retrouve dans beaucoup de domaines :
Cette structure est naturellement récursive et possède un vocabulaire spécifique :
taille, hauteur, feuille par exemple.
De même, pour parcourir l'arbre et trouver les informations recherchées, il y a deux approches : le parcours en largeur et le parcours en profondeur . Mais ces opérations sont coûteuses en temps de l'ordre de O(n) (voir l'exemple du labyrinthe).
Arbres binaires de recherche
Se retrouver dans un arbre est pafois difficile. Certains arbres très particuliers sont utiles pour classer une information accessible rapidement : les
arbres binaires de recherches
(ABR ou encore BST en anglais).
Pour chaque noeud de cet arbre, toutes les valeurs situées dans le sous-arbre GAUCHE sont inférieures à la valeur
du noeud, et toutes les valeurs situées dans le sous-arbre DROIT sont supérieures.
L'opération de recherche d'une valeur dans un ABR est de comlplexité O(log 2(n)).
TP d'application : Code de Huffman et le code Morse
Deux applications des arbres binaires de recherche sous forme de TP à réaliser.
Le code Huffman est un algorithme de compression de données. L’idée est d’affecter des codes de longueur
variable aux caractères d’entrée, la longueur des codes assignés étant basée sur la fréquence d’apparition
des caractères dans la séquence initiale.
Le code morse est bien connu, sa structure pour coder/décoder est un arbre.
