Árboles binarios
• Si a partir de n claves se
construye un árbol binario de
búsqueda de altura mínima se
obtiene un árbol de log2n ñ
niveles.
• Las operaciones de búsqueda, h r
inserción y extracción
requieren un tiempo de g k o x
O(log2n).
Árboles binarios
• Si la única consideración a tener en cuenta es la de
“menores a la izquierda y mayores a la derecha”, la
altura del árbol puede degenerar hasta n.
g g
k r
x
k
r
o
o
ñ ñ
Definición del árbol biselado
Es un árbol binario de búsqueda
Cualquier operación requiere un esquema de
reestructuración denominado biselación
El esquema de biselación consiste en:
Desplazar un nodo hasta la raíz del árbol biselado
Mediante una secuencia de rotaciones
Objetivo: reducir el tiempo de búsqueda de
cada valor de clave
Se sitúan los nodos más frecuentemente solicitados
en torno a la raíz del árbol.
Relación con los árboles binarios equilibrados
El objetivo de los árboles AVL y Rojo-Negro es
asegurar que el árbol nunca se desequilibre
Garantizan que el tiempo de búsqueda de un valor de clave
individual nunca requiere más de O(lg2 n)
• Los árboles biselados pueden necesitar un tiempo de O(n)
– Aseguran que este comportamiento no se va a producir de forma
repetida
– No precisan de ningún tipo de información de equilibrio adicional
en cada nodo
Rotaciones
• En los esquemas, la biselación se realiza sobre el
nodo u, su padre -el nodo p- y su abuelo –el nodo b.
• Los tipos de rotaciones a utilizar
son:
b b
p p p
4 4
u u u
3 1 3
1 2 2 3 1 2
Rotación Simple Rotación Doble Rotación Doble Inversora
Rotación Simple
• Las rotaciones I y D son simétricas.
p p
u p p
u
u u D
u 3 p p 1 3 u
I
3 1 1
1 2 1 2 2 3 2 3 1 2 2 3
u es hijo izquierdo de p u es hijo derecho de p
• Intercambian la relación padre-hijo y sitúan el
subárbol central de forma que cumpla la condición de
árbol binario de búsqueda.
Rotación Simple en Java
protected NodoBinario rotaciónSimple(NodoBinario nodo, int rama) {
//Se intercambian los nodos
NodoBinario hijo = [Link][rama];
int otraRama = 1 - rama;
[Link][rama] = [Link][otraRama];
[Link][otraRama] = nodo;
return hijo;
}
nodo
A B
nodo| hijo B
A
I
T3
T1’ T2
T1’ T2 T3
Rotación Doble
b b
u
p p 4 b
ID
4
Modifican relaciones 1 u 1 u 2 3 4
abuelo-padre-hijo
y sitúan los dos
subárboles centrales de
2 3 2 3
u es hijo derecho de p
forma que cumplan con
la condición de b b
u
árbol binario de p
DI
búsqueda. p b 1
1
u 4 1 2 u 3 4
2 3
2 3 u es hijo izquierdo de p
Una rotación doble equivale a dos simples
• Consiste en efectuar la rotación simple D
al nivel del padre inicial...
b b
p 4 u u
4
u D p I p b
1 3
2 3 1 2 1 2 3 4
• ... y después la I a nivel del abuelo del subárbol
intermedio
nodo
A
hijo
Rotación Doble en Java
B
nieto
C nodo
protected NodoBinario rotaciónDoble(NodoBinario nodo, int rama) {
//Se intercambian los nodos
NodoBinario hijo = [Link][rama];
int otraRama = 1 - rama;
NodoBinario nieto = [Link][otraRama]; T4
[Link][rama] = [Link][otraRama];
[Link][otraRama] = [Link][rama];
T1 T2’ T3
[Link][otraRama] = nodo;
[Link][rama] = hijo;
return nieto;
}
B A
T3
T1 T2’ T4
Rotación Doble inversora
(u es hijo izquierdo
de p)
b u b
p p
4 1 4
u u
3 II 2 3 b
1 2 1 2 3 4
• Se efectúan dos rotaciones simples I consecutivas
– Se obtiene una situación inversa a la de partida
Rotación Doble inversora
(u es hijo derecho de
p)
b b u
p p
1 1 4
DD
2 u b 2 u
3
3 4 1 2 3 4
Se efectúan dos rotaciones simples D
consecutivas
nodo
A
hijo
B
Rotación DobleInversora en Java nieto
C nodo
protected NodoBinario rotaciónDobleInversora( NodoBinario nodo,
int rama) {
//Se intercambian los nodos
NodoBinario hijo = [Link][rama]; T3 T4
int otraRama = 1 - rama; T2’
NodoBinario nieto = [Link][rama];
[Link][rama] = [Link][otraRama];
[Link][rama] = [Link][otraRama];
T1
[Link][otraRama] = hijo;
[Link][otraRama] = nodo;
C
return nieto;
}
B
T1 T2
T3 T4
Proceso de biselación
• En cada paso se realiza una rotación
• La rotación simple actúa sólo cuando el nodo en el
que se desea biselar es hijo de la raíz del árbol.
• Las rotaciones doble o doble inversora se
aplican cuando existe el abuelo del nodo en el que se
que desea biselar.
• Se elige una u otra (doble o doble inversora) en función
del camino del abuelo al nodo.
Proceso de biselación
g g
k k
h x h x
DD
ñ r
T ñi o ¿Tiene o T rd
abuelo?
r ñ
T o T ri
i
¿rotación doble o
doble inversora?
T ri T ñi Toi
T rd
roceso de biselación en el nodo r
g
Proceso de biselación
k g
rotación
doble
r
h x
r DI k x
o T rd
h o T rd
ñ ñ T ri
Ti
r
T ñi Toi
T ñ
i T o
i
oceso de biselación en el nodo r
Proceso de biselación
rotación simple
g r
r g x
D
k x k T rd
h o T rd h o
ñ T ri ñ T ri
T ñi Toi
T ñi Toi
Proceso de biselación en el nodo r
Búsqueda
• El descenso por el árbol es igual que en el árbol
binario de búsqueda.
• Si se encuentra un nodo u con el valor de clave
buscado.
– El árbol se bisela en u.
• Si no
– El árbol se bisela en el último nodo visitado.
La búsqueda modifica el árbol
• El camino recorrido en la biselación es el inverso del
seguido durante el descenso por el árbol.
• El tiempo de búsqueda es proporcional al recorrido.
– ¡Ojo, puede llegar a O(n)!, aunque no de forma repetida.
Búsqueda del valor de clave x
g x
rotación
doble inversora
Tg i k k Txd
¿Tiene
abuelo?
h x g ñ
DD
Th i Th d ñ T x
d
Tg i
h m o
m o
Th i Th d T ji To i r
T ji To i r
Tr i Tr d
Tr i
Proceso de biselación en el nodo x
Tr d
Inserción
• Funciona de forma similar a un árbol binario de
búsqueda.
– Se alcanza el árbol vacío.
– Se añade el nuevo nodo al árbol.
• Se realiza la biselación sobre el nuevo
nodo.
• Si el valor de clave a insertar existe en el
árbol.
– Se bisela en el nodo que lo contiene.
Extracción
• La extracción es la operación más complicada
– Requiere dos biselaciones
• Se busca el nodo S que contiene el valor de clave a
extraer
– Si no se encuentra, se bisela en el último nodo examinado
– Si sí se encuentra, se bisela en el nodo S
s
Ti Td
– y se elimina S s
– Se obtienen dos árboles separados
Ti Td
Ti Td
Para unir de nuevo los dos árboles se reorganiza uno de ellos
O se bisela en el nodo con el máximo valor de clave del árbol
izquierdo.
• Tal nodo se sitúa en la raíz del árbol izquierdo
• es el Predecesor en orden simétrico del valor de clave del
nodo S
Predeces
or
•no tiene hijo Ti Ti’
derecho
• La unificación de los dos árboles se completa situando la raíz
del árbol derecho como hijo derecho de la nueva raíz del árbol
izquierdo
Predeces
or
Ti’ Td
O se bisela en el nodo con el mínimo valor de clave del árbol
derecho, cuando el árbol izquierdo está vacío.
Extracción del valor de clave ñ
x ñ
k Txd k x
¿Tiene
abuelo?
g ñ g m o Txd
ID
Tg i h T ji To i r
Tg i h m o
Th i Th d Tr i Tr d
T h
i
Th d T ji To i r
Tr i Tr d
Proceso de biselación en el nodo ñ
Extracción del valor de clave ñ
El árbol de la derecha se
ñ
m encadena a m como subárbol
derecho
k x
g m
T
j
i
o Txd
Eliminación
del nodo
Tg i h T ji To d r
Th i Th d Tr i Tr d
Se obtienen dos árboles separados
Se bisela en m (máximo valor de clave del árbol
izquierdo)
Árboles binarios de búsqueda equilibrados
Representan una buena solución a la degeneración de
un árbol de búsqueda.
Son árboles autoajustables con cota logarítmica de
altura.
La estructura debe reorganizarse en cuanto las
inserciones y extracciones transgredan el equilibrio.
Las operaciones de mantenimiento deben garantizar un
tiempo de O(lg2 n).
El quid radica en introducir Árboles Biselados
binarios de
cierta holgura búsqueda
Los nodos rojos en los árboles Rojo-Negro Árboles autoajustables AVL
Los nodos con un desequilibrio de altura
Árboles equilibrados
de una unidad en los árboles AVL
Rojo-Negro
Implementación en Java de un
contenedor con un árbol biselado
Se parte de la interfaz ContenedorOrdenado y de su
implementación ÁrbolBinarioBúsqueda que se
extiende a la clase ÁrbolBinarioAjustable (que define
las rotaciones como los métodos comunes a todos los
ajustables); por último se deriva la clase
ÁrbolBiselado que implementa los métodos
apropiados sin añadir ningún campo.
El método está de ÁrbolBinarioBúsqueda define la
operación de pertenencia sin modificar el árbol, es
necesario redefinir este método para que se adapte a
las características del árbol biselado.
Esquema de clases
public class ÁrbolBinarioBúsqueda implements ContenedorOrdenado {
public interface ContenedorOrdenado { protected int numElem;
public void insertar(Comparable e); protected NodoBinario raíz;
public void extraer(Comparable e); public void insertar(Comparable valor);
public boolean está(Comparable e); public void extraer(Comparable valor);
public void vaciar(); public void vaciar();
public boolean esVacío(); public boolean está(Comparable valor);
public int tamaño(); public boolean esVacío();
} public int tamaño();
}
Interfa
z
public class ÁrbolBinarioAjustable extends ÁrbolBinarioBúsqueda {
Clase que extiende Implementa la interfaz
protected NodoBinario rotaciónSimple(NodoBinario nodo,int rama);
ÁrbolBinarioAjustable y ContenedorOrdenado
protected y
NodoBinario rotaciónDoble(NodoBinario nodo,int rama);
proporciona las proporciona la estructura de
protected NodoBinario rotaciónDobleInversora(NodoBinario nodo,int rama);
}
operaciones específicas arbol binario y sus
del árbol biselado operaciones básicas
Extensión de la Resuelve insertar, extraer,
clase vaciar y todas las operaciones
ÁrbolBinarioBúsqu observadoras
public class
eda ÁrbolBinarioAjustable {
Biselado extends
public void insertar(Comparable valor);
public void extraer(Comparable valor); Aporta los
public void está(Comparable valor); mecanismos de
} rotación para los
árboles binarios
autoajustables
Clase ÁrbolBiselado
public class ÁrbolBiselado extends ÁrbolBinarioAjustable implements ContenedorOrdenado {
private class EnteroMutable { ... } Clase auxiliar
private NodoBinario raíz; Realiza un paso de biselación
public ÁrbolBiselado() {
Constructor
super();
Bisela el nodo con el mayor o el menor valor de
raíz = null;
} clave de un árbol dependiendo del valor de rama
private NodoBinario bisela( NodoBinario nodo, int rama, Comparable valor, EnteroMutable niveles) {...}
private NodoBinario biselaSubárbol( NodoBinario nodo, int rama, EnteroMutable niveles) { ... }
private NodoBinario insertar( NodoBinario nodo, Comparable valor, EnteroMutable niveles) { ... }
Métodos
privados
Añade el elemento al contenedor, si no está.
En cualquier caso, se bisela en él.
private NodoBinario está( NodoBinario nodo, Comparable valor, EnteroMutable niveles) { ... }
Método está específico: modifica el árbol.
public void insertar(Comparable valor) { ... }
Devuelve la referencia del nodo encontrado
Métodos
públicos
public void extraer(Comparable valor) { ... }
public boolean está(Comparable valor) { ... }
Extrae el valor del contenedor. Si está, realiza sus dos biselaciones
propias; si no está, bisela en el último nodo accedido.
}
Clase ÁrbolBiselado: clase auxiliar EnteroMutable
private class EnteroMutable {
Permite tener un entero como parámetro de entrada/salida
int entero;
public EnteroMutable() {
entero = 0;
}
public void incrementar(){
entero++;
}
public void decrementar(){
entero--;
}
public int valor(){
return entero;
}
public void ponerValor(int n){
entero = n;
}
}
Clase ÁrbolBiselado: está (privado)
Devuelve la referencia del nodo que contiene el valor de clave buscado, nulo si no
existe
private NodoBinario está(NodoBinario nodo, Comparable valor, EnteroMutable niveles) {
int rama;
O alcanza
if (nodo == null) { Indica al llamador el número de niveles que se tiene que
un nulo
niveles = ponerValor(2); ascender para aplicar una rotación doble o
} dobleInversora
else { O encuentra el valor buscado
if ([Link]([Link]) == 0) {
niveles = ponerValor(1);
} La búsqueda continúa en abuelo abuelo
else { el subárbol adecuado
if ([Link]([Link]) < 0)
niveles = 1
niveles = 2
rama = 0;
else En caso de no cumplirse ninguna de las
dos condiciones, se llama de manera
rama = 1;
recursiva en el subárbol apropiado
[Link][rama] = nodo nodo
está([Link][rama], valor, niveles);
// El nodo actual se bisela un paso
nodo = bisela(nodo, rama, valor, niveles); Nodo a biselar
}
}
return nodo; valor
} Nulo
Nodo a biselar
Clase ÁrbolBiselado: insertar (privado)
Devuelve la referencia del nodo resultante de insertar el valor de clave, si ya se encuentra bisela el último accedido
private NodoBinario insertar(NodoBinario nodo, Comparable valor, EnteroMutable niveles) {
int rama;
if (nodo == null) { O alcanza un nulo y valor se inserta como
nodo = new NodoBinario(valor); hoja
numElem++;
niveles = ponerValor(1);
} O encuentra el valor buscado y valor no se inserta
else {
if ([Link]([Link]) == 0) {
niveles = ponerValor(1); En caso de no cumplirse abuel
} ninguna de las dos o
else { condiciones, se llama de
if ([Link]([Link]) < 0)
rama = 0;
manera recursiva en el
niveles = 1
else subárbol apropiado
rama = 1;
[Link][rama] = insertar([Link][rama], valor, niveles);
// El nodo actual se bisela un paso
nodo = bisela(nodo, rama, valor, niveles);
}
}
return nodo; nodo
}
valor
Nulo
Nodo a
biselar
Clase ÁrbolBiselado: bisela (privado)
niveles indica el número de ascensos necesario para realizar una rotación doble o doble inversora sobre nodo,
según el hijo que indica rama y el nieto deducido de valor. Si se llega antes a la raíz se hace una rotación simple
sobre nodo, según el hijo que indica rama
private NodoBinario bisela(NodoBinario nodo, int rama, Comparable valor, EnteroMutable niveles){
int ramaDos;
NodoBinario hijo; Nivel de la raíz y no existe abuelo: Rotación simple
if ((nodo == raíz) && ([Link]() > 0))
if ([Link][rama] != null) nodo = rotaciónSimple(nodo, rama);
else { Se asciende un nivel por no
if ([Link]() > 0) [Link](); haber alcanzado el abuelo
else {
hijo = [Link][rama]; Es el abuelo porque niveles=0
if ([Link]([Link]) < 0)
ramaDos = 0;
else La posición valor respecto de nodo y de hijo (abuelo
ramaDos = 1; y padre) condiciona el tipo de rotación
if (rama == ramaDos)
nodo = rotaciónDobleInversora(nodo, rama);
else
nodo = rotaciónDoble(nodo, rama);
[Link](1);
}
}
return nodo;
}
Clase ÁrbolBiselado: extraer (público)
Extrae el valor del contenedor: Si está, realiza sus dos biselaciones propias.
Si no está, bisela en el último nodo accedido.
public void extraer(Comparable valor) { está localiza valor y lo bisela,
EnteroMutable niveles = new EnteroMutable(); si no lo encuentra bisela el
NodoBinario hijo, otroHijo; último nodo accedido
raíz = está(raíz, valor, niveles);
if ((raíz != null) && ([Link](raí[Link]) == 0)) {
hijo = raí[Link][0];
otroHijo = raí[Link][1]; Si se encontró, se biseló a la raíz, entonces
numElem--; se elimina la raíz y se tratan sus
if (otroHijo != null) { subárboles
raíz = otroHijo;
Se bisela el sucesor en orden simétrico
raíz = biselaSubárbol(otroHijo, 0, niveles);
raí[Link][0] = hijo; del valor de clave extraído
}
else { Como no existe el sucesor, se bisela el
raíz = hijo; predecesor
raíz = biselaSubárbol(hijo, 1, niveles);
}
}
}
Clase ÁrbolBiselado: biselaSubárbol (privada)
Bisela en el nodo con menor valor de clave, rama=0, o en el nodo con mayor valor de
clave, rama=1, del árbol de raíz nodo
private NodoBinario biselaSubárbol( NodoBinario nodo, int rama, EnteroMutable niveles ) {
if (nodo == null)
[Link](2); Descenso por la misma rama
else {
[Link][rama] = biselaSubárbol([Link][rama], rama, niveles);
if (nodo == raíz && [Link]() > 0)
if ([Link][rama] != null) Nivel de la raíz y no existe abuelo: Rotación simple
nodo = rotaciónSimple(nodo, rama);
else Asciende otro nivel
if ([Link]() > 0) [Link]();
else {
nodo = rotaciónDobleInversora(nodo, rama); Existe abuelo porque niveles=0
[Link](1);
}
}
return nodo; Se aplica rotación doble inversora porque se
} ha descendido siempre por la misma rama
Clase ÁrbolBiselado: insertar, está y vaciar (públicos)
public void insertar(Comparable valor) { Invoca a insertar (privado) con niveles a 0
EnteroMutable niveles = new EnteroMutable();
raíz = insertar(raíz, valor, niveles);
}
Invoca a está (privado) con niveles a
public boolean está(Comparable valor) {
0
EnteroMutable niveles = new EnteroMutable();
raíz = está(raíz, valor, niveles);
if ((raíz != null) && ([Link](raí[Link]) == 0))
return true;
else
return false;
}
