Arbres binaires de recherche sont utilisés pour organiser les données séquentielles pour les retrouver facilement. Chaque nœud dans un arbre binaire de recherche a entre zéro et deux enfants. L'enfant gauche pour un noeud est toujours inférieur au noeud et le droit enfant est toujours plus grande. Ainsi, lorsque nous recherchons un noeud spécifique, nous pouvons comparer notre objectif au noeud courant. Si notre objectif est plus grand que le nœud actuel, nous continuons la recherche en bas de la branche de droite, si notre cible est inférieur au noeud courant nous cherchons en bas de la branche gauche. Cela fournit un avantage considérable dans la recherche par rapport à marcher à travers une liste ordonnée de ces valeurs. Suppression de nœuds d'un arbre binaire est un peu plus compliqué que l'ajout de nouveaux noeuds ou de trouver des anciens. Selon la situation, nous pourrions avoir à réorganiser l'arbre pour faire en sorte que les enfants de chaque nœud sont toujours bien équilibrée.
Instructions
Suppression d'un nœud feuille
1 Vérifiez que le noeud n'a pas d'enfants.
2 Trouver le parent du noeud. Réglez la référence enfant du parent à null.
3 Supprimez le nœud de votre baie de stockage.
Suppression d'un nœud avec un enfant
4 Vérifiez que le noeud a un seul enfant.
5 Trouver le parent du noeud. Réglez la référence de l'enfant du parent pour faire référence à l'enfant du nœud que vous supprimez.
6 Supprimez le nœud de votre baie de stockage.
Suppression d'un nœud avec deux enfants
7 Vérifiez que le noeud a deux enfants.
8 Trouver le plus grand noeud de l'arbre vers la gauche du noeud (prédécesseur). Cela peut être fait en marchant à gauche dans l'arborescence d'un pas, puis intensifient droite jusqu'à ce qu'il n'y a pas plus de références à droite.
9 Réglez le droit de référence du prédécesseur pour faire référence à l'enfant le droit du nœud que vous supprimez.
dix Remplacer la référence du nœud parent à son prédécesseur.
11 Supprimez le nœud de votre baie de stockage.
Conseils et avertissements
- suppressions multiples peuvent causer votre arbre pour devenir déséquilibré. Si vous trouvez que votre programme fonctionne lentement après de nombreuses suppressions, vous devez programmer pour équilibrer l'arbre à l'occasion.