tsearch, tfind, tdelete, twalk, twalk_r, tdestroy - Manipuler un arbre binaire
de recherche
Bibliothèque C standard (
libc,
-lc)
#include <search.h>
typedef enum { preorder, postorder, endorder, leaf } VISIT;
void *tsearch(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void *tfind(const void *key, void *const *rootp,
int (*compar)(const void *, const void *));
void *tdelete(const void *restrict key, void **restrict rootp,
int (*compar)(const void *, const void *));
void twalk(const void *root,
void (*action)(const void *nodep, VISIT which,
int depth));
#define _GNU_SOURCE /* Consultez feature_test_macros(7) */
#include <search.h>
void twalk_r(const void *root,
void (*action)(const void *nodep, VISIT which,
void *closure),
void *closure);
void tdestroy(void *root, void (*free_node)(void *nodep));
tsearch(),
tfind(),
twalk() et
tdelete() permettent
de manipuler un arbre binaire de recherche. Ces fonctions implémentent
une généralisation de l'algorithme T de Knuth (6.2.2). Le
premier membre de chaque nœud de l'arbre est un pointeur vers la
donnée elle-même (le programme appelant doit prendre en charge
le stockage de ces données).
compar pointe sur une routine de
comparaison prenant en argument deux pointeurs sur ces données. Elle
doit renvoyer un entier négatif, nul, ou positif suivant que le premier
élément est inférieur, égal ou supérieur au
second.
tsearch() recherche un élément dans l'arbre.
key
pointe sur l'élément à chercher.
rootp pointe vers
une variable qui pointe vers la racine de l'arbre. Si l'arbre est vide, alors
rootp doit pointer sur une variable devant être
réglée à
NULL. Si l'élément est
trouvé dans l'arbre,
tsearch() renvoie un pointeur sur le
nœud de l'arbre correspondant. (En d'autres termes,
tsearch()
retourne un pointeur sur un pointeur sur l'élément.) Si
l'élément n'est pas trouvé,
tsearch() l'ajoute
dans l'arbre et renvoie un pointeur sur le nœud de l'arbre
correspondant.
tfind() fonctionne comme
tsearch(), sauf que si
l'élément n'est pas trouvé, la fonction
tfind()
renvoie
NULL.
tdelete() supprime un élément de l'arbre. Ses arguments
sont les mêmes que ceux de
tsearch().
twalk() exécute un parcours en profondeur d'abord, de gauche
à droite ensuite, de l'arbre binaire.
root pointe sur le
nœud de départ du parcours. S'il ne s'agit pas de la vraie
racine de l'arbre, seule une partie de celui-ci sera balayé.
twalk() appelle la fonction
action chaque fois qu'un nœud
est rencontré (c'est-à-dire trois fois pour un nœud
interne et une seule fois pour une feuille de l'arbre).
action doit
accepter trois arguments. Le premier argument est un pointeur sur le
nœud rencontré. La structure du nœud n'est pas
spécifiée, mais il est possible de transformer le pointeur sous
forme de pointeur-vers-pointeur-vers-élément afin
d'accéder à l'élément enregistré dans le
nœud. L'application ne doit pas modifier la structure pointée
par cet argument. Le deuxième argument est un entier prenant l'une des
valeurs suivantes :
preorder,
postorder ou
endorder suivant qu'il s'agisse de la première, deuxième
ou troisième rencontre du nœud, ou la valeur
leaf s'il
s'agit d'un nœud feuille (ces symboles sont définis dans
<search.h>). Le troisième argument est la profondeur du
nœud dans l'arbre, le nœud racine ayant la profondeur
zéro.
Ordinairement,
preorder,
postorder et
endorder sont connus
sous le nom
preorder (préfixe),
inorder (infixe), et
postorder (postfixe) : avant de visiter le nœud fils,
après le premier et avant le second, après avoir visité
les enfants. Ainsi, le choix du nom
postorder est un peu
déroutant.
twalk_r() est similaire à
twalk(), mais à la place
de l'argument
depth, le pointeur argument
closure est
passé à chaque invocation de la fonction de rappel d'action,
inchangé. Ce pointeur peut être utilisé pour passer de
l'information vers et depuis la fonction de rappel de façon sûre
pour les threads, sans utiliser de variables globales.
tdestroy() supprime tout l'arbre pointé par
root,
libérant toutes les ressources allouées par la fonction
tsearch(). Pour libérer les données de chaque
nœud, la fonction
free_node est invoquée. Le pointeur sur
les données est passé en argument à cette fonction. Si
aucune libération n'est nécessaire,
free_node doit
pointer vers une fonction ne faisant rien.
tsearch() renvoie un pointeur sur un nœud correspondant de
l'arbre, ou sur le nœud nouvellement ajouté, ou
NULL s'il
n'y avait pas assez de mémoire pour ajouter le nœud.
tfind() renvoie un pointeur sur le nœud recherché, ou
NULL si aucune correspondance n'a été trouvée. Si
plusieurs éléments correspondent à la clé,
l’élément dont le nœud est renvoyé n'est
pas spécifié.
tdelete() renvoie un pointeur sur le nœud père de celui
détruit, ou
NULL si l'élément n'a pas
été trouvé. Si le nœud détruit était
le nœud racine,
tdelete() renvoie un pointer ne pointant sur
aucun objet valable et auquel il ne faut pas accéder.
tsearch(),
tfind() et
tdelete() renvoient également
NULL si
rootp valait
NULL.
twalk_r() est disponible depuis la glibc 2.30.
Pour une explication des termes utilisés dans cette section, consulter
attributes(7).
| Interface |
Attribut |
Valeur |
|
tsearch(), tfind(), tdelete() |
Sécurité des threads |
MT-Safe race:rootp |
|
twalk() |
Sécurité des threads |
MT-Safe race:root |
|
twalk_r() |
Sécurité des threads |
MT-Safe race:root |
|
tdestroy() |
Sécurité des threads |
MT-Safe |
POSIX.1-2001, POSIX.1-2008, SVr4. Les fonctions
tdestroy() et
twalk_t() sont des extensions GNU.
twalk() utilise un pointeur sur la racine, alors que les autres fonctions
utilisent un pointeur sur une variable pointant sur la racine.
tdelete() libère la mémoire nécessaire au stockage
du nœud dans l'arbre. Le programme appelant est responsable de la
libération de la mémoire occupée par
l'élément de données correspondant.
Le programme d'exemple s'appuie sur le fait que
twalk() ne fait plus
jamais référence à un nœud après avoir
appelé la fonction utilisateur avec l'argument
« endorder » ou
« leaf ». Ceci fonctionne avec
l'implémentation de la bibliothèque GNU, mais n'est pas
spécifié sous System V.
Le programme suivant insère douze nombres aléatoires dans un arbre
binaire, où les doublons sont supprimés, puis affiche les
nombres classés.
#define _GNU_SOURCE /* Expose la déclaration de tdestroy() */
#include <search.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static void *racine = NULL;
static void *
xmalloc(size_t n)
{
void *p;
p = malloc(n);
if (p)
return p;
fprintf(stderr, "insufficient memory\n");
exit(EXIT_FAILURE);
}
static int
compare(const void *pa, const void *pb)
{
if (*(int *) pa < *(int *) pb)
return -1;
if (*(int *) pa > *(int *) pb)
return 1;
return 0;
}
static void
action(const void *nodep, VISIT which, int depth)
{
int *datap;
switch (type) {
case preorder:
break;
case postorder:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
case endorder:
break;
case leaf:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
}
}
int
main(void)
{
int *ptr;
int **val;
srand(time(NULL));
for (unsigned int i = 0; i < 12; i++) {
ptr = xmalloc(sizeof(*ptr));
*ptr = rand() & 0xff;
val = tsearch(ptr, &root, compare);
if (val == NULL)
exit(EXIT_FAILURE);
if (*val != ptr)
free(ptr);
}
twalk(root, action);
tdestroy(root, free);
exit(EXIT_SUCCESS);
}
bsearch(3),
hsearch(3),
lsearch(3),
qsort(3)
La traduction française de cette page de manuel a été
créée par Christophe Blaess
<
https://www.blaess.fr/christophe/>, Stéphan Rafin
<
[email protected]>, Thierry Vignaud
<
[email protected]>, François Micaux, Alain Portal
<
[email protected]>, Jean-Philippe Guérard
<
[email protected]>, Jean-Luc Coulon (f5ibh)
<
[email protected]>, Julien Cristau
<
[email protected]>, Thomas Huriaux <
[email protected]>,
Nicolas François <
[email protected]>, Florentin
Duneau <
[email protected]>, Simon Paillard
<
[email protected]>, Denis Barbier
<
[email protected]>, David Prévot <
[email protected]>,
Jean-Baptiste Holcroft <
[email protected]> et Grégoire
Scano <
[email protected]>
Cette traduction est une documentation libre ; veuillez vous reporter
à la
GNU
General Public License version 3 concernant les conditions de copie
et de distribution. Il n'y a aucune RESPONSABILITÉ LÉGALE.
Si vous découvrez un bogue dans la traduction de cette page de manuel,
veuillez envoyer un message à
[email protected]