Motivaciones

• El árbol binario de búsqueda permite implementar

Estructuras de Datos conjuntos y mapeos con un tiempo de operaciones
Clase 18 – Árboles de búsqueda buscar, insertar y eliminar con orden logarítmico en la
cantidad de elementos en promedio.
• En el peor caso las operaciones tienen orden lineal en
Dr. Sergio A. Gómez la cantidad de elementos (cuando las inserciones se
[Link] realizaron en forma ascendente o descendente en cuyo
caso el árbol degenera en una lista).
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur • Hay estructuras alternativas que garantizan tiempo de
Bahía Blanca, Argentina acceso de orden logarítmico en la cantidad de
elementos y se los conoce como árboles de búsqueda
balanceados: Árbol AVL, Árbol 2-3 y Árbol B.
Estructuras de datos - Dr. Sergio A. Gómez 2

Árboles AVL: Ejemplo

Árboles AVL • Propiedad del balance de la altura: Para cada nodo interno v de
• Agregaremos una corrección al árbol binario de búsqueda T, las alturas de los hijos difieren en a lo sumo 1.
para mantener una altura del árbol proporcional al
logaritmo de la cantidad de nodos del árbol. • Ejemplo: Los * corresponden a nodos nulos (con altura 0 de
• Recordemos que el tiempo de búsqueda, inserción y acuerdo a GT).
borrado en un árbol binario de búsqueda es lineal en la 4
altura del árbol. 44
• Entonces, si n=cantidad de elementos de un arbol T, 2 17 3 78
tendríamos así que T(n) = O(log2(n)).
• Propiedad del balance de la altura: Para cada nodo interno
v de T, las alturas de los hijos difieren en a lo sumo 1. 0 * 1 32 2 50 1 88
• Cualquier árbol binario de búsqueda que satisface esta
propiedad se dice "árbol AVL" (por Adel'son-Vel'skii y * *
0 * 0 *
1 48 1 62
Landis). 0 0

0 * 0 * 0 * 0 *

Estructuras de datos - Dr. Sergio A. Gómez 3 Estructuras de datos - Dr. Sergio A. Gómez 4
 Comentarios Rotaciones
• Siguiendo a Goodrich & Tamassia diremos que los nodos nulos
tienen altura 0.
• Como un AVL es un árbol binario de búsqueda, la operación de
Son cuatro correspondientes a las cuatro
búsqueda no sufre alteraciones. combinaciones para la inserción de una clave a
• La únicas operaciones a modificar son la de inserción y eliminación, partir de un nodo raíz del subárbol considerado:
las cuales deben verificar que se cumpla la propiedad de balance al
finalizar la operación. 1) izquierda – izquierda: rotación simple de
• Luego de cada modificación en un nodo, rebalancearán los hijos de izquierda a derecha
dicho nodo en O(1) por medio de las llamadas “rotaciones”. 2) izquierda – derecha: Rotación doble de izquierda
• Las modificaciones se hacen desde la hoja donde se insertó el nodo
hacia la raíz siguiendo el camino de llamadas recursivas. a derecha
• Las eliminaciones las haremos perezosas (lazy): marcaremos los 3) derecha – derecha: Rotación simple de derecha
datos eliminados con un booleano. a izquierda
4) derecha – izquierda: Rotación doble de derecha
a izquierda
Estructuras de datos - Dr. Sergio A. Gómez 5 Estructuras de datos - Dr. Sergio A. Gómez 6

Ejemplo de rotación simple de (1) Rotación simple de izquierda a

izquierda a derecha derecha (formalización)
x
5 5
y
y
2 8 2 7
t4
z x
1 4 7 1 4 6 8 z
t3
3 6 3

Antes de rotar Después de rotar

t1 t2
t1 t2 t3 t4
La inserción del 6 destruye la propiedad de AVL en el nodo 8, lo que se resuelve con una
rotación simple de izquierda a derecha (tomado de Mark Allen Weiss, Data Structures Corresponde a dos inserciones seguidas hacia la izquierda desde la raíz
and Algorithm Analysis in Java, Third Edition).
del subárbol considerado
Estructuras de datos - Dr. Sergio A. Gómez 7 Estructuras de datos - Dr. Sergio A. Gómez 8
 Ejemplo de rotación de derecha a (3) Rotación der-der (simple derecha a
izquierda izquierda): Formalización
x
5 5
y
y
2 8 2 9
t1
z z
1 4 1 4 8 10 x
9 t2

