PDF de programación - 2.4 Arboles digitales de busqueda, tries y Patricia

Análisis del caso promedio

• El plan:

– Probabilidad
– Análisis probabilista
– Árboles binarios de búsqueda construidos

aleatoriamente

– Tries, árboles digitales de búsqueda y Patricia
– Listas “skip”
– Árboles aleatorizados

Técnicas Avanzadas de Programación - Javier Campos

127

Tries, árboles digitales de búsqueda y Patricia

• Tries: motivación…

– Letras centrales de la palabra “retrieval”, recuperación

(de información).

– Diccionario de Unix: 23.000 palabras y 194.000

caracteres  una media de 8 caracteres por palabra…
Hay información redundante:

bestial bestir bestowal bestseller bestselling

– Para ahorrar espacio:

agrupar los prefijos comunes

– Para ahorrar tiempo:

si las palabras son más cortas
es más rápida la búsqueda…

Técnicas Avanzadas de Programación - Javier Campos

best
---- i
---- - al
---- - r
---- owal
---- sell
---- ---- er
---- ---- ing

128

Tries, árboles digitales de búsqueda y Patricia

• Trie: definición formal

– Sea ={1 , …, m
– Sea * el conjunto de las palabras (o secuencias) de
un subconjunto de * (es decir un

} un alfabeto finito (m > 1).



símbolos de , y X
conjunto de palabras).
es:

– El trie asociado a X
= 

• trie(X) = , si X
• trie(X) = <x>, si X
• trie(X) = <trie(X

= {x}



)>, si |X| > 1, donde
representa el subconjunto de todas las palabras de X

