structure de données partie 2 Flashcards
Propriété d’un arbre binaire de recherche
• Chaque nœud a au maximum 2 enfants,
• La clé d’un nœud est de valeur plus grande ou égale à tous les
nœuds dans le sous-arbre gauche,
• La clé d’un nœud est de valeur plus petite ou égale à tous les
nœuds dans le sous-arbre droit
Quel est Parcours en profondeur d’abord des arbres binaire de recherche
– Pré-ordre Visite le nœud, visite le sous-arbre gauche suivi du sous arbre droit. – Ordre Visite le sous-arbre gauche, explore le nœud et poursuit la visite du sous-arbre droit. – Post-ordre Visite le sous-arbre gauche, visite le sous-arbre droit avant de considérer le nœud.
quelles sont les opérations sont supportées par les
arbres binaires de recherche
- Minimum/Maximum
- Prédécesseur/Successeur
- Recherche
- Insertion/Suppression
Le temps nécessaire pour effectuer ces
opérations est proportionnel à quoi?
la hauteur de l’arbre
Définition de successeur et les 3 cas a considérés
Le successeur de x est le plus petit élément y
dont la clé est plus grand que x.
- Null si x est le nœud maximal
- Le minimum du sous-arbre droit lorsque ce
sous-arbre existe - Le plus petit ancêtre de x pour lequel l’enfant
gauche est aussi un ancêtre de x
Pour le Prédécesseur(x) qu’est ce qui change dans la méthode comparé au successeur
Minimum devient maximum
• Droit devient gauche
voir algorithme de arbre de recherche( recherche) et de insertion
dia 15 16
quel sont les 3 cas a considéré lors de la suppression et leur explication
Il y a 3 cas à considérer:
1. Le nœud z n’a pas d’enfant =Le nœud z est simplement enlevé de l’arbre
2. Le nœud z à un seul enfant= Le nœud z est remplacé par son unique enfant
3. Le nœud z à deux enfants= Il faut d’abord identifier le prédécesseur (ou successeur) y de z. y est forcément dans le sous-arbre gauche (droit) de z et a au plus un enfant (à gauche). Le nœud y prend la place de z. On traite la suppression de y à l’aide des deux règles précédentes, selon le cas.
exemple dia 21 a 26
Le temps d’accès aux éléments de l’arbre est
directement proportionnel à
la hauteur de
l’arbre.
définition et propriété de l’arbre rouge ou noir
Un arbre rouge-noir est un arbre de recherche binaire dans lequel une couleur (rouge ou noire) associée à chacun des noeuds
Propriétés:
– Un nœud est soit rouge ou soit noir.
– La racine est noire.
– Chaque feuille (nil) est noire.
– Si un nœud est rouge alors ses deux enfants sont noirs.
– Pour chaque nœud, tous les chemins reliant le nœud à des feuilles
contiennent le même nombre de nœuds noirs (hauteur-noir(x)).
Ces propriétés assurent que la hauteur de l’arbre ne sera jamais
plus de 2 * lg(n+1)
Principe générale de l’insertion dans l’arbre rouge ou noir
Principe général
1. Effectuer une recherche afin de trouver
l’emplacement de l’élément à insérer.
2. Colorier le nouveau nœud en rouge.
3. Restructurer l’arbre afin de maintenir ses
propriétés.
Cas 1: Parent du nouveau nœud est noir.
Toutes les propriétés sont maintenues!
Cas 2: Le parent du nouveau nœud est rouge et le frère du parent est noir. – Changement de couleur: • parent devient noir • Grand-parent devient rouge – Rotation droite du grand parent
Le nœud frère
est NULL, donc
noir par défaut.
quelle est la symétrie de l’insertion dans l’arbre rouge ou noir
– Même opération si les noeuds se trouve du côté droit du grandparent
– Rotation devient une rotation gauche
Cas 2b: Même situation que le cas 2 mais le nouveau nœud est inséré :
– à droite du sous arbre gauche du grand-parent
– à gauche du sous arbre droit du grand-parent
Dans ce cas, une rotation est appliquée et ça devient un cas #2