3 10 3

Antes de rotar Después de rotar t3 t4

t1 t2 t3 t4
La inserción del 10 destruye la propiedad de AVL en el nodo 8, lo que se resuelve con una
rotación simple de derecha y izquierda. Corresponde a dos inserciones seguidas hacia la derecha de la raíz del
subárbol considerado
Estructuras de datos - Dr. Sergio A. Gómez 9 Estructuras de datos - Dr. Sergio A. Gómez 10

Ejemplo de rotación doble de (2) Rotación izq-der (doble de

izquierda a derecha izquierda a derecha): Formalización
x
5 5
z
y
2 8 2 8
t4
9 9 z y x
1 4 7 1 4 6,5 t1

3 6 3 6 7
t2 t3
6,5
Antes de rotar Después de rotar t1 t2 t3 t4

Corresponde a una inserción en el hijo izquierdo y luego en hijo derecho

La inserción del 6,5 destrute la propiedad de AVL en el nodo 7, entonces hay que rotar.
del hijo izquierdo de la raíz del subárbol considerado
Estructuras de datos - Dr. Sergio A. Gómez 11 Estructuras de datos - Dr. Sergio A. Gómez 12
 Ejemplo de rotación doble de derecha (4) Rotación der-izq (doble de derecha
a izquierda a izquierda)
x
5 5
z
y
2 15 2 15
t1 z
19 19 x y
1 4 8 1 4 9 t4

3 10 3 8 10
t2 t3
9
Después de rotar t1 t2 t3 t4
Antes de rotar
Corresponde a una inserción en el hijo derecho de la raíz y luego en el
La inserción del 9 destrute la propiedad de AVL en el nodo 8, entonces hay que rotar.
hijo izquierdo del hijo derechos de la raíz del subárbol considerado
Estructuras de datos - Dr. Sergio A. Gómez 13 Estructuras de datos - Dr. Sergio A. Gómez 14