\ 1 ), …, trie(X

\ m



quitándoles la primera letra.



\ 

X
empiezan por 



que



– Si el alfabeto tiene definida una relación de orden
(caso habitual), el trie se llama árbol lexicográfico.



Técnicas Avanzadas de Programación - Javier Campos

129

Tries, árboles digitales de búsqueda y Patricia

• Es decir, un trie es un árbol de prefijos:

bestial bestir bestowal bestseller bestselling

best

besti

bestowal

bestsell

bestial

bestir

bestseller

bestselling

best

owal

sell

i

al

r

er

ing

Técnicas Avanzadas de Programación - Javier Campos

130

Tries, árboles digitales de búsqueda y Patricia

• Utilidad del trie:

– Soporta operaciones de búsqueda de palabras:

best

owal

sell

i

al

r

er

ing

– También se pueden implementar inserciones y

borrados  TAD diccionario

best

owal

i

sell

ride

al

r

er

ing

Técnicas Avanzadas de Programación - Javier Campos

131

Tries, árboles digitales de búsqueda y Patricia
• Y también uniones e intersecciones  TAD

conjunto

• Y comparaciones de subcadenas 

procesamiento de textos,
biología computacional…



• No lo hemos dicho, pero no pueden almacenarse
palabras que sean prefijos de otras… uso de un
carácter terminador si eso fuese preciso.

Los tries son una de las estructuras
de datos de propósito general más

importantes en informática

Técnicas Avanzadas de Programación - Javier Campos

132

Tries, árboles digitales de búsqueda y Patricia

• Implementaciones de tries:

– Nodo-vector: cada nodo es un vector de punteros para

acceder a los subárboles directamente
cris, cruz, javi, juan, rafa, raquel

c

j

r

r

i

u

a

v

s

$

$

z

i

$

$

u

a

f

q

a

n

a

$

u

e

l

¡Demasiado coste en espacio!

Técnicas Avanzadas de Programación - Javier Campos

$

133

Tries, árboles digitales de búsqueda y Patricia
– Nodo-lista: cada nodo es una lista enlazada por

punteros que contiene las raíces de los subárboles

cris, cruz, javi, juan, rafa, raquel

c

r

i

s

u

z

j

a

v

i

u

a

n

r

a

f

a

(representación primogénito-siguiente hermano
de un bosque)
¡Menos coste en espacio pero más en tiempo para buscar!

Técnicas Avanzadas de Programación - Javier Campos

q

u

e



l

134

Tries, árboles digitales de búsqueda y Patricia
– Precisión sobre las implementaciones anteriores:

En realidad, cuando un cierto nodo es la raíz de un
subtrie que ya sólo contiene una palabra, se puede
almacenar esa palabra (sufijo) directamente en un
nodo externo (eso ahorra espacio, aunque obliga a
manejar punteros a tipos distintos…)

r

a

f

a

quel

Técnicas Avanzadas de Programación - Javier Campos

135

Tries, árboles digitales de búsqueda y Patricia
– Nodo-abb: la estructura se llama también

árbol ternario de búsqueda.
Cada nodo contiene:
• Dos punteros al hijo izquierdo y derecho (como en un árbol

binario de búsqueda).

• Un puntero, central, a la raíz del trie al que da acceso el nodo.
Objetivo: combinar la eficiencia en tiempo de los tries
con la eficiencia en espacio de los abb’s.
• Una búsqueda compara el carácter actual en la cadena

buscada con el carácter del nodo.

• Si el carácter buscado es menor, la búsqueda de ese carácter

sigue en el hijo izquierdo.

• Si el carácter buscado es mayor, se sigue en el hijo derecho.
• Si el carácter es igual, se va al hijo central, y se pasa a buscar

el siguiente carácter de la cadena buscada.

Técnicas Avanzadas de Programación - Javier Campos

136

Tries, árboles digitales de búsqueda y Patricia

Árbol ternario de búsqueda para las palabras…

as at be by he in is it of on or to

En un abb:

En un trie (representación nodo-vector o nodo-lista):

Técnicas Avanzadas de Programación - Javier Campos

137

Tries, árboles digitales de búsqueda y Patricia

Árbol ternario de búsqueda:

Técnicas Avanzadas de Programación - Javier Campos

138

Tries, árboles digitales de búsqueda y Patricia

• Árboles digitales de búsqueda:

– Caso binario (m

= 2, es decir, sólo dos símbolos):

• Almacenar claves completas en los nodos, pero usando los
bits del argumento para decidir si se sigue por el subárbol
izquierdo o por el derecho.



• Ejemplo,
usando el
código MIX
(D.E. Knuth)

9 01001 R 19 10011
0 00000 I
11 01011 S 22 10110
A 1 00001 J
B 2 00010 K 12 01100 T 23 10111
C 3 00011 L 13 01101 U 24 11000
D 4 00100 M 14 01110 V 25 11001
E 5 00101 N 15 01111 W 26 11010
F
6 00110 O 16 10000 X 27 11011
G 7 00111 P 17 10001 Y 28 11100
H 8 01000 Q 18 10010 Z 29 11101

Técnicas Avanzadas de Programación - Javier Campos

139

Tries, árboles digitales de búsqueda y Patricia
– Árboles digitales de búsqueda (caso binario):

1ª

THE

(10111…)

3ª

AND

(00001…)

(10000…)

2ª

OF

(00001…)

5ª

A
11ª

FOR

30ª
FROM

24ª

12ª

AS
17ª

ARE
29ª

AT

BE
19ª

BY

20ª

BUT

15ª

HIS

16ª

HE

21ª

HAVE

28ª

HAD

27ª

6ª

IN

8ª

IS

4ª

(01001…)
25ª

18ª
NOT

ON

TO
7ª

9ª

I

26ª

OR

(10111…)
14ª

13ª

WITH

THAT WAS
23ª
31ª

THIS WHICH

22ª
YOU

10ª

IT

Las 31 palabras inglesas más frecuentes,
insertadas por orden de frecuencia descendente.

HER
¡Ojo! Es un árbol de búsqueda pero considerando
la codificación binaria de las claves (código MIX).

Técnicas Avanzadas de Programación - Javier Campos

140

Tries, árboles digitales de búsqueda y Patricia
– La búsqueda en al árbol anterior es binaria pero puede

ampliarse fácilmente a m-aria (m > 2), para un
alfabeto con m

símbolos.



1ª

THE
18ª

NOT
9ª
8ª
I
IS
27ª

10ª
IT

3ª
AND
12ª
AS

17ª
29ª
AT

BE
20ª
BUT

FOR11ª
30ª
FROM

19ª
BY

5ª
A

24ª
ARE

15ª

HIS

21ª
HAVE

IN6ª
16ª

HE

OF2ª
25ª
ON

26ª
OR

WITH

TO4ª
7ª
THAT

13ª
14ª
WAS

22ª
YOU
23ª

WHICH

28ª

HAD

HER

31ª

THIS

Los mismos datos de antes, insertados en igual orden,
pero en un árbol digital de búsqueda de orden 27.

Técnicas Avanzadas de Programación - Javier Campos

141

Tries, árboles digitales de búsqueda y Patricia

• Patricia

(Practical Algorithm To Retrieve Information Coded In

Alphanumeric)
– Problema del trie: si |{claves}| <<



|{claves potenciales}|, la mayoría de los nodos
internos tienen un solo hijo  aumenta el coste en
espacio

– Idea: árbol binario, pero evitando las bifurcaciones de

una sola dirección.

– Patricia: representación compacta de un trie en la que
todos los nodos con un solo hijo “se mezclan” con sus
padres.

– Ejemplo de utilización: tablas de encaminamiento en

los router, asignatura “Sistemas de transporte de
datos” (búsqueda de direcciones = longest prefix
matching)

Técnicas Avanzadas de Programación - Javier Campos

142

Tries, árboles digitales de búsqueda y Patricia
– Ejemplo de Patricia:

• Partimos de:

– Un trie binario con

las claves almacenadas en
las hojas y compactado
(de manera que cada
nodo interno tiene dos hijos).
– La etiqueta del nodo interno

indica el bit usado para bifurcar.

1

0

3

1

2

0001 0011

4

4

1000 1001

1100 1101

• En un Patricia, las claves se almacenan en los nodos internos.

– Como hay un nodo interno menos que

nº de elementos, hay que añadir un
nuevo nodo (se pone como raíz).

– Cada nodo sigue guardando el

nº de bit usado para bifurcar.
– Ese nº distingue si el puntero

sube o baja (si > el del padre, baja).

0011

Técnicas Avanzadas de Programación - Javier Campos

1101
3

0

0001

1

2

1001

4

1000

4

1100

143

Tries, árboles digitales de búsqueda y Patricia
– Búsqueda de clave:

0

0001

• Se usan los bits de la clave de izq. a dch.

Bajando en el árbol.

• Cuando el puntero que se ha

seguido va hacia arriba se
compara la clave con la del nodo.

• Ejemplo, búsqueda de 1101:

0011

1101
3

1

2

1001

4

1000

4

1100

– Se empieza yendo al hijo izq. de la raíz.
– El puntero que se ha seguido es hacia abajo (se sabe porque el
bit que etiqueta el nodo 1101, 1, es mayor que el del padre, 0).
– Se busca según el valor del bit 1 de la clave buscada, como es

un 1, vamos al hijo derecho (el 1001).

– El nº de bit del nodo alcanzado es 2, se sigue hacia abajo según

ese bit, como el 2º bit de la clave es 1, vamos al hijo derecho.

– Ahora se usa el 4º bit de la clave buscada, como es 1 seguimos

el puntero hijo dch. y llegamos a la clave 1101.

– Como el nº de bit es 1 (<4) comparamos la clave actual con la

buscada, como coincide, terminamos con éxito.

Técnicas Avanzadas de Programación - Javier Campos

144

Tries, árboles digitales de búsqueda y Patricia
– Inserción de claves:

0000101 0

0000101 0

• Partimos de árbol vacío (ninguna clave).
• Insertamos la clave 0000101.
• Ahora insertamos la clave 0000000.

Buscando esa clave llegamos a la raíz y