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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
.\"
.\" Se concede autorizacin para hacer y distribuir copias literales de este
.\" manual siempre que el aviso de copyright y esta autorizacin se conserven
.\" en todas las copias.
.\"
.\" Se concede autorizacin para copiar y distribuir versiones modificadas de
.\" este manual bajo las condiciones de copia literal, siempre que el resultado
.\" completo del trabajo realizado se distribuya bajo los trminos de una
.\" autorizacin idntica a esta.
.\"
.\" Como el ncleo y las bibliotecas de Linux estn permanentemente cambiando
.\" esta pgina del manual puede ser incorrecta o estar desactualizada. El
.\" autor o autores no asumen ninguna responsabilidad sobre los errores u
.\" omisiones, o por los daos que resulten del uso de la informacin contenida
.\" aqu. Puede que el autor o los autores no hayan tenido el mismo cuidado en
.\" escribir este manual, cuya licencia es libre de cargo, como el que puedan
.\" tener cuando trabajan profesionalmente.
.\"
.\" Versiones formatadas o procesadas de este manual, si no van acommpaadas
.\" por la fuente, deben dar a conocer el copyright y los autores de este
.\" trabajo.
.\"
.\" Traducido por Carlos Gomez Romero (cgomez@databasedm.es)
.TH TSEARCH 3 "24 de Sept. de 1995" "GNU" "Manual del Programador de Linux"
.SH NOMBRE
tsearch, tfind, tdelete, twalk \- manejan un rbol binario
.SH SINOPSIS
.nf
.B #include <search.h>
.sp
.BI "void *tsearch (const void *" key ", void **" rootp ,
.BI " int (*" compar ")(const void *, const void *));"
.sp
.BI "void *tfind (const void *" key ", const void **" rootp ,
.BI " int (*" compar ")(const void *, const void *));"
.sp
.BI "void *tdelete (const void *" key ", void **" rootp ,
.BI " int (*" compar ")(const void *, const void *));"
.sp
.BI "void twalk (const void *" root ", void (*" action ") (const void *" nodep ,
.BI " const VISIT " which ,
.BI " const int " depth "));"
.RE
.fi
.SH DESCRIPCIN
\fBtsearch\fP, \fBtfind\fP, \fBtwalk\fP y \fBtdelete\fP manejan un rbol
binario. Son una generalizacin del algoritmo T de Knuth (6.2.2).
El primer campo de cada nodo del rbol es un puntero al correspondiente
elemento de datos. (El programa llamante debe almacenar los datos actuales).
\fIcompar\fP apunta a la rutina de comparacin, que toma punteros a los dos
elementos. Debe devolver un entero negativo, cero o positivo dependiendo
de si el primer elemento es menor, igual o mayor que el segundo.
.PP
\fBtsearch\fP busca un elemento en el rbol. \fIkey\fP apunta al elemento
buscado. \fIrootp\fP apunta a la variable que apunta a la raz del rbol.
Si el rbol est vaco la variable a la que apunta \fIrootp\fP debera estar a
\fBNULL\fP.
Si se encuentra el elemento dentro del rbol \fBtsearch\fP devuelve un puntero
al elemento. Si no lo encuentra, \fBtsearch\fP lo aade y devuelve un puntero
al nuevo elemento.
.PP
\fBtfind\fP es como \fBtsearch\fP, slo que si no encuentra el elemento
\fBtfind\fP devuelve \fBNULL\fP.
.PP
\fBtdelete\fP borra un elemento del rbol. Sus argumentos son los mismos que
los de \fBtsearch\fP.
.PP
\fBtwalk\fP realiza un recorrido en profundidad o en anchura de un rbol
binario. \fIroot\fP apunta al nodo de comienzo del recorrido.
Si el nodo no es la raz slo se visitar parte del rbol.
\fBtwalk\fP llama a la funcin de usuario \fIaction\fP cada vez que se visita
un nodo (esto es, tres veces para un nodo interno y una vez para una hoja).
\fIaction\fP, toma tres argumentos. El primero es un puntero al nodo que se
est visitando. El segundo es un entero cuyo valor toma algundo de los
valores \fBpreorder\fP, \fBpostorder\fP o \fBendorder\fP dependiendo de si
esta es la primera, sregunda o tercera visita al nodo interno o \fBleaf\fP
si es la nica vez que se visita la hoja. (Estos smbolos estn definidos
en \fI<search.h>\fP). El tercer argumento es la profundidad del nodo,
siendo la profundidad de la raz cero.
.SH "VALOR DEVUELTO"
\fBtsearch\fP devuelve un puntero al elemento igual del rbol, o al elemento
aadido, o \fBNULL\fP si no hubo suficiente memoria para aadir el elemento.
\fBtfind\fP devuelve un puntero al elemento, o \fBNULL\fP si no se encuentra
ninguno igual. Si hay mltiples elementos que concuerdan con la clave el
elemento devuelto es inespecificado.
.PP
\fBtdelete\fP devuelve un puntero al padre del elemento borrado, o \fBNULL\fP
si no se encontr el elemento.
.PP
\fBtsearch\fP, \fBtfind\fP, y \fBtdelete\fP devuelven \fBNULL\fP si
\fIrootp\fP es \fBNULL\fP en la entrada a la funcin.
.SH ADVERTENCIAS
\fBtwalk\fP toma un puntero a la raz, mientra que las otras funciones toman
un puntero a una variable que apunta a la raz.
.PP
\fBtwalk\fP usa \fBpostorder\fP con el significado "depus del subrbol
izquierdo y antes del subrbol derecho". Algunas autoridades llamana a esto
"inorden" y reservan "postorden" con el significado "despus de ambos
subrboles".
.PP
\fBtdelete\fP libera la memoria necesaria para el elemento en el rbol.
El usuario es el responsable de liberar la memoria de los correspondientes
datos.
.PP
El programa de ejemplo depende del hecho de que \fBtwalk\fP no vuelve a
referenciar a un nodo despus de llamar a la funcin de usuario con el
argumento "endorder" o "leaf". Esto funciona con la biblioteca de GNU, pero
no est en la documentacin SysV.
.SH EJEMPLO
El ejemplo siguiente inserta doce nmeros aleatorios en un rbol binario
e imprime los nmeros en orden. Los nmeros son eliminados del rbol y
su almacenamiento liberado durante el recorrido.
.sp
.nf
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
void *root=NULL;
void *xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if(p) return p;
fprintf(stderr, "insufficient memory\\n");
exit(1);
}
int compare(const void *pa, const void *pb)
{
if(*(int *)pa < *(int *)pb) return -1;
if(*(int *)pa > *(int *)pb) return 1;
return 0;
}
void action(const void *nodep, const VISIT which, const int depth)
{
int *datap;
void *val;
switch(which)
{
case preorder:
break;
case postorder:
datap = *(int **)nodep;
printf("%6d\\n", *datap);
break;
case endorder:
datap = *(int **)nodep;
(void)tdelete(datap, &root, compare);
free(datap);
break;
case leaf:
datap = *(int **)nodep;
printf("%6d\\n", *datap);
val = tdelete(datap, &root, compare);
free(datap);
break;
}
return;
}
int main()
{
int i, *ptr;
void *val;
for (i = 0; i < 12; i++)
{
ptr = (int *)xmalloc(sizeof(int));
*ptr = rand()&0xff;
val = tsearch((void *)ptr, &root, compare);
if(val == NULL) exit(1);
}
twalk(root, action);
return 0;
}
.fi
.SH "CONFORME A"
SVID
.SH "VASE TAMBIN"
.BR qsort "(3), " bsearch "(3), " hsearch "(3), " lsearch "(3)"
|