Implementación Java de la Inserción public class AVL<E> El árbol AVL está parametrizado con el tipo E de los rótulos
La única diferencia con el NodoABB es que en cada nodo mantengo {
la altura de dicho nodo. NodoAVL<E> raiz; Su raíz es un nodo AVL
// Archivo: [Link] Comparator<E> comp; Necesito el comparador de claves
public class NodoAVL<E>
public AVL(Comparator<E> comp) El cliente me pasa el comparador
{
{
private NodoAVL<E> padre; raiz = new NodoAVL<E>(null); Creo un nodo dummy para la raíz
private E rotulo; [Link] = comp; Salvo el comparador
private int altura; private boolean eliminado; //  }
diferencia!
public void insert(E x) Insertar recorre el árbol recursivamente
private NodoAVL<E> izq, der;
{ desde la raíz con un método auxiliar
insertaux( raiz, x ); llamado insertaux
public NodoAVL<E>(E rotulo){ }
altura = 0;
// Al crear un nodo dummy anoto que su altura es 0. private int max(int i, int j ) Este método sirve para calcular el
{ máximo entre i y j
... // Resto Idem NodoABB}
return i>j ? i : j;
// setters y getters incluyendo la altura y eliminado }
Estructuras de datos - Dr. Sergio A. Gómez 15 Estructuras de datos - Dr. Sergio A. Gómez 16
}
private void insertaux( NodoAVL<E> p, E item ) { /* p es el nodo actual, la primera vez es la raíz */
if( [Link]() == null ) { // Llegué a un dummy
[Link]( item ); [Link]( 1 ); // Le seteo la altura al dummy como 1 y le hago 2 hijos
[Link]( new NodoAVL<E>( null ) ); [Link]( new NodoAVL<E>( null ) ); Complejidad temporal de la inserción
[Link]().setPadre( p ); [Link]().setPadre( p );
} else {
int comparacion = [Link]( item, [Link]() );
if( comparacion == 0 ) { eliminado=false; /* ítem ya está en el árbol => no cambia nada */ }
• Noten que las rotaciones se hacen en los nodos del
else if( comparacion < 0 ) { camino desde la raíz hasta la hoja donde se insertó la
insertaraux( [Link](), item ); // Inserto recursivamente en el HI y a la vuelta rebalanceo nueva clave.
if( [Link]( [Link]().getAltura() - [Link]().getAltura() ) > 1 ) {
// Rebalancear mediante rotaciones: testeo por rotaciones (i) o (ii) • Como las rotaciones se implementan con asignaciones
// Si estoy aca => item < x, debo testear si (item < y) o (item > y) de referencias (posiciones), cada rotación se hace en
// si item < y => rotacion (i); si item > y => rotacion (ii)
E x = [Link](); // no se usa, es solo para la explicación
tiempo constante.
E y = [Link]().getRotulo(); • La cantidad de rotaciones es del orden de la altura del
E z = [Link]().getLeft().getRotulo(); // no se usa, es solo para la explicación
int comp_item_y = [Link]( item, y );
árbol.
if( comp_item_y < 0 ) rotacion_i(p); // item < y => rotacion (i) • La altura es proporcional al logaritmo de la cantidad de
else rotacion_ii(p); // item > y => rotacion (ii)
}
nodos del árbol.
} else { • Por lo tanto, el tiempo de insertar es del orden del
/* Caso simétrico pero insertando hacia la derecha y luego testeo por rotaciones (iii) y (iv) */
}
logaritmo de la cantidad de nodos del árbol.
[Link]( max([Link]().getAltura(), [Link]().getAltura()) + 1 ); // Setear altura del nodo p
}
Estructuras de datos - Dr. Sergio A. Gómez 17 Estructuras de datos - Dr. Sergio A. Gómez 18
}

¿Por qué la altura del AVL es O(log(n))?

Como la diferencia de altura de los hijos de un nodo de un AVL es a lo sumo 1, se
cumple que la cantidad Nh de nodos de un árbol de altura h en el peor árbol
Árboles 2-3: Definiciones
desbalanceado se define recursivamente como (ver Fig. 1): Un "árbol 2-3" es un árbol tal que cada nodo interno (no hoja)
Nh = 1 + Nh-1 + Nh-2. tiene dos o tres hijos, y todas las hojas están al mismo nivel.
Esta recurrencia se parece a Fibonacci: La definición recursiva es: T es un árbol 2-3 de altura h si:
F0=0, F1=1, Fi=Fi-1+Fi-2 para i≥2. a) T es vacío (es decir de altura 0)
Sea F = = 1,6180… conocido como la razón dorada o número aúreo. b) T es de la forma:
Se puede demostrar que
n donde n es un nodo y Ti y Td son árboles 2-3
Nh = Fh+2 – 1 = {( )h+2 – ( )h+2} -1  Fh+2-1 cada uno de altura h-1.
Ti se dice "subárbol izquierdo" y Td "subárbol
Nh = Fh+2-1 => Nh + 1 = Fh+2 => log(Nh+1) = log( Fh+2 ) =>
Ti Td derecho".
log(Nh+1) = log( Fh+2 ) => log(Nh+1) = (h+2)logF −
( ) F c) T es de la forma:
 ℎ=
F n donde n es un nodo y Ti, Tm y Td son árboles 2-3
( ) .
 ℎ=
.
cada uno de altura h-1.
 h =O(log(Nh)) Ti se dice "subárbol izquierdo“, Tm se dice
Ti Tm Td "subárbol medio“ y Td "subárbol derecho".
Estructuras de datos - Dr. Sergio A. Gómez 19 Estructuras de datos - Dr. Sergio A. Gómez 20
 Árboles 2-3: Definiciones Árboles 2-3: Definiciones
Un arbol 2-3 es un "arbol 2-3 de búsqueda" si T es un árbol 2-3
tal que
• Propiedad: Si un árbol 2-3 no contiene ningún a) T es vacío
nodo con 3 hijos entonces su forma b) T es de la forma:
corresponde a un árbol binario lleno. n contiene una clave k, y
k k es mayor que las claves de Ti
k es menor que las claves de Td
Ti y Td son árboles 2-3 de búsqueda
Ti Td

