Arbre Binaire

Comprendre les arbres binaires

Pour commencer ce voyage dans le domaine de l'informatique, voyons d'abord ce qu'est un arbre binaire - une structure de données fondamentale utilisée pour des applications informatiques telles que les algorithmes de traitement d'images et les recherches efficaces.

Propriétés essentielles de l'arbre binaire

• Racine : Le nœud le plus haut de l'arbre.
• Enfant : Tout nœud, à l'exclusion de la racine, connecté vers le haut par une arête.
• Parent : Pour tout nœud " enfant ", le nœud connecté au-dessus de lui, plus proche de la racine.
• Feuille : Un nœud sans enfant.
• Sous-arbre : Tout nœud peut être considéré comme la racine, avec ses enfants, d'un sous-arbre.
• Visiter : Exécuter une certaine forme d'opération, c'est-à-dire imprimer, calculer une fonction au niveau du nœud.
• Traverser : Visiter les nœuds dans un certain ordre.
• Niveaux : les niveaux sont numérotés de la racine vers le bas. La racine se trouve au niveau 1.

Explication de la structure de l'arbre binaire

• Arbre binaire complet : Ce type comprend un arbre où chaque nœud a soit zéro, soit deux enfants.
• Arbrebinaire complet : dans ce type d'arbre, tous les niveaux sont complètement remplis, sauf éventuellement le dernier niveau qui est rempli de gauche à droite.

Plongée dans la recherche d'arbre binaire

La recherche par arbre binaire est un algorithme informatique classique utilisé pour localiser une valeur spécifique dans un arbre binaire. L'algorithme fonctionne selon le principe que pour chaque nœud, tous les éléments de son sous-arbre gauche sont inférieurs au nœud, et tous les éléments du sous-arbre droit sont supérieurs au nœud. La recherche par arbre binaire fonctionne en divisant efficacement l'espace de recherche par deux à chaque étape, en le redéfinissant vers le sous-arbre gauche ou droit, en fonction de la comparaison.

Implémentation de la recherche dans l'arbre binaire

Recherche dans un arbre binaire en Python

Voici un extrait de code Python montrant la mise en œuvre de la recherche par arbre binaire :

classe  Node: 
def  __init__(self, key) : 
self.left = None self.right = None self.val = keydef search(root, key) : 
# Cas de base : root est null ou key est présent à root si root est None ou root.val == key : 
return root # La clé est plus grande que la clé de la racine if root.val < key :        
return search(root.right, key) # La clé est plus petite que la clé de la racine return search(root.left, key)

Dans l'extrait ci-dessus, une classe Node est créée et l'opération de recherche BST est implémentée sous la forme d'une fonction qui prend deux paramètres - 'root' et 'key'. La fonction teste si la clé du nœud actuellement exploré correspond à la clé recherchée. En cas de correspondance, elle renvoie le nœud.

Si la clé recherchée est plus grande, la fonction est appelée récursivement sur le sous-arbre de droite, et sinon, sur le sous-arbre de gauche. Si l'espace de recherche est épuisé (c'est-à-dire qu'un sous-arbre vide est atteint), "Aucun" est renvoyé, ce qui signifie que la clé n'a pas été trouvée dans l'arbre.

Exploration d'exemples d'arbres binaires

• Systèmes de recherche : L'une des applications les plus répandues des arbres binaires est celle des systèmes de recherche. Par exemple, dans un dictionnaire en ligne, la recherche par arbre binaire permet à un utilisateur de trouver un mot beaucoup plus rapidement que la recherche linéaire.
• Arbres de décision : Les arbres de décision, un outil populaire dans l'analyse des décisions, sont également un type d'arbre binaire. Chaque nœud représente une décision, et la structure de l'arbre permet un examen complet du résultat de chaque chemin de décision.
• Algorithmes de tri : Les arbres binaires sont également utilisés dans les algorithmes de tri comme le heapsort qui sont plus efficaces que le tri par bulle, le tri par insertion et le tri par sélection.

Exemples d'arbres binaires en informatique

• Hiérarchie du système de fichiers : Le système de fichiers des systèmes informatiques est structuré sous la forme d'un arbre binaire. Chaque dossier (répertoire) et chaque fichier est un nœud de l'arborescence. La propriété hiérarchique de l'arbre binaire convient naturellement à cette tâche, étant donné la hiérarchie inhérente aux systèmes de fichiers.
• Analyse des expressions : L'analyse des expressions, un aspect crucial de la conception des compilateurs, utilise l'arbre binaire. L'expression est représentée sous la forme d'une structure d'arbre binaire, ce qui permet au compilateur d'évaluer facilement l'expression.
• Routage des données de réseau : Les routeurs de réseau utilisent un arbre de partitionnement de l'espace binaire pour accélérer l'accès aux données et favoriser un routage efficace dans la colonne vertébrale du réseau.

Guide de l'inversion des arbres binaires

Qu'est-ce qu'un arbre binaire inversé ?

Comment inverser un arbre binaire

1. Intervertir l'enfant gauche et l'enfant droit du nœud racine.
2. Inverser récursivement les sous-arbres enracinés dans les enfants de gauche et de droite qui viennent d'être échangés.

Inversion d'un arbre binaire en Python

classe  Nœud: 
def  __init__(self, key) : 
self.left = None self.right = None self.val = keydef invert(node) : 
si node est None: 
return# Échange les nœuds enfants gauche et droit temp = node.left node.left= node.right node.right = temp # Appel récursif sur les sous-arbres invert(node.left) invert(node.right)

