Discussion :

[_iri_]

Bonjour,

J'ai besoin de créer une API spécifique pour des ABR. L'ensemble fournit les résultats escomptés à l'exception de la suppression d'un nœud.
En effet, le nœud est supprimé et l'arbre réorganisé SAUF si le nœud demandé est le nœud racine, auquel cas je rentre dans une boucle infinie.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
typedef struct btree
{
    int key;
    struct btree *left;
    struct btree *right;
} *btree;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
static btree _btremove (btree tree, int key)
{
    btree node = tree, *father = &tree;
    btree newnode, *newfather;
    while (node != NULL)
    {
        if (key == node->key)
            break;
        if (key < node->key)
        {
            father = &node->left;
            node = node->left;
        }
        else
        {
            father = &node->right;
            node = node->right;
        }
    }
    if (node != NULL)
    { 
        if (node->left == NULL)
        {
            if (node->right == NULL)
            {
                *father = NULL;
                free (node);
                node = NULL;
            }
            else /* node->right != NULL */
            {
                *father = node->right;
                free (node);
                node = NULL;
            }
        }
        else /* node->left != NULL */
        {
            if (node->right == NULL)
            {
                *father = node->left;
                free (node);
                node = NULL;
            }
            else /* node->right != NULL */
            /* we search the smaller value in the right tree */
            {
                newnode = node->right;
                newfather = &node->right;
                while (newnode != NULL)
                { 
/* Si le nœud demandé est la racine, boucle infinie ici ! */
                    if (newnode->left != NULL)
                    {
                        newfather = &newnode->left;
                        newnode = newnode->left; 
                    }
                }
                node->key = newnode->key;
                *newfather = newnode->right;
                free (newnode);
                newnode = NULL;
            }
        }
    }
    return tree;
}

La boucle infinie est signalée par un commentaire.
Je ne comprends pas pourquoi le nœud à cet endroit est une fuille.
Pouvez-vous m'éclairer ?
Pb d'algo ?

[Médinoc]

Peut-être devrais-tu le récupérer avant de faire la modification.
Et aussi, séparer ta fonction un peu plus (notamment isoler les phases de recherche).

Edit:
Comme plan, je proposerais:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*Retourne un pointeur vers le pointeur vers le nœud qu'on cherche*/
btree* FindPtrToNode(btree *ppRoot, int key)
{
	btree *ppCurrent = ppRoot;
	if(ppCurrent==NULL)
		return NULL;
	while(*ppCurrent != NULL)
	{
		if((*ppCurrent)->key == key)
			break;
		else if((*ppCurrent)->key < key)
			ppCurrent = &( (*ppCurrent)->left );
		else
			ppCurrent = &( (*ppCurrent)->right );
	}
	return ppCurrent;
}
 
/*Retourne un pointeur sur le pointeur du fils le plus à gauche*/
btree* FindPtrLeftmost(btree* ppNode)
{
	btree* ppPrevious = ppNode;
	if(ppNode==NULL)
		return NULL;
	while(*ppNode != NULL)
	{
		ppPrevious = ppNode;
		ppNode = &( (*ppNode)->left );
	}
	return ppPrevious;
}
 
void Remove(btree *ppNode)
{
	/*Algorithme de suppression qui aura besoin de FindPtrLeftmost().*/
}
 
void FindAndRemove(btree *ppRoot, int key)
{
	btree* ppDelete = FindPtrToNode(ppRoot, key);
	Remove(ppDelete);
}

[Metalman]

Ce qui est étonnant, c'est justement la phase de recherche : tu cherches à atteindre une feuille : while (node != NULL)... donc nécessairement tu ne modifieras jamais la racine ni les noeuds dans les branches...

EDIT : Oui avec un break tu sors de la boucle.... c'est vrai....
My bad.
C'est juste que je me refuse à faire des break ou continue donc je ne les cherche même pas.

[_iri_]

Oui tout à fait d'autant que j'ai déjà une fonction récursive de recherche ... plus adaptée me semble-t'il que cette boucle itérative.

@Metalman si le nœud est non null, c'est que justement ce n'est pas une feuille non ?

[Metalman]

C'est corrigé... il y avait un break, donc oui tu sors bien de la boucle.
As-tu essayé d'ajouter du debug pour voir où tu es dans l'arbre au moment où tu supprimes, les valeurs passées, etc...

J'avais hésité à le poster plus tôt, mais tu es sûr que tu modifieras la racine de l'arbre avec cette fonction ?
Elle ne retourne pas de pointeur, et ne "peut pas" modifier le paramètre fourni...
Donc l'appelant ne pourra avoir qu'une épée-de-segfaultès au dessus de sa tête/en variable

[_iri_]

Oui pour le debug. Pour un nœud autre que la racine, l'arbre est parcouru correctement et le nœud supprimé.
Lorsque le nœud à supprimer est la racine, cette seconde boucle while boucle à l'infinie sur le nœud ... racine qui n'aurait donc pas de fils.

Alors effectivement, je me demande si le problème ne vient pas de ce break, dans la première boucle while, inadapté dans ce cas particulier ??

Je vais déjà éclaircir ce bout de code comme l'a intelligemment suggéré Medinoc !

[_iri_]

Dans le code présenté ici, j'ai ajouté un else break dans la seconde boucle, afin de pallier le cas de l'absence de nœud gauche.

La fonction n'était pas très jolie, je l'ai donc découpée et je les ai passées en mode récursif (préférence personnelle pour ce dernier point).

Merci pour vos commentaires qui m'ont favorablement guidé. Je passe en Résolu.