c) T es de la forma: n contiene dos claves k1 y k2, y

k1 k2 k1 es mayor que las claves de Ti,
k1 es menor que las claves de Tm
k2 es mayor que las claves de Tm
k2 es menor que las claves de Td
Ti Tm Td
Ti, Tm y Td son árboles 2-3 de búsqueda
Estructuras de datos - Dr. Sergio A. Gómez 21 Estructuras de datos - Dr. Sergio A. Gómez 22

Árboles 2-3: Definiciones Ejemplo de árbol 2-3

Reglas para ubicar claves en los nodos de un árbol 2-3 50 90

de búsqueda:
1) Si n tiene dos hijos, entonces contiene una clave
2) Si n tiene tres hijos, entonces contiene dos claves 20 70
120 150
3) Si n es una hoja, entonces contiene una o dos claves

10 30 40 60 80 100 110 130 140 160

Estructuras de datos - Dr. Sergio A. Gómez 23 Estructuras de datos - Dr. Sergio A. Gómez 24
 Recuperar( R, clave ) : boolean Inserción en un árbol 2-3:
SI clave está en R ENTONCES
RETORNAR true • Igual que en el ABB, siempre se inserta en una hoja siguiendo el
SINO SI R es una hoja ENTONCES camino de la búsqueda desde la raíz del árbol hasta la hoja
RETORNAR false Búsqueda en un árbol 2-3 correspondiente (esa hoja ya va a tener por lo menos 1 clave).
SINO
SI R tiene una clave k ENTONCES
• Si la hoja ahora tiene 2 claves, terminamos.
SI clave < k ENTONCES RETORNAR Recuperar( Ti(R), clave ) • Si la hoja ahora tiene 3 claves, se produce un rebalse (overflow) y se
SINO RETORNAR Recuperar( Td(R), clave ) debe partir el nodo en 2 nodos, la clave del medio sube al padre,
SINO quien queda a cargo de administrar ese hijo que se duplicó y ver
SI R tiene dos claves k1 y K2 ENTONCES
SI clave < k1 ENTONCES dónde ubicar esa clave.
RETORNAR Recuperar( Ti(R), clave ) • Si el padre tenía 1 clave y 2 hijos, no hay problema, porque ahora
SINO SI clave < k2 ENTONCES tendrá 2 claves y 3 hijos.
RETORNAR Recuperar( Tm(R), clave )
SINO • Si el padre ya tenía 2 claves y 3 hijos, ahora pasaría a tener 3 claves y
RETORNAR Recuperar( Td(R), clave ) 4 hijos, lo cual no puede ocurrir. Entonces el proceso anterior se
repite.
• El proceso termina cuando terminamos en un nodo intermedio (con
2 claves o 3 hijos) o llegamos a crear una nueva raíz y el árbol crece 1
nivel.
Estructuras de datos - Dr. Sergio A. Gómez 25
• Como esteEstructuras
procesode datos - Dr. Sergio A. Gómez
tiene T(h) = O(h), ocurre que T(n) = O(log(n)). 26

1) Insertamos 10 en el árbol vacío: 4) Cualquier clave que inserte, siempre va a una hoja siguiendo el criterio de búsqueda.
Inserto 20 y 5. Como no hay rebalse porque había lugar en las hojas, terminamos.

10
12 12
2) Insertamos 15: como hay lugar en la única hoja, allí ponemos la nueva clave y
terminamos 10 15 5 10 15 20
10 15

5) Inserto 30, el cual termina en el hijo derecho de 12.

