Comment supprimer le dernier noeud d'un tas (min-)?

Question

J'apprends pour un examen et actuellement je suis à des tas. J'ai compris comment supprimer un noeud d'un tas, mais je pourrais trouver un cas où je ne peux pas utiliser l'algorithme pour supprimer.

Le problème est que je veux supprimer 15 qui est une feuille et le dernier nœud du tas min. Lorsque vous supprimez un nœud dans un tas, vous recherchez le dernier nœud du tas, remplacez-le par le nœud de suppression et vérifiez si les enfants de ce nœud sont supérieurs à celui-ci. Continuez ensuite de manière récursive.

Pour cette raison (15 est le dernier élément et n'a pas d'enfants), je ne sais pas comment le supprimer.

 1 
    / \ 
    9  6 
/\ /
17 11 8 
/
15 

Je pense que vous pouvez simplement le supprimer sans rien faire d'autre. Vous le remplacez par lui-même puisque le nœud de suppression = dernier nœud ..? Donc, il ressemble à ça:

 1 
    / \ 
    9  6 
/\ /
17 11 8 

J'espère que vous pouvez me aider, j'ai vraiment besoin de savoir que pour mon examen et je ne pouvais pas trouver quoi que ce soit à propos de ce cas sur Internet.

Answer 1

Supprimer le dernier nœud est une tâche très simple - il suffit de l'enlever, rien à faire plus (sauf pour décrémenter le compteur et le tableau de redimensionnement si nécessaire). En général, l'échange de fonction avec lui-même ne change rien (alors que le travail est inutile), mais vous pouvez vérifier si l'élément est le dernier et omettre l'échange.

Notez que la suppression des éléments non-tête est un problème rare (vous devez fournir un accès explicite), la plupart des algorithmes utilisent uniquement l'élément le plus haut.

Notez également que votre image ne montre pas tas binaire valide, car tas est complet arbre binaire, et tous les niveaux (sauf le dernier) doit être rempli complètement, mais votre arbre a lieu vide dans la troisième rangée.