Download Recorridos sobre árboles binarios

Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
Arboles
En esta sección se presentan los árboles que son un tipo de dato abstracto más adecuado
para el tratamiento de grandes cantidades de información, las aplicaciones de los
mismos son muy diversas, así por ejemplo, se usan para el almacenamiento y búsqueda
de información ya que pueden establecerse diversas estructuras en las que el tiempo
medio de las operaciones de búsqueda es del orden de log(n), lo que es bastante bueno
comparado por ejemplo, con las listas enlazadas en la búsqueda de alguna información,
otros ámbitos de aplicación son en la implementación del sistema de archivos en los
sistemas operativos, manejo de archivos en la realización de bases de datos, así como
diversos árboles que poseen sus propias estructuras y propiedades, tales como los
árboles AA, Splay, Red-Black, AVL, etc....
Los árboles se basan en el concepto de nodo, que corresponde a cualquier tipo cuyos
elementos son registros formados por un campo datos y un número dado de punteros, tal
como se vieron en las listas enlazadas , por ejemplo, lista enlazada, lista doblemente
enlazada, árbol binario y un árbol ternario.
Un árbol es una estructura no lineal formada por un conjunto de nodos y un conjunto de
ramas o arcos, tal como se aprecia en la siguiente figura.
Ahora, si los nodos están rotulados con el fin de almacenar un tipo de información,
tenemos una gran variedad de árboles. En general, digamos que en un árbol existe un
nodo especial denominado raíz. Así mismo, un nodo del que sale alguna rama, recibe el
nombre de nodo de bifurcación o nodo rama y un nodo que no tiene ramas recibe el
nombre de nodo terminal o nodo hoja, tal como lo muestra la siguiente figura.
___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
1
Diseño y Análisis de Algoritmos
raíz
Dr. Eric Jeltsch F.
Nivel 0
A
nodo de bifurcación
B
C
Nivel 1
D
hojas
E
F
Nivel 2
De un modo más formal, diremos que un árbol es un conjunto finito de uno o más nodos
tales que:
a) Existe un nodo especial llamado raíz del árbol, y
b) los nodos restantes están agrupados en n > 0 conjuntos disjuntos A1, .., An donde
cada uno de los cuales es a su vez un árbol que recibe el nombre de subárbol.
Evidentemente, la definición dada es recursiva; es decir, hemos definido un árbol como
un conjunto de árboles. De la definición se desprende, que cada nodo de un árbol es la
raíz de algún subárbol contenido en la totalidad del mismo. El número de ramas de un
nodo recibe el nombre de grado del nodo. El nivel de un nodo respecto al nodo raíz se
define diciendo que la raíz tiene nivel 0 y cualquier otro nodo tiene un nivel igual a la
distancia de ese nodo al nodo raíz. El máximo de los niveles se denomina profundidad o
altura del árbol. Es útil limitar los árboles en el sentido de que cada nodo sea a lo sumo
de grado 2. De esta forma cabe distinguir entre subárbol izquierdo y subárbol derecho
de un nodo. Los árboles así formados, se denominan árboles binarios. Un árbol binario
es un conjunto finito de nodos que consta de un nodo raíz que tiene dos subárboles
binarios denominados subárbol izquierdo y subárbol derecho. Las expresiones
algebraicas, debido a que los operadores que intervienen son operadores binarios, nos
dan un ejemplo de estructura en árbol binario. La figura siguiente nos muestra un árbol
que corresponde a la expresión aritmética: (a+b*c)/(d-e/f)
/
-
+
a
d
*
b
c
/
e
f
El árbol binario es una estructura de datos muy útil cuando el tamaño de la estructura no
se conoce, y se necesita acceder a sus elementos ordenadamente, la velocidad de
búsqueda es importante o el orden en el que se insertan los elementos es casi aleatorio.
En definitiva, un árbol binario es una colección de objetos (nodos del árbol) cada uno de
___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
2
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
los cuales contiene datos o una referencia a los datos, una referencia a su subárbol
izquierdo y una referencia a su subárbol derecho. Según lo expuesto, la estructura de
datos representativa de un nodo puede ser de la forma siguiente:
Si el número de nodos en un árbol de orden t es n, entonces un árbol completo de altura
h contiene:
h
(1) N   t i 1 
i 1
th 1
t 1
En particular, un árbol binario (t=2) contiene N  2 h  1 nodos. Esto nos dice que para
un árbol binario de altura h= 3 , se tienen 7 nodos. Tal como se vé en la siguiente figura,
Clasificación de los árboles
A causa del gran significado que poseen los árboles es que se hace necesaria una
clasificación, tanto en la forma, como los datos que son almacenados en los árboles, así
como en la forma de buscar un tipo de información, y de recorrer los nodos. En general,
los datos o información se encuentra en los nodos, de aquí que consideremos en forma
particular los árboles binarios y la forma de cómo disponer su información, generando
un tipo de árbol llamado arbol de búsqueda binaria.
ABB(árboles de búsqueda binaria)
Las claves o datos son dispuestas de la siguiente manera: los datos menores a la
izquierda y los mayores a la derecha. En la siguiente figura se puede constatar
fácilmente la posición en la cual se encuentra algún dato en particular.
___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
3
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
40
30
50
20
11
39
37
24
60
44
41
40
45
62
65
Arboles de Decisión(o árbol de búsqueda o de comparaciones)
Este tipo de árboles es aplicado a los algoritmos el cual se obtiene al trazar de principio
a fin la acción del algoritmo, representando cada comparación como un vértice del
árbol. En los árboles binarios se da la situación de dos comparaciones, las que se pueden
codificar por:
- 0 : Decisión para el hijo izquierdo
- 1 : Decisión para el hijo derecho
En el ejemplo, se muestra el árbol de comparaciones para la búsqueda secuencial, en
donde debemos resaltar los „cajones„ como nodos externos o especiales y los nodos en
donde se encuentra la información, generándose así un nuevo tipo de árbol, llamado
árbol extendido.
1
=
=