3) Insertamos 12: vamos a la única hoja y ponemos el 12 allí, pero hay rebalse porque
tenemos 3 claves y sólo tenemos permitidas 2. 12 12 20
12 12
10 12 15
5 10 15 20 30 5 10 15 30
10 15 10 15
Hay rebalse porque Parto el nodo rebalsado en 2 nodos y
Partimos el nodo en 2 nodos dividiendo las claves y le pasamos al padre los 2 tengo 3 claves y solo se los paso a su padre junto con la
nodos junto con la clave del medio. Como no hay padre, el árbol crece en un tengo permitidas 2 clave del medio (que es el 20) y
nivel al crear un nuevo nodo para acomodar la clave con los 2 nodos como sus terminamos porque la raíz tiene lugar
hijos. para otra clave y otro hijo extra.
Estructuras de datos - Dr. Sergio A. Gómez 27 Estructuras de datos - Dr. Sergio A. Gómez 28
6) Inserto 1 en el árbol del paso (5): RESUMEN:
Para insertar un valor X en un árbol 2-3,
12 20 12 20 primero hay que ubicar la hoja L en la cual X terminará.
Si L contiene ahora dos claves, terminamos.
Si L contiene tres claves, hay que partirla en dos hojas
5 10 15 30 1 5 10 15 30 L1 y L2. L1 se queda con la clave más pequeña, L2 con la
más grande, y la del medio se manda al padre P de L.
Hay rebalse Los nodos L1 y L2 se convierten en los hijos de P.

Si P tiene sólo 3 hijos (y 2 claves), terminamos.

12 En cambio, si P tiene 4 hijos (y 3 claves), hay
que partir a P igual que como hicimos con una hoja
5 20
sólo que hay que ocuparse de sus 4 hijos. Partimos a P
5 12 20
en P1 y P2, a P1 le damos la clave más pequeña
y los dos hijos de la izquierda y a P2 le damos
1 10 15 30 1 10 15 30 la clave más grande y los dos hijos de la derecha.
Parto el nodo y subo el 5 al padre (que es la raíz). Parto el nodo raíz en 2 nodos
Luego de esto, la clave que sobra se manda al padre de P
Pero ahora la raíz tiene rebalse (3 claves y 4 hijos, y subo el 12 creando una
nueva raíz
en forma recursiva. El proceso termina cuando la clave
situación no permitida).
sobrante termina en un nodo con dos claves o el árbol crece
1 en altura (al crear una nueva raíz).
Estructuras de datos - Dr. Sergio A. Gómez 29 30

Archivos Indizados (o indexados)

• Noción: Los archivos indexados tienen un orden virtual determinado Implementaciones para el índice
por el ordenamiento de una clave (en nuestro ejemplo hay dos
índices, uno con el nombre de la persona y otro con el DNI). • Arreglo ordenado
• Implementación: Por cada tabla, hay al menos dos archivos: – Búsqueda en orden logarítmico
– Actualizaciones implican reordenar el arreglo en orden nlog(n) o hacer
– Un archivo de datos donde cada registro tiene tamaño fijo inserción ordenada en O(n)
– Un archivo de índice: Un mapeo de clave en número de registro • Árbol binario de búsqueda:
– Puede degenerar en orden lineal para buscar y actualizar pero se espera orden
(contiene además la cantidad de registros del archivo de datos) logarítmico
– Cada clave extra de búsqueda requiere otro índice (pero no otro • AVL, 2-3:
– Buscar y actualizar en orden logarítmico
archivo de datos, ej: buscar/ordenar alumnos por legajo, dni,
• Árbol B y B+
nombre, etc). – Para grandes volúmenes de datos las opciones anteriores no son viables ya
Indice_DNI = { 34 -> 0, 55 -> 1, 44 -> 2, 12 -> 3, 03 -> 4, 22 -> 5, 8 -> 6 } que no entran en RAM y el acceso al disco es del orden de los milisegundos
Indice_nombre = { Sergio -> 0, Martin -> 1, Matías -> 2, Juan -> 3, Tito -> 4, María -> 5, Pablo->8} contra el acceso a la RAM que es del orden de los nanosegundos
– El árbol B generaliza la idea del árbol 2-3 con un gran número M de claves en
0 1 2 3 4 5 6 cada nodo
– El árbol B+ almacena entradas (clave,valor) sólo en las hojas, los nodos
datos Sergio 34 Martin 55 Matías 44 Juan 12 Tito 03 María 33 Pablo 8 internos almacenan solo claves que sirven para guiar la búsqueda.

