Scribd
Importer
7 vues1 page

TP 1 Sur Les Arbres Rouges Et Noirs

Ce TP vise à comprendre et à implémenter un arbre binaire équilibré, l'arbre rouge et noir, qui garantit l'efficacité des opérations d'insertion, de suppression et de recherche. Les tâches incluent l'implémentation de la structure de l'arbre, l'écriture des fonctions pour l'insertion, la suppression et la recherche, ainsi que la création de tests unitaires pour valider ces opérations. Les propriétés de l'arbre doivent être maintenues à l'aide de rotations et de réorganisations de couleurs, avec une démonstration prévue le 20.11.2023.

Transféré par

Bil Na Mokoussé
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
7 vues1 page

TP 1 Sur Les Arbres Rouges Et Noirs

Ce TP vise à comprendre et à implémenter un arbre binaire équilibré, l'arbre rouge et noir, qui garantit l'efficacité des opérations d'insertion, de suppression et de recherche. Les tâches incluent l'implémentation de la structure de l'arbre, l'écriture des fonctions pour l'insertion, la suppression et la recherche, ainsi que la création de tests unitaires pour valider ces opérations. Les propriétés de l'arbre doivent être maintenues à l'aide de rotations et de réorganisations de couleurs, avec une démonstration prévue le 20.11.2023.

Transféré par

Bil Na Mokoussé
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TP 1 : Les Arbres Rouges et Noirs

L'objectif de ce TP est de comprendre et d'implémenter un arbre binaire équilibré


appelé "arbre rouge et noir". Les arbres rouges et noirs sont une structure de
données utilisée pour maintenir un équilibre dans les arbres binaires de recherche,
garantissant que les opérations d'insertion, de suppression et de recherche sont
efficaces.

Tâches à accomplir :

1. Implémentation de base :
 Implémentez la structure d’un arbre rouge et noir. Chaque nœud doit avoir
les propriétés suivantes : clé, valeur, couleur, nœud parent, nœud gauche et
nœud droit.
2. Insertion :
 Écrivez une fonction pour insérer un nœud dans l'arbre rouge et noir tout en
maintenant les propriétés de l'arbre rouge et noir.
 Assurez-vous que la propriété de couleur est respectée : aucun nœud rouge
n'a de nœuds rouges enfants, et chaque chemin de la racine à une feuille doit
avoir le même nombre de nœuds noirs.
3. Suppression :
 Écrivez une fonction pour supprimer un nœud de l'arbre rouge et noir tout en
maintenant les propriétés de l'arbre rouge et noir.
 Gérez les cas où le nœud à supprimer a 0, 1 ou 2 enfants.
4. Recherche :
 Implémentez une fonction de recherche pour trouver un nœud donné dans
l'arbre rouge et noir.
5. Tests :
 Écrivez des tests unitaires pour vous assurer que les opérations d'insertion,
de suppression et de recherche fonctionnent correctement et que les
propriétés des arbres rouges et noirs sont maintenues.

Remarque :

 Vous pouvez utiliser des rotations et des réorganisations de couleurs pour maintenir
les propriétés de l'arbre rouge et noir lors de l'insertion et de la suppression.
 Assurez-vous de vérifier les propriétés de l'arbre rouge et noir après chaque
opération pour vous assurer qu'elles sont maintenues.
 La couleur d'un nœud est généralement soit rouge (R) soit noire (N).
Le TP doit être réalisé en binômes ou individuellement.
La date de la démonstration est fixée pour 20.11.2023 durant les séances de TP.
Ce travail est noté.

Vous aimerez peut-être aussi