2

3
=

=
n

___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
4
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
En este sentido, el árbol de comparaciones cambia radicalmente su rotulación si
incorporamos la comparación <, >, o =, tal como se vé en la siguiente figura, cuando
n=10, en la cual se combinan dos comparaciones a fin de obtener una comparación de
tres vías para cada paso, así el árbol se vé más compacto, en comparación con el árbol
que considera las comparaciones  a la izquierda y > a la derecha.
5
=
<
>
8
2
<
1
< = >
=
>
<
6
3
< = >
4
< =
< =
>
=
>
7
< = >
>
9
< =
>
10
<
=
>
Basado en esta nueva forma de rotular los nodos, digamos que podríamos clasificar los
árboles en árboles orientados a los nodos y árboles orientados a las hojas, para
distinguirlos digamos que los primeros son árboles en donde los datos se encuentran en
los nodos del árbol, mientras que los otros son árboles en donde los datos se encuentran
solamente en las hojas. Convengamos que, tal como la figura anterior si el árbol es
ampliado con nodos especiales, de manera que todos los subárboles están completos, es
decir todos los apuntadores sin nodos descendientes apuntan a un nodo especial, se
habla de un árbol extendido
En este contexto definamos la longitud de trayectoria interna de un nodo, como el
número de aristas o ramas que se recorren desde la raíz al nodo. Por otra parte, la
longitud de trayectoria interna de un árbol, es la suma de todas las longitudes de
trayectoria de sus nodos. En principio, un nodo de nivel i tiene una longitud de
trayectoria i. Sin embargo, es posible definir árboles en los que esto no sucede, tal como
ocurre en los árboles B.
Otra forma de clasificación es considerar árboles optimal estáticos u optimal dinámicos,
los primeros significa que el árbol debe ser construido nuevamente, mientras que el otro
se construye durante el ingreso o al agregar los datos. El objetivo final en ambos casos
es lograr una razonable estructura de almacenamiento, aunque esta situación en general
globalmente no se pueda lograr, pero sí localmente. En ambos casos, se evitan árboles
degenerados, que son los árboles que degeneran en listas lineales o ramas.
Los árboles sirven también para representar una jerarquía, tal como lo muestra el
siguiente ejemplo, respecto de la representación de expresiones aritméticas. Por
ejemplo, para la expresión (A  B / C) ( D  E F) se puede representar por el siguiente
árbol:
___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
5
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
*
+
-
A
/
B
D
*
E
C
F
Relación de Orden y Representación
En cada nodo, se da una situación de orientación y jerarquerización en los árboles
binarios: Toda clave al lado derecho(izq) de los subarboles son mayores(menores) a la
clave del nodo. Con ayuda de esta relación de orden se generan arboles que sirven para
buscar, borrar o hallar algún elemento en particular.
DATOS
Información
Punteros
Izquierda(Izq)
derecha(Der)
Puntero al hijo izquierdo
Puntero al hijo derecho
La búsqueda de un elemento se realiza desde la raíz hasta el nodo en donde se encuentra
la clave, en caso de existir, en caso contrario no existe el dato.
1. Las dos claves son iguales, la que se busca y la que tiene el nodo: el elemento es
encontrado
2. La clave buscada es pequeña: el elemento buscado se encuentra solamente en los
subarboles izquierdo
3. La clave buscada es mayor: el elemento buscado se encuentra solamente en los
subarboles derecho.
Este proceso se realiza hasta que la clave es encontrada. Notar que la estructura y
crecimiento de los árboles binarios son a través de una relación de orden, por tal motivo
___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
6
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
se generan varios árboles con rotulaciones distintas. Por ejemplo, se dan las 3 claves 1,
2 y 3, tan solo con estas podemos generar distintos árboles binarios respetuosos del
orden antes descrito, por ejemplo
1, 2, 3
1, 3, 2
2, 1, 3
1
1
2
3
2
3
1
1
2
2, 3, 1
3, 1, 2
3, 2, 1
2
3
3
3
2
1
1
existiendo 6 distintas formas de rotularlos y por ende 6 árboles binarios distintos. En
general, se demuestra que n-elementos generan n! formas.
k
Aquí existen (k-1)! Subarboles
con claves 1..N
Aquí existen (N –k)! subarboles
con claves k+1, .... N
___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
7
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
Operaciones
Veamos como generar un árbol de búsqueda binaria a partir del árbol vacío, al cual se le
agregan los datos (12, 7, 15, 5, 13).
12
7
Izquierda(I
zq)
derecha(De
r)
Izquierda(I
5 zq)
derecha(De
r)
Izquierda(I
zq)
derecha(De
r)
15
Izquierda(I
13 zq)
derecha(De
r)
Izquierda(I
zq)
derecha(De
r)
Inserción en un ABB
1) comparar la clave a insertar con la raíz del árbol. Si es mayor, debe avanzar hacia el
subarbol derecho. Si es menor, debe avanzar hacia el subarbol izquierdo.
Repetir sucesivamente 1), hasta que se cumpla alguna de las siguientes condiciones:
a) el subarbol derecho es vacío, o el subarbol izquierdo es vacío; en cuyo caso se
procede a insertar el elemento en el lugar que le corresponda.
b) La clave que se quiere insertar es igual a la raíz del árbol; en cuyo caso no se realiza
la inserción.
Por ejemplo, insertar 120, 87 y 130, en ese orden a partir del árbol vacío.
120
120
87
120
87
130
Borrar o eliminar un nodo
Se refiere a eliminar un Nodo con una determinada clave, suponiendo que el elemento
ha sido encontrado. Existen varias situaciones, entre ellas están:
a) Si el elemento a borrar es terminal u hoja, simplemente se elimina.
___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
8
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
b) Si el elemento a borrar tiene un solo descendiente, entonces tiene que sustituirse por
ese descendiente.
c) Si el elemento a borrar tiene los 2 descendientes, entonces se tiene que sustituir por
el nodo que se encuentra más a la izquierda en el subárbol derecho o por el nodo que
se encuentra más a la derecha en el subárbol izquierdo.
Por ejemplo
a) El nodo que se eliminará es una hoja.
Antes
despues
b) El nodo que se elimina tiene exactamente un hijo.
Antes
despues
c) El nodo que se elimina tiene 2 hijos
Antes
despues
___________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena
9
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
Otro ejemplo, es el árbol siguiente,
12
7
15
5
2
13
6
14
y se desea saber, que forma tendrá cuando se eliminen los valores 2 y 6.(caso a)
12
7
15
5
13
14
c) 13(caso b)
12
7
15
5
14
d) 15 (caso b)
12
7
14
___________________________________________________________________ 10
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
5
e) 5 (caso a)
12
7
14
f) 12 (caso c)
7
14
___________________________________________________________________ 11
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
Dado el árbol búsqueda binaria. Se desea eliminar el 12, como queda el ABB.
12
7
7
5
8
5
8
2) Implementación del borrado según la transferencia de claves en un árbol de búsqueda
binaria en Java
a) Si el elemento a borrar es terminal u hoja, simplemente se elimina.
b) Si el elementoa borrar tiene un solo descendiente, entonces tiene que sustituirse por
ese descendiente.
c) Si el elemento a borrar tiene los 2 descendientes, entonces se tiene que sustituir por el
nodo que se encuentra más a la izquierda en el subárbol derecho o por el nodo que se
encuentra más a la derecha en el subárbol izquierdo.
Recorrido y orden en Arboles
El principio de recorrer un árbol binario, determina un orden sobre el conjunto de
nodos. Existen 3 posibilidades o principios de como recorrer un árbol binario, ellos son
la lectura en Inorden, Preorden y Posorden.
Inorden
Orden IRD
(1) Recorrer el subárbol izquierdo en INORDEN
(2) Visitar la raíz
(3) Recorrer el subárbol derecho en INORDEN
Orden DRI
(1) Recorrer el subárbol derecho en INORDEN
(2) Visitar la raíz
(3) Recorrer los subárbol derecho en INORDEN
Los orden IRD y DRI son uno inverso del otro. El orden IRD, se llama orden simétrico
Preorden
Orden RID
___________________________________________________________________ 12
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
(1) Visitar la raíz
(2) Recorrer el subárbol izquierdo en PREORDEN
(3) Recorrer el subárbol derecho en PREORDEN
Orden RDI
(1) Visitar la raíz
(2) Recorrer el subárbol derecho en PREORDEN
(3) Recorrer el subárbol izquierdo en PREORDEN
En general se visita la raíz antes de los dos subárboles.
Posorden
Orden IDR
(1) Recorrer el subárbol izquierdo en POSTORDEN
(2) Recorrer el subárbol derecho en POSTORDEN
(3) Visitar la raíz
Primero se visitan los subárboles y luego la raíz.
Orden DIR
(1) Recorrer el subárbol derecho en POSTORDEN
(2) Recorrer el subárbol izquierdo en POSTORDEN
(3) Visitar la raíz
Primero se visitan los subárboles y luego la raíz.
Por ejemplo, se dan una serie de árboles binarios, y la idea es describir su recorrido en
las formas antes definidas.
1.A
B
C
E
D
F
I
G
J
H
K
L
"Preorden": A B C E I F J D G H K L
"Inorden":
EICFJBGDKHLA
___________________________________________________________________ 13
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
"Posorden": I E J F C G K L H D B A
2.
+
*
A
+
B
*
C
E
D
"Preorden": + * A B + * C D E
"Inorden":
A*B+C*D+E
"Posorden": A B * C D * E + +
Este ejemplo nos muestra una estructura de árbol (representación de una estructura
jerarquica de una expresión aritmáetica). Esta representación „arbórea“ es en particular
muy útil para la traducción de una expresión en lenguaje de máquina. Desde la
estructura anterios se pueden representar fácilmente las distintas formas de una
expresión aritmética. Entregando de esta manera el recorrido en "Posorden" como la
notación Postfija, y en "Preorden" la notación Prefija".
3.
+
A
*
B
C
"Preorden": + A * B C
"Inorden":
A+B*C
"Posorden": A B C * +
4.
*
+
A
C
B
___________________________________________________________________ 14
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
"Preorden": * + A B C
"Inorden":
A+B*C
"Posorden": A B + C *
Aplicaciones de los recorridos
Con ayuda de los recorridos antes descritos se pueden determinar algunas otras
operaciones sobre los árboles. Por ejemplo, determinar el número de hojas en el árbol,
entregar la altura del árbol, copiar el árbol, borrar el árbol, descripción gráfica de un
árbol de búsqueda binaria. En un árbol de búsqueda binario se puede dar la siguiente
situación, la que se interpreta como un árbol de búsqueda binario que degenero en una
lista lineal, derivando en que la búsqueda de algún elemento en particular resulta tan
costoso como buscarlo en forma exhaustiva, de aquí que es importante evitar que se
genere una situación de este tipo.
1
2
3
4
5
Para ello, están los „árboles perfectamente balanceados“ que evitan que se de una
situación como la descrita a continuación, de manera de obtener una forma de balanceo
que en definitiva facilita la búsqueda de algún elemento, pues no se encuentra a una
profundidad tan alejado de la raíz. Se verifica que el árbol de la derecha es árbol AVL,
que luego lo veremos en detalle.
A continuación se muestra un simple algoritmo que genera un árbol con las condiciones
de balanceo.
(1) ordenar las claves en una sucesión ordenada en forma creciente
(2) es conocido el número de Objetos (claves) que se deben tener.
___________________________________________________________________ 15
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura o
a nivel. Puesto que los árboles no son secuenciales como las listas, hay que buscar
estrategias alternativas para visitar todos los nodos. Dada la siguiente figura:
Figura 1
- Recorridos en profundidad:
* Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser
simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol
izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por
naturaleza. Si se hace el recorrido en preorden del árbol de la figura 1 las visitas serían
en el orden siguiente: a,b,d,c,e,f.
void preorden(tarbol *a)
{
if (a != NULL) {
visitar(a);
preorden(a->izq);
preorden(a->der);
}
}
* Recorrido en inorden u orden central: se visita el subárbol izquierdo, el nodo actual, y
después se visita el subárbol derecho. En el ejemplo de la figura 1 las visitas serían en
este orden: b,d,a,e,c,f.
void inorden(tarbol *a)
{
if (a != NULL) {
inorden(a->izq);
visitar(a);
inorden(a->der);
}
}
___________________________________________________________________ 16
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
* Recorrido en postorden: se visitan primero el subárbol izquierdo, después el subárbol
derecho, y por último el nodo actual. En el ejemplo de la figura 1 el recorrido quedaría
así: d,b,e,f,c,a.
void postorden(arbol *a)
{
if (a != NULL) {
postorden(a->izq);
postorden(a->der);
visitar(a);
}
}
La ventaja del recorrido en postorden es que permite borrar el árbol de forma
consistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este
recorrido se borrará el árbol o subárbol que se pasa como parámetro. La razón para
hacer esto es que no se debe borrar un nodo y después sus subárboles, porque al borrarlo
se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla de
manipular una estructura de datos inexistente. Una alternativa es utilizar una variable
auxiliar, pero es innecesario aplicando este recorrido.
- Recorrido en amplitud:
Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1
(como mucho hay uno, la raíz), después los nodos de nivel 2, así hasta que ya no queden
más. Si se hace el recorrido en amplitud del árbol de la figura una visitaría los nodos en
este orden: a,b,c,d,e,f.
Construcción de un árbol binario
Hasta el momento se ha visto la declaración y recorrido de un árbol binario. Sin
embargo no se ha estudiado ningún método para crearlos. A continuación se estudia un
método para crear un árbol binario que no tenga claves repetidas partiendo de su
recorrido en preorden e inorden, almacenados en sendos arrays.
Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es
sencillo cuando uno es capaz de construir el árbol viendo sus recorridos pero sin haber
visto el árbol terminado.
Partiendo de los recorridos preorden e inorden del árbol de la figura 1 puede
determinarse que la raíz es el primer elemento del recorrido en preorden. Ese elemento
se busca en el array inorden. Los elementos en el array inorden entre izq y la raíz
forman el subárbol izquierdo. Asimismo los elementos entre der y la raíz forman el
subárbol derecho. Por tanto se tiene este árbol:
___________________________________________________________________ 17
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
A continuación comienza un proceso recursivo. Se procede a crear el subárbol
izquierdo, cuyo tamaño está limitado por los índices izq y der. La siguiente posición en
el recorrido en preorden es la raíz de este subárbol. Queda esto:
El subárbol b tiene un subárbol derecho, que no tiene ningún descendiente, tal y como
indican los índices izq y der. Se ha obtenido el subárbol izquierdo completo de la raíz
a, puesto que b no tiene subárbol izquierdo:
___________________________________________________________________ 18
Escuela Ingeniería en Computación, Universidad de La Serena
Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
Después seguirá construyéndose el subárbol derecho a partir de la raíz a.
Aplicación:
Se tiene un fichero de texto ASCII. Para este propósito puede servir cualquier libro
electrónico de la librería Gutenberg o Cervantes, que suelen tener varios cientos de
miles de palabras. El objetivo es clasificar todas las palabras, es decir, determinar que
palabras aparecen, y cuantas veces aparece cada una. Palabras como 'niño'-'niña',
'vengo'-'vienes' etc, se consideran diferentes por simplificar el problema.
Escribir un programa, que recibiendo como entrada un texto, realice la clasificación
descrita anteriormente. Ejemplo: Texto: "abac, hola, adios, hola"
La salida que produce es la siguiente:
a2
adios 1
b1
c1
hola 2
Nótese que el empleo de una lista enlazada ordenada no es una buena solución. Si se
obtienen hasta 20.000 palabras diferentes, por decir un número, localizar una palabra
cualquiera puede ser, y en general lo será, muy costoso en tiempo. Se puede hacer una
implementación por pura curiosidad para evaluar el tiempo de ejecución, pero no
merece la pena.
La solución pasa por emplear un árbol binario de búsqueda para insertar las claves. El
valor de log(20.000) es aproximadamente de 14. Eso quiere decir que localizar una
palabra entre 20.000 llevaría en el peor caso unos 14 accesos. El contraste con el
empleo de una lista es simplemente abismal. Por supuesto, como se ha comentado
anteriormente el árbol no va a estar perfectamente equilibrado, pero nadie escribe
novelas manteniendo el orden lexicográfico (como un diccionario) entre las palabras, asi
que no se obtendrá nunca un árbol muy degenerado. Lo que está claro es que cualquier
evolución del árbol siempre será mejor que el empleo de una lista.
Por último, una vez realizada la lectura de los datos, sólo queda hacer un recorrido en
orden central del árbol y se obtendrá la solución pedida en cuestión de segundos.
___________________________________________________________________ 19
Escuela Ingeniería en Computación, Universidad de La Serena