Question 202

Comment réaliser et utiliser un arbre binaire ?

Les arbres binaires (en anglais, binary trees) permettent une organisation hiérarchique des données. Ceci leur confère souvent un avantage dans un parcours à la recherche d'une donnée, en comparaison de simple vecteurs. D'autre part, de très nombreux problèmes se prêtent bien à être vus comme des problèmes d'arbres. Les problèmes présentant naturellement une structure hiérarchique (pyramide d'une entreprise, arbres syntaxiques abstraits d'un compilateur, arborescence de fichiers), la réalisation de tris. Ceci fait la relative popularité de cette structure de données dans un grand nombre de cas.

Structure d'un arbre binaire

Un arbre binaire est constitué d'un ensemble de noeuds. Chaque noeud possède une référence vers au plus deux autres noeuds. Ces noeuds sont appelés noeuds enfants et sont souvent distingués en tant que fils gauche et fils droit. Chaque noeud contient de plus une donnée à conserver et optionnellement une référence vers son noeud parent.

Un noeud particulier est le noeud dit racine de l'arbre. C'est le seul noeud à ne pas avoir de parent.

Décrire l'arbre revient à en connaître le noeud racine. L'ensemble des référents vers les noeuds fils permet ainsi d'accéder, à partir de la racine, à tout noeud de l'arbre.

Les notions suivantes sont fréquemment utilisées :

• La profondeur d'un noeud est sa distance à la racine
• La hauteur de l'arbre est la taille du chemin le plus long qu'il est possible de parcourir dans l'arbre
• Les frères (en anglais, Siblings) d'un noeud sont l'ensemble des noeuds possédant le même parent.
• Un noeud ne possédant pas de fils est appelé feuille.

Les noeuds peuvent être décrits de manière différente. On utilisera généralement soit un système de référents offerts par l'utilisation d'objets au travers des instructions New et Set, ou alors un vecteur de types définis dont les indices serviront de référents.

Variantes

Les arbres binaires de recherche (encore appelés arbres binaires de fouille ou arbre binaires ordonnés) sont des arbres binaires tels que la valeur associée à un noeud parent est supérieure à toute valeur présente dans sa branche gauche et inférieure à toute valeur présente dans sa branche droite. Ces arbres sont, de par leur nature, toujours triés. L'insertion et la suppression d'un noeud dans un tel arbre est rapide, ce qui en fait une structure utile pour conserver triée une liste dynamique de données.

L'arbre binaire n'est en réalité qu'une particularisation d'un arbre n-aire. Un arbre n-aire contient des noeuds possédant au plus n noeuds fils.

Réalisation

L'implémentation suivante d'un arbre binaire utilise un vecteur comme structure de données sous-jacente. Data est choisi de type Long. Il est bien entendu possible d'implémenter la même structure pour stocker tout autre type de données. Les méthodes sont les suivantes :

• SetValue(Node, Data) : Définit la donnée (Data) associée au noeud Node
• GetValue(Node) : Retrouve la donnée associée au noeud Node
• SetLeft(Node, Data) : Associe au noeud Node un fils gauche possédant la donnée Data
• SetRight(Node, Data) : Associe au noeud Node un fils droit possédant la donnée Data
• ClearLeft(Node) : Supprime le fils gauche du noeud Node
• ClearRight(Node) : Supprime le fils droit du noeud Node
• GetLeft(Node) : Retrouve le fils gauche du noeud Node
• GetRight(Node) : Retrouve le fils gauche du noeud Node

Les points importants afin de comprendre l'implémentation sont les suivants :

• la présence du type utilisateur Node, permettant de décrire un noeud de l'arbre
• la suppression récursive des noeuds par ClearNode  des méthodes récursives sont très souvent utilisées pour réaliser des opérations sur des arbres
• la gestion des descendants et en particulier l'utilisation de NODE_INVALIDREF lorsque ceux-ci sont indéfinis

Le module de classe BinaryTree réalise un arbre binaire :

Option Explicit

'Décrit un noeud de l'arbre
Private Type Node
    Left As Long                                'Fils gauche
    Right As Long                               'Fils droit
    Value As Long                               'Valeur associée au noeud
    InUse As Boolean                            'Est-ce réellement un noeud, ou un espace libre?
End Type

Private Const MAX_NODES As Long = 1024          'Nombre maximal de noeuds dans l'arbre
Private Const NODE_INVALIDREF As Long = -1      'Descendant inexistant (associé à Left ou Right dans la structure Node)

Private mNextFreeNode As Long                   'Emplacement libre suivant dans le vecteur
Private mNodes(MAX_NODES) As Node               'Vecteur contenant les noeuds de l'arbre

Private Sub Class_Initialize()
    'Crée la racine de l'arbre
    CreateNode 0
End Sub

Private Sub Class_Terminate()
    'Détruit les données
    Erase mNodes
End Sub

'Associe à mNextFreeNode le prochain noeud libre
Private Sub GetNextFreeNode()
    Dim i As Long
    Dim TempValue As Long
    
    TempValue = -1
    
    'Parcours le reste de la liste à partir du noeud libre courant
    'a la recherche d'un noeud libre
    For i = mNextFreeNode To MAX_NODES
        If mNodes(i).InUse = False Then
            TempValue = i
            Exit For
        End If
    Next
    
    mNextFreeNode = TempValue
End Sub

