Chapitre 7 : Les arbres binaires de recherche.

Introduction :

Un arbre binaire de recherche est conçu pour organiser les données de manière à faciliter les recherches. Chaque nœud a deux enfants : les valeurs plus petites vont à gauche, et les valeurs plus grandes à droite.

Cela permet de diviser rapidement l'ensemble des données et d'accélérer les recherches..

1. Définition:

A copier dans le cahier.

Un arbre binaire de recherche est un arbre binaire où pour chaque noeud, les valeurs du sous-arbre gauche sont inférieures à la valeur de ce noeud et les valeurs du sous-arbre droit sont supérieures à la valeur de ce noeud.

2. Complément :

Cette définition est volontairement ambigüe sur les inégalités, car on peut établir plusieurs règles :

Les valeurs sont distinctes et les inégalités sont strictes.
Les inégalités sont larges : les valeurs du sous-arbre gauche d'un noeud sont inférieures ou égales à la valeur de ce noeud et les valeurs du sous-arbre droit d'un noeud sont supérieures ou égales à la valeur de ce noeud.
Les valeurs du sous-arbre gauche d'un noeud sont inférieures ou égales à la valeur de ce noeud et les valeurs du sous-arbre droit d'un noeud sont strictement supérieures à la valeur de ce noeud.
Les valeurs du sous-arbre gauche d'un noeud sont strictement inférieures à la valeur de ce noeud et les valeurs du sous-arbre droit d'un noeud sont supérieures ou égales à la valeur de ce noeud.

3. Exercice :

A faire dans le cahier.

Représenter un arbre binaire de recherche dont les valeurs sont des entiers, de taille 14 et de hauteur 4 contenant des nombres entiers. (Un arbre composé que de sa racine a une hauteur de 1.)

4. Exercice :

A l'aide de la class ArbreBinaire vue dans le chapitre précédent, implémenter en Python l'arbre binaire de recherche de l'exercice précédent.

5. Exercice :

Créer une fonction recherche_valeur qui prend en paramètres un objet ArbreBinaire représentant un arbre binaire de recherche et une valeur et retourne un booléen qui vaut True si la valeur est présente dans l'arbre et False sinon.

6. Ajout d'une valeur dans un arbre binaire de recherche :

Lorsque l'on ajoute une valeur dans un arbre binaire de recherche, le noeud contenant cette valeur doit respecter les règles de l'arbre binaire de recherche.

7. Exercice :

Créer une fonction ajout_valeur qui prend en paramètres un objet ArbreBinaire représentant un arbre binaire de recherche et une valeur et ajoute cette valeur à l'arbre.

On supposera qu'il n'y a que des valeurs distinctes.

8. Exercice :

Créer une fonction crea_arbre_recherche(liste) qui prend comme paramètre une liste et qui renvoie un objet ArbreBinaire de recherche contenant ces valeurs.

9. Arbre équilibré :

Un arbre binaire est dit équilibré si pour chaque noeud de l'arbre, la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit à une différence au plus d'un.

10. Exercice :

On peut par exemple optimiser l'exercice précédent avec l'algorithme suivant :

On trie la liste.
On insère un élement central dans un arbre.
On créé une file.
On insère la sous-liste à gauche de cet élément dans la file si elle n'est pas vide.
On insère la sous-liste à droite de cet élément dans la file si elle n'est pas vide.
Tant que la file n'est pas vide :
    on sort une liste de la file.
    on insère l'élément central dans l'arbre.
    On insère la sous-liste à gauche de cet élément dans la file si elle n'est pas vide.
    On insère la sous-liste à droite de cet élément dans la file si elle n'est pas vide

Implémenter ce code en Python.

11. Recherche dans un arbre binaire équilibré :

Un algorithme de recherche dans un arbre binaire équilibré de hauteur \(n\) est en \( O(\log_2(n)) \)

12. Exercice : (sujet 25 - 2023)

Un arbre binaire est implémenté par la classe Arbre donnée ci-dessous.

Les attributs fg et fd prennent pour valeurs des instances de la classe Arbre ou None.

class Arbre:
    def __init__(self, etiquette):
        self.v = etiquette
        self.fg = None
        self.fd = None

def parcours(arbre, liste):
    if arbre != None:
        parcours(arbre.fg, liste)
        liste.append(arbre.v)
        parcours(arbre.fd, liste)
    return liste

La fonction récursive parcours renvoie la liste des étiquettes des nœuds de l’arbre implémenté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.

Compléter le code de la fonction insere qui insère un nœud d’étiquette cle en feuille de l’arbre implémenté par l’instance arbre selon la spécification indiquée et de façon que l’arbre ainsi complété soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci- dessous :

def insere(arbre, cle):
    """ arbre est une instance de la classe Arbre qui implémente
        un arbre binaire de recherche.
    """
    if ...:
        if ...:
            insere(arbre.fg, cle)
        else:
            arbre.fg = Arbre(cle)
    else:
        if ...:
            insere(arbre.fd, cle)
        else:
            arbre.fd = Arbre(cle)

13. Parcours en profondeur infixé :

Mettre dans une liste les valeurs rencontrées lors d'un parcours en profondeur infixé d'un arbre binaire de recherche produit une liste triée!