Contenu du cours
Aperçu des Algorithmes et des Structures de Données
Aperçu des Algorithmes et des Structures de Données
Défi : Arbres Équilibrés
Un arbre équilibré, spécifiquement un arbre de recherche binaire équilibré (BST), est une structure de données arborescente dans laquelle les hauteurs des sous-arbres gauche et droit de n'importe quel nœud diffèrent d'au plus un. Cet équilibre assure des opérations de recherche, d'insertion et de suppression efficaces, maintenant une complexité temporelle logarithmique pour ces opérations. Dans un BST équilibré, la hauteur de l'arbre est minimisée, conduisant à des performances optimales.
Regardons l'exemple d'un arbre déséquilibré :
Dans le BST fourni, le sous-arbre gauche du nœud racine a une hauteur de 4, tandis que le sous-arbre droit a une hauteur de seulement 2. Cette différence significative de hauteurs indique que l'arbre est déséquilibré, ce qui entraîne des opérations de recherche, d'insertion et de suppression inefficaces par rapport à un BST équilibré.
Swipe to start coding
On vous fournit un Arbre Binaire de Recherche (BST) implémenté en Python. Votre tâche est d'écrire une fonction pour déterminer si le BST est équilibré ou non.
Vous devez effectuer les étapes suivantes :
- calculer la hauteur d'un sous-arbre enraciné à un nœud donné de manière récursive. Elle renvoie la hauteur maximale entre les sous-arbres gauche et droit plus un (pour tenir compte du nœud actuel). Cette logique est implémentée dans la fonction
calculate_height(). - Vérifiez récursivement si le sous-arbre enraciné à un nœud donné est équilibré. Cela est implémenté en utilisant la fonction
is_balanced_recursive(). Elle compare les hauteurs des sous-arbres gauche et droit et renvoieFalsesi la différence de hauteurs est supérieure à 1, indiquant un déséquilibre. - Pour vérifier si l'arbre est équilibré, vous devez appeler
is_balanced_recursive()avec la racine de l'arbre comme argument.
Solution
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
Défi : Arbres Équilibrés
Un arbre équilibré, spécifiquement un arbre de recherche binaire équilibré (BST), est une structure de données arborescente dans laquelle les hauteurs des sous-arbres gauche et droit de n'importe quel nœud diffèrent d'au plus un. Cet équilibre assure des opérations de recherche, d'insertion et de suppression efficaces, maintenant une complexité temporelle logarithmique pour ces opérations. Dans un BST équilibré, la hauteur de l'arbre est minimisée, conduisant à des performances optimales.
Regardons l'exemple d'un arbre déséquilibré :
Dans le BST fourni, le sous-arbre gauche du nœud racine a une hauteur de 4, tandis que le sous-arbre droit a une hauteur de seulement 2. Cette différence significative de hauteurs indique que l'arbre est déséquilibré, ce qui entraîne des opérations de recherche, d'insertion et de suppression inefficaces par rapport à un BST équilibré.
Swipe to start coding
On vous fournit un Arbre Binaire de Recherche (BST) implémenté en Python. Votre tâche est d'écrire une fonction pour déterminer si le BST est équilibré ou non.
Vous devez effectuer les étapes suivantes :
- calculer la hauteur d'un sous-arbre enraciné à un nœud donné de manière récursive. Elle renvoie la hauteur maximale entre les sous-arbres gauche et droit plus un (pour tenir compte du nœud actuel). Cette logique est implémentée dans la fonction
calculate_height(). - Vérifiez récursivement si le sous-arbre enraciné à un nœud donné est équilibré. Cela est implémenté en utilisant la fonction
is_balanced_recursive(). Elle compare les hauteurs des sous-arbres gauche et droit et renvoieFalsesi la différence de hauteurs est supérieure à 1, indiquant un déséquilibre. - Pour vérifier si l'arbre est équilibré, vous devez appeler
is_balanced_recursive()avec la racine de l'arbre comme argument.
Solution
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessous