Comment faire pour supprimer un nœud avec 2 enfants de nœuds dans un arbre de recherche binaire?
Comment faire pour supprimer un nœud avec 2 enfants de nœuds dans un arbre binaire?
Est-il un genre de méthode pour l'enlever? Je l'ai googlé. Mais n'obtient pas d'idée claire à ce sujet. Quelqu'un l'expliquer avec une représentation schématique?
Vous devez vous connecter pour publier un commentaire.
vous de les remplacer nœud le plus à gauche de l'enfant sur son côté droit, ou le droit de la plupart des enfants sur son côté gauche. Vous supprimez ensuite l'enfant à partir du bas qu'il a été remplacé par.
La suppression de cinq pourrait donner un arbre avec 3 comme sa racine ou 18 comme sa racine, selon la direction que vous prenez.
Il semble que vous ayez eu cette image à partir de ce site: http://www.algolist.net/Data_structures/Binary_search_tree/Removal
Il montre l'algorithme que vous souhaitez avec des images trop.
Pour la suppression d'un Nœud, il y a trois scénarios possibles..
Avant de connaître le concept de la suppression, il faut comprendre le concept de successeurs et prédécesseurs
Successeur: Dans un arbre binaire successeur d'un nœud est le plus petit nœud de l'arbre qui est strictement supérieure à ce nœud.
Il y a deux cas de figure possibles avec un nœud
Un nœud a le droit de l'enfant: Dans ce cas, le plus à gauche de l'enfant de la droite du sous-arbre sera successeur.
Un nœud n'a pas d'enfants: Aller au nœud parent et trouver un nœud pour lequel ce nœud est la partie de gauche du sous-arbre.
Maintenant la logique de suppression de
Solution est pris de http://coder2design.com/binary-tree/
Aussi, ils ont expliqué le flux de parcours et d'insertion avec l'intégralité du code source.
Successor
Article de Wikipedia donne une bonne description de la BST:
http://en.wikipedia.org/wiki/Binary_search_tree
Lorsque vous supprimez un nœud avec 2 enfants, 5 dans votre cas, vous pouvez remplacer l'élément supprimé, avec un minimum de valeur nœud du sous-arbre droit, ou de la valeur maximale nœud du sous-arbre gauche.
Un moyen simple et facile de la solution:
Algorithme :
Java mise en œuvre :
Trouver le afinde successeur du nœud à supprimer. Puis copiez le contenu de afinde successeur du nœud et de supprimer les afinde successeur. (Vous pouvez également utiliser afinde prédécesseur la place de afinde successeur)
Une simple suppression d'un nœud qui a 2 enfants, c'est de reclassement du parent à l'enfant de l'élément supprimé avec son successeur.
Vous ne pouvez pas utiliser le nœud le plus à gauche du sous-arbre droit. Dire que vous avez un arbre et le plus à gauche du nœud du sous-arbre droit est de 15, mais le parent de 15 est également 15, remplacer le nœud à supprimer le nœud le plus à gauche sur la droite du sous-arbre peut vous donner un nœud de valeur égale dans le sous-arbre droit. Le 15 deviendrait la nouvelle racine du sous-arbre dans mon exemple, et puis il y aurait un autre 15 à droite de la racine.