Maîtriser l'arbre binaire équilibré

Un arbre binaire équilibré est un type particulier d'arbre binaire qui est profondément ancré dans l'informatique en raison de ses propriétés uniques et utiles. L'attribut principal qui définit un arbre binaire équilibré est le fait que la hauteur des sous-arbres gauche et droit de chaque nœud diffère d'au plus 1.

Cette condition d'équilibre idéale garantit des performances optimales lors d'opérations telles que l'insertion, la suppression et la recherche. C'est pourquoi les arbres binaires équilibrés sont largement utilisés dans diverses structures de recherche de données telles que les arbres AVL, les arbres rouge-noir et les arbres B.

Équilibrer un arbre binaire : Un aperçu

• Rotation gauche : Effectuée lorsque le sous-arbre droit d'un nœud est plus lourd (plus élevé).
• Rotation droite : Effectuée lorsque le sous-arbre gauche d'un nœud est plus lourd.
• Rotation gauche-droite : Une combinaison de rotation à gauche suivie d'une rotation à droite. Effectuée lorsque le sous-arbre gauche est plus lourd et que son enfant droit contient le déséquilibre.
• Rotation droite-gauche : Une combinaison de rotation à droite suivie d'une rotation à gauche. Elle est effectuée lorsque le sous-arbre de droite est plus lourd et que son enfant de gauche contient le déséquilibre.

Équilibrer les arbres binaires en Python

Voici un petit extrait de code Python qui illustre cette méthode :

classe  Node: 
def  __init__(self, key, height=1) : 
self.left = None self.right = None self.val = key self.height = height # hauteur du nœud ajouté
def insert(node, key) :#...code d'insertion... # Mise à jour de la hauteur du nœud node.height = 1 + max(getHeight(node.left), getHeight(node.right))    
# Obtenir l'équilibre pour vérifier si l'arbre est devenu déséquilibré balance = getBalance(node) # Effectuer des rotations (4 cas) # ...code de rotation...

Dans le code susmentionné, une classe Node a été définie et dotée d'un attribut supplémentaire - height, qui stocke la hauteur du noeud.

Après chaque opération d'insertion, la hauteur du noeud est mise à jour et l'équilibre est vérifié. Si l'équilibre est supérieur à 1, des rotations appropriées sont effectuées selon que le déséquilibre se situe dans les sous-arbres gauche, droit, gauche-droit ou droite-gauche. Ce processus itératif garantit que l'arbre binaire reste toujours équilibré.

Implémentation de l'arbre binaire en Python

classe  Nœud: 
def  __init__(self, data) : 
self.left = None self.right = None self.data = dat

def insert(root, data) :if root is None:return Node(data)else:if data < root.data :root.left = insert(root.left, data)else: 
root.right = insert(root.right, data)return roo

def inOrderTraversal(root) :if root : 
inOrderTraversal(root.left) print(root.data) inOrderTraversal(root.right)

Arbre binaire Python : Étapes simples pour commencer

1. Crée une classe Node : Chaque nœud de l'arbre binaire sera une instance de cette classe, contenant un attribut 'data' et deux nœuds 'left' et 'right' représentant respectivement les enfants de gauche et de droite.
2. Conçois la fonction 'insert' : Cette fonction prend la racine d'un arbre binaire et des données. Elle insère les données dans l'arbre binaire dont la racine est 'root', en respectant la propriété de l'arbre de recherche binaire, et renvoie la racine.
3. Crée une fonction 'traversal' : Cette fonction imprime les données des nœuds dans différents ordres. La fonction prend une racine, parcourt l'arbre binaire dont la racine est 'racine' dans l'ordre (gauche --> racine --> droite), avant l'ordre (racine --> gauche --> droite), ou après l'ordre (gauche --> droite --> racine), et imprime les données.

Manipuler des données d'arbres binaires avec Python

Une fois que tu as compris la mise en œuvre de base de l'arbre binaire, tu as accès à un grand nombre d'opérations et de manipulations des arbres binaires. Qu'il s'agisse d'équilibrer, de faire pivoter ou de refléter l'arbre binaire, tu peux tout faire. Pour que l'arbre binaire reste une structure de données efficace et ordonnée, nous devons nous assurer que l'arbre reste équilibré, principalement lorsque nous ajoutons ou supprimons des nœuds. Python fournit plusieurs fonctions intégrées pour simplifier ces tâches.

Nous avons discuté en détail de l'équilibrage et de la rotation des arbres binaires dans les sections précédentes. La clé est de s'assurer que la différence maximale entre la hauteur des sous-arbres gauche et droit de n'importe quel nœud est de un. Le respect de cette règle maintiendra l'équilibre de l'arbre et optimisera la complexité temporelle des opérations de recherche, d'insertion et de suppression à \(O(log(n))\N). Pour refléter ou inverser un arbre binaire, la simplicité de Python entre à nouveau en jeu.

Voici une façon simple d'inverser un arbre binaire :

def invert(root) : 
if root : 
root.left, root.right = root.right, root.left invert(root.left) invert(root.right) return root

Dans cette fonction Python, à chaque nœud rencontré, ses enfants de gauche et de droite sont échangés. La fonction inverse ensuite de façon récursive les sous-arbres de gauche et de droite. On ne peut pas faire plus simple, n'est-ce pas ?