Estructuras de datos - Dr. Sergio A. Gómez

datos es de tipo RandomAccessFile que permite accede a 31
los Estructuras de datos - Dr. Sergio A. Gómez 32
registros por posición.
 Árbol B Arboles B (o M-arios de búsqueda)
• Un árbol-B (B-tree) es un árbol balanceado (o auto- • Los árboles B se optimizan para manejar grandes volúmenes
balanceante) que mantiene los datos ordenados y permite de datos.
realizar búsquedas, inserciones y eliminaciones en tiempo • Los árboles B se almacenan en disco y el tamaño del nodo
logarítmico. coincide con un múltiplo entero del tamaño del sector del
• Se puede ver también como una generalización del árbol 2-3 disco.
porque sus nodos pueden tener más de tres hijos. • Se utilizan para implementar índices en bases de datos.
• El grado de ramificación d del árbol es un entero, indicando
• A diferencia de los árboles 2-3, el árbol-B está optimizado que un nodo tiene entre d y 2d claves y entre d+1 y 2d+1
para sistemas que leen y escriben grandes bloques de datos. hijos (excepto la raíz que puede tener menos de d claves y
• Los árboles-B son un buen ejemplo de una estructura de tiene por lo menos 1 clave y 2 hijos).
datos para memoria externa (en disco) y se usan • Cuando d=1 tenemos un árbol 2-3.
comúnmente en bases de datos y sistemas de archivos. • Dependiendo de la formalización, al número 2d+1 se lo
llama M (i.e. tenemos M-1 claves y M hijos a lo sumo por
nodo; en un árbol 2-3, M vale 3)
Estructuras de datos - Dr. Sergio A. Gómez 33 Estructuras de datos - Dr. Sergio A. Gómez 34

Árbol B Árboles B: Inserción

• Comenzamos con un nodo vacío (el cual funciona como

un arreglo ordenado).
• Las claves se insertan (en forma lineal y ordenada) en el
nodo hasta tener a lo sumo 2d = m-1 claves.
• Luego, al insertar la siguiente clave, el nodo rebalsa.
El tiempo de búsqueda, inserción y eliminación es en tiempo
logarítmico puesto que es del orden de la altura del árbol. • El nodo se parte en dos (cada uno con d claves): la clave
Si d=1000, cada nodo tiene d claves y d+1 hijos por lo menos, del medio va al nodo de arriba (incrementando la altura
entonces la altura del árbol es del orden logd(n) con n = cantidad de del árbol cuando tal nodo de arriba no existiera) y los
claves del árbol.
nodos que quedan se quedan cada uno con la mitad de
Ej: si d=1.000 y n=1.000.000, entonces logd(1.000.000)=2 entonces
son 3 lecturas (como la altura es 2, el camino tiene 3 nodos). las claves menores a d y mayores a d respectivamente.
Generalmente hay espacio desperdiciado en los nodos (i.e.
fragmentación interna).
Estructuras de datos - Dr. Sergio A. Gómez 35 Estructuras de datos - Dr. Sergio A. Gómez 36
 Estado antes de insertar 9: Al insertar 9, ¡se produce un rebalse!
Supongamos que d=3, entonces tendremos entre d=3 y 2d=6 claves por nodo excepto la
raíz que puede tener menos claves (es decir, M=2d+1=7, el B-árbol es de orden 7) y
1 3 5 8 40 45 1 3 5 8 9 40 45
siempre el número de hijos de un nodo es uno más que su cantidad de claves.
Insertemos las claves 1, 40, 5, 3, 45, 8, 9.
Inserto 1: Inserto 40:
Entonces partimos el nodo L en L1 y L2 y creamos un nodo más arriba con L1 y L2
1 1 40 como hijos y como clave la clave del medio de L considerando también al 9, que en
este caso será el 8:

Inserto 5 (hago shift): Inserto 3 (hago shift):

8
1 5 40 1 3 5 40