'Supprime le noeud Node et ses descendants
Private Sub ClearNode(Node As Long)
    If (Node <> NODE_INVALIDREF) Then
        'Détruit les descendants
        ClearNode (mNodes(Node).Left)
        ClearNode (mNodes(Node).Right)
        
        'Libère le noeud qu'on est occupé de traiter
        mNodes(Node).InUse = False
        
        'Le marque éventuellement pour réutilisation
        If (mNextFreeNode > Node) Then
            mNextFreeNode = Node
        End If
    End If
End Sub

'Crée un noeud avec une valeur associée Value
'Renvoie sa position
Private Function CreateNode(Value As Long) As Long
    'Définit un nouveau noeud à la position mNextFreeNode
    
    'S'il n'y a plus de position libre, l'indique
    If (mNextFreeNode = -1) Then
        Err.Raise 7
    End If

    mNodes(mNextFreeNode).Value = Value
    mNodes(mNextFreeNode).Left = NODE_INVALIDREF
    mNodes(mNextFreeNode).Right = NODE_INVALIDREF
    mNodes(mNextFreeNode).InUse = True
    
    CreateNode = mNextFreeNode
    GetNextFreeNode
End Function

'Retrouve la valeur associée au noeud à la position Node
Public Function GetValue(Node As Long) As Long
    GetValue = mNodes(Node).Value
End Function

'Définit la valeur associée au noeud à la position Node
Public Function SetValue(Node As Long, Value As Long)
    mNodes(Node).Value = Value
End Function

'Retrouve la position du descendant gauche associé au noeud de position Node
Public Function GetLeft(Node As Long) As Long
    GetLeft = mNodes(Node).Left
End Function

'Attribue un descendant gauche, de valeur Value, au noeud de position Node
Public Function SetLeft(Node As Long, Value As Long) As Long
    SetLeft = CreateNode(Value)

    'Supprime le fils gauche actuel
    ClearLeft Node
    
    'Et le remplace
    mNodes(Node).Left = SetLeft
End Function

'Supprime le descendant gauche du noeud Node
Public Sub ClearLeft(Node As Long)
    'Supprime le fils gauche
    ClearNode mNodes(Node).Left
    mNodes(Node).Left = NODE_INVALIDREF
End Sub

'Retrouve la position du descendant droit associé au noeud de position Node
Public Function GetRight(Node As Long) As Long
    GetRight = mNodes(Node).Right
End Function

'Attribue un descendant droit, de valeur Value, au noeud de position Node
Public Function SetRight(Node As Long, Value As Long) As Long
    SetRight = CreateNode(Value)

    'Supprime le fils gauche actuel
    ClearNode (mNodes(Node).Right)
    
    'Et le remplace
    mNodes(Node).Right = SetRight
End Function

'Supprime le descendant droit du noeud Node
Public Sub ClearRight(Node As Long)
    'Supprime le fils droite
    ClearNode mNodes(Node).Right
    mNodes(Node).Right = NODE_INVALIDREF
End Sub

La fonction suivante présente un exemple d'utilisation :

Option Explicit

Private Sub Form_Load()
    Dim Tree As BinaryTree
    Dim NewNode As Long
    Set Tree = New BinaryTree
    
    'Ajoute des noeuds pour construire l'arbre suivant
    '  0 +> 1 -> 2 +> 3
    '    |         +> 4 -> 5
    '    +> 6 +> 7
    '         +> 8
    Tree.SetValue 0, 0
    
    'Branche de droite (6,7,8)
    NewNode = Tree.SetRight(0, 6)
    Tree.SetLeft NewNode, 7
    Tree.SetRight NewNode, 8
    
    'Noeud 1
    NewNode = Tree.SetLeft(0, 3)    'oups, pas la bonne valeur
    Tree.SetValue NewNode, 1
    
    'Noeud 2
    Tree.SetRight NewNode, 2 'oups, c'était pas à droite
    Tree.ClearRight NewNode
    NewNode = Tree.SetLeft(NewNode, 2)
    
    'Noeuds 3,4,5
    Tree.SetLeft NewNode, 3
    NewNode = Tree.SetRight(NewNode, 4)
    Tree.SetLeft NewNode, 5
    
    'Affiche l'arbre
    ShowTree Tree
End Sub

Private Sub ShowTree(Tree As BinaryTree, Optional Node As Long = 0, Optional Level As Long = 0)
    Dim i As Long

    If Level >= 0 And Node >= 0 Then
        'Parcours l'arbre en affichant d'abord le noeud courant et ensuite les enfants
        '   Ce type de parcours est appelé préfixe
        'On peut aussi parcourir l'arbre en notant le noeud courant
        '   Entre les deux enfants (infix)
        '   Après les deux enfants (postfix)
        'Ces autres parcours ont d'autres applications
        For i = 1 To Level - 1
            Debug.Print "|",
        Next i
        
        If (Level > 0) Then
            Debug.Print "+-----------";
        End If
        Debug.Print Tree.GetValue(Node)
        ShowTree Tree, Tree.GetLeft(Node), Level + 1
        ShowTree Tree, Tree.GetRight(Node), Level + 1
    End If
End Sub

Pour aller plus loin

• Arbre binaire sur wikipedia
• Arbre binaire de recherche sur wikipedia
• Binary tree (data structure) sur le site du NIST (en)

Voir aussi :

• Comment implémenter et utiliser les structures de données classiques ?
• Comment trier des données en VB ? Quelles sont les différentes méthodes de tri ?