Inserto 45: Inserto 8:

1 3 5 40 45 1 3 5 8 40 45
1 3 5 9 40 45

La próxima inserción, es decir la del

9, producirá un rebalse porque el L1 L2
nodo ya está lleno.
Estructuras de datos - Dr. Sergio A. Gómez 37 Estructuras de datos - Dr. Sergio A. Gómez 38

Las inserciones se hacen siempre en las hojas siguiendo el orden de las claves. Estado al insertar el 2: 8
Para insertar una clave, habrá que ver si es menor o mayor a la clave de la raíz.
Insertar 10, 4, 30, 7, 6, 90 produce el árbol:

1 2 3 4 5 6 7 9 10 30 40 45 90
8
Rebalsó el 7, vamos a partir nodo reabalsado en dos y mandar la clave del medio
(es este caso 4) al padre:

4 8

1 3 4 5 6 7 9 10 30 40 45 90

1 2 3 5 6 7 9 10 30 40 45 90

¡Insertar el 2 producirá un rebalse en la hoja de la izquierda!

Insertar 100 producirá un rebalse en la hoja de más a la derecha.
El espacio desperdiciado en los arreglos constituye la fragmentación interna (espacio de
memoria desperdiciado dentro de las estructuras de datos).

Estructuras de datos - Dr. Sergio A. Gómez 39 Estructuras de datos - Dr. Sergio A. Gómez 40
 Estado antes de
insertar el 100:
4 8 Árboles B: Búsqueda de k

1 2 3 5 6 7 9 10 30 40 45 90

Al insertar el 100, como 100 > 8, va hacia la hoja de más a la derecha, que
rebalsa. Entonces la partimos y subimos la clave del medio (en este caso el 40):

4 8 40 • Empezamos a buscar a partir del nodo p=raíz.

• CB: Si k está en p => termino con éxito.
45 90 100 • CB: Si k es una hoja y k no está en p => fallamos.
• CR: Si k no está en p, buscamos k en el hijo entre
1 2 3 5 6 7 9 10 30
las dos claves ki y ki+1 de p tales que ki ≤ k ≤ ki+1.
Este proceso continúa hasta que los rebalses sucesivos en las hojas van llenando la raíz • Ej: Para buscar el 6, hay que ramificar en el hijo
del árbol. En el siguiente rebalse, se partirá la raíz en 2 y se crea una nueva raíz que está entre las claves 4 y 8.
haciendo crecer el árbol en un nivel.
Estructuras de datos - Dr. Sergio A. Gómez 41 Estructuras de datos - Dr. Sergio A. Gómez 42

Variante del árbol B: Árbol B+

Bibliografía
• Árboles AVL: Capítulo 10, Secciones 2 y 4 de M. Goodrich & R. Tamassia,
Data Structures and Algorithms in Java. Fourth Edition, John Wiley & Sons,
2006.
• Árboles 2-3: Basado en Paul Helman & Robert Veroff. Intermediate
Problem Solving and Data Structures. Walls and Mirrors, Benjamming
Cummings, Menlo Park, 1986.
El árbol B+ almacena entradas (clave,valor) sólo en las hojas, los • Árboles B: Capítulo 14, Sección 3 de M. Goodrich & R. Tamassia, Data
nodos internos almacenan solo claves que sirven para guiar la Structures and Algorithms in Java. Fourth Edition, John Wiley & Sons,
búsqueda en O(h). 2006.
Recorrer las hojas de izquierda a derecha iterativamente permite • Justificación performance AVL:
listar las claves en forma ascendente en O(n). [Link]
[Link]
Ejemplo: 3 en la raíz indica la mayor clave del primer hijo del
[Link]
siguiente nivel. [Link]?m=1
5 en la raíz indica la mayor clave del segundo hijo del siguiente nivel. [Link]
d1, d2, d3, d5, d6, d7 corresponden a los valores de las entradas para
las claves 1,2,3,4,5,6,7 (punteros al archivo de datos).
Estructuras de datos - Dr. Sergio A. Gómez 43 Estructuras de datos - Dr. Sergio A. Gómez 44