Los árbolesson estructuras que organizan sus elementos de forma jerarquizada en forma de nodos, de manera que existe un nodo raiz del cual nacen otros nodos (hijos) de un nodo padre. Esta estructura se usa para expresar relaciones donde exista una jerarquía, de forma eficiente
💡
Un nodo puede tener 0 o más hijos, pero solo 0 o 1 padre.
Un nodo sin padres es la raiz
Un nodo sin hijos es una hoja
Un arbol donde sus nodos no tienen mas de 2 hijos es un Arbol Binario
Las relaciones verticales entre los nodos se representan con aristas o ramas
Solo existe un camino para llegar desde un nodo a otro
El único arbol sin raiz es el arbol vacío
El único arbol sin hojas es el arbol vacío
Definiciones
🏷️
Altura del árbol: Longitud del camino
🏷️
El camino entre dos nodos es el conjunto de nodos que hay que recorrer para conectar dichos nodos (nodo inicial y final incluidos), el número de aristas que se recorren en un camino se conoce como longitud del camino
🏷️
El grado (aridad)de un nodo se refiere al número de hijos del mismo. El grado del arbol es en mayor de los grados de todos sus nodos (hijos y subhijos)
🏷️
El nivel/profundidad de un nodo es el número de aristas entre la raiz y el nodo, aunque si contamos con que la raiz es de nivel 1, entonces hay que sumar uno más.
🏷️
La altura del arbol es la longitud del camino desde el nodo raíz a su hoja más lejana (el árbol de un solo elemento lo consideramos con altura 1, para que el árbol vacio pueda ser considerado con altura 0)
🏷️
El Grado de Aridad de un nodoesel número de hijos del nodo
Especificación de un Arbol Binario
Tipos
TArbolB
Operaciones
Constructoras generadoras
crearArbolBVacio: → TArbolB
construirArbolB: TElemento X TArbolB X TArbolB → TArbolB
DEF(raiz(crearArbolBVacio(r, i, d)))
DEF(hijoI(crearArbolBVacio(r, i, d)))
DEF(hijoD(crearArbolBVacio(r, i, d)))
Ecuaciones
raiz(rellenarArbolB(r, i, d)) = r
hijoI(rellenarArbolB(r, i, d)) = i
hijoD(rellenarArbolB(r, i, d)) = d
esArbolBVacio(crearArbolBVacio()) = True
esArbolBVacio(rellenarArbolB(r, i, d)) = False
numNodos(construirArbolB(r, i, d)) = 1 + numNodos(i) + numNodos(d)
numHojas
numHojas(crearArbolBVacio) = 0
numHojas(construirArbolB(r, i, d)) = SI esArbolBVacio(i)&&esArbolBVacio(d) → (1) || ( nomHojas(i) + numHojas(d) )
altura
altura(crearArbolBVacio) = 0
altura(crearArbolB(r, i, d)) = 1 + max(altura(i), altura(d))
compensado
compensado(crearArbolBVacio) = True
compensado(construirArbolBVacio(r, i, d)) = (numNodos(i) = numNodos(d))
nivelElemento
nivelElemento(crearArbolBVacio, e) = 1
nivelElemento(construirArbolB(r, i, d), e) = SI (r = e) → ( 1 ) || (1 + min(nivelElemento(i, e), nivelElemento(d, e)))
espejo
espejo(crearArbolBVacio) = crearArbolBVacio
espejo(construirArbolBVacio(r, i, d)) = crearArbolBVacio(r, espejo(i), espejo(d))
frontera
frontera(crearArbolBVacio) = crearListaVacia
frontera(l, construir(r, i, d)) = SI esArbolBVacio(i) && esArbolBVacio(d)→ (construir(l, r)) || (concatenar(frontera(i), frontera(d)))
Recorridos de un arbol Binario
Recorridos
Los diferentes tipos de recorridos expresan el orden en el que se visitan los nodos de un arbol binario
Preorden (Raiz→Izq→Der)
💡
Siempre debe aparecer en la lista la raiz, posteriormente el hijo izq y posteriormente el hijo der. Recorremos el arbol desde la raiz avanzando siempre por el hijo más a la izquierda que podamos
Ecuaciones
preorden(crearArbolBVacio) = crearListaVacia
preorden(construirArbolB(r, i, d)) = construirLista(r, concatenar(preorden(i), preorden(d)))
procedure preorden(a:TArbolB);
var e:TElemento;
aux:TArbolB;
begin
// -------------------------------------[ Añadir elemento a la lista, antes de los hijos
Inorden (Izq→Raiz→Der)
💡
Siempre debe aparecer en la lista el hijo izq, posteriormente la raiz y posteriormente el hijo der. Recorreremos el arbol desde el nodo más a la izquerda posible de todo el subarbol, a continuación su raiz y el derecho
Ecuaciones
inorden(crearArbolBVacio) = crearListaVacia
inorden(construirArbolB(r, i, d)) = concatenar(inorden(i), construirLista(r, inorden(d)))
procedure inorden(a:TArbolB);
var e:TElemento;
aux:TArbolB;
begin
// Recursividad del hijo Izq
hijoI(a, aux);
if not esArbolBVacio(aux) then inorden(aux);
// -------------------------------------[ Añadir elemento a la lista, entre los hijos
Posorden (Izq→Der→Raiz)
💡
Siempre debe aparecer en la lista el hijo izq, posteriormente el hijo der y posteriormente la raiz . Recorreremos el arbol desde el nodo más a la izquerda posible, a continuación recorreremos sus hermanos para finalmente subir de nivel y recorrer la raiz
Ecuaciones
posorden(crearArbolBVacio) = crearListaVacia
posorden(construirArbolB(r, i, d)) = insertarFinal(r, concatenar(posorden(i), posorden(d)))
procedure posorden(a:TArbolB);
var e:TElemento;
aux:TArbolB;
begin
// Recursividad del hijo Izq
hijoI(a, aux);
if not esArbolBVacio(aux) then posorden(aux);
// Recursividad del hijo Izq
hijoD(a, aux);
if not esArbolBVacio(aux) then inorden(aux);
// -------------------------------------[ Añadir elemento a la lista, despues de los hijos
Un ABB es un arbol binario balanceado, esto quiere decir que si complejidad es O(log2(n)) , si no estubiera balanceado, en el peor de los casos la complejidad sería O(n). En un ABB se busca seguir un criterio para que nos permita ordenar el arbol para luego buscar en su interior siguiendo el mismo criterio: Es menor, es mejor, es mas grande, etc…
Especificación Algebraica de los Árboles Binarios de Búsqueda
Tipos
TArbolBB
Operaciones
Observadora no selectora
pertenece: TArbolBB X TElemento → boolean
(parcial)minimo(TArbolBB) → TElemento (esta obtiene el peor/mas pequeño nodo del arbol)
Constructoras no generadoras
insertarOrd: TArbolBB X TElemento → TArbolBB
eliminar: TArbolBB X TElemento → TArbolBB
Ecuaciones de definitud
DEF ( minimo(construirArbolBB(r, i, d)) )
Ecuaciones
Observadoras no selectoras
pertenece
pertenece(crearArbolBBVacio, e) = False
pertenece(construirArbolBB(r, i, d), e) = SI r = e → ( True ) || ( siesMejor(e, r) → pertenece(i, e) || pertenece(d, e) )
minimo(construirArbolBB(r, i, d)) = SI esArbolBBVacio(i) → r || minimo(i)
insertar(construirArbolBB(r, i, d), e) = SIe = r → ( construirArbolBB(r, i, d) ) || ( si esMejor(e, r) → construirArbolBB(r, insertar(i, e), d) || construirArbolBB(r, i, insertar(d, e)) )
eliminar
eliminar(crearArbolBBVacio) = crearArbolBBVacio
eliminar(construirArbolBB(r, i, d), e) = SI e = r ( si esArbolBBVacio(d) → i || construirArbolBB(minimo(d), i, eliminar(d, minimo(e))) ) || ( si esMejor(e, r) → construirArbolBB(r, eliminar(i, e), d) || construirArbolBB(r, i, eliminar(d, e)) )
Equilibrio
📖
Los árboles equilibrados surgen para facilitar operaciones como la consulta. El árbol Adelson-Velskii y Landis (AVL) es un arbol equilibrado
📖
EL AVL es un arbol equilibrado según un criterio
Las alturas de los subárboles (hijos)de cada nodo no difiere en más de una unidad
El factor de equilibrio se conoce a la diferencia entre la altura del árbol izquierdo y el derecho.
FE=AlturaD−AlturaI
En un AVL, cada nodo puede tener un FE (balance) de {−1,0,1}
Ejemplo de árbol desbalanceado
Ejemplo de árbol balanceado
Para que se pueda dar la condición de equilibrio en un AVL debe haber un número mínimo de nodos definido por la fórmula
N(h)=N(h−1)+N(h−2)+1
Para corregir los desbalances aplicamos unas tranformaciones al arbol llamadas rotaciones
Rotaciones
📖
Rotación Simple (i→i ó d→d)
En esta rotación se coje el nodo y sus subarboles, se rota en la dirección deseada. La raiz pasará a ser un hijo mientras que un hijo pasará a ser la raiz, el subarbol que queda libre del hijo que pasa a ser la raiz, pasa a ser hijo de la que era la raiz ya que ahora tiene un hijo libre
PROCEDURE RotarSDer(VAR a: TArbolBB);
VAR nuevaR: TArbolBB;
BEGIN
IF not EsArbolBinVacio(a^.izq) THEN begin // Existe hijo izquierdo
nuevaR := a^.izq; // Guardar hijoI de la antigua raiz como la nueva raiz
a^.izq := nuevaR^.der; // Pasar el hijoD del hijoI de la antigua raiz al otro lado como hijoI de la antigua raiz
nuevaR^.der := a; // Establecer como hijoD de la nueva raiz a la antigua raiz
a := nuevaR; // Establecer la nueva raiz como la raiz del arbol pasado por referencia
END;
END;
📖
Rotación Doble (i→d ó d→i)
En una rotación doble utilizaremos dos rotaciones simples, la primera la usaremos para forzar un desequilibrio debajo del nodo con ±2 para que sus nodos este orientados hacia el mismo lado que el desequilibrio del nodo padre (como si fuera una rampa) y la siguiente rotación la usaremos en el nodo desequilibrado hacia el lado donde no tengamos el desequilibrio
PROCEDURE RotarDIzqDer(VAR a:TArbolBB);
VAR aux: TArbolBB;
BEGIN
IF esArbolBinVacio(a^.izq) THEN BEGIN
rotarSimpleIzq(a^.izq);
rotarSimpleDer(a);
END;
END;
⚙️ Implementación
uArbolB.pas
unit uArbol;
interface
uses uElemento;
type
TArbol = ^TNodo;
TNodo = RECORD
raiz: TElemento;
izq, dch:TArbol;
END;
// Prototipos
procedure crearArbolVacio(var a:TArbol);
procedure construirAB(var a:TArbol; raiz:TElemento; i,d:TArbol);
procedure getRaiz(a:TArbol; var e:TElemento);
procedure getIzq(a:TArbol; var a_out:TArbol);
procedure getDch(a:TArbol; var a_out:TArbol);
implementation
procedure crearArbolVacio(var a:TArbol); begin
a := NIL;
end;
// El argumento `a` debe ser pasado siempre como un arbol vacio
procedure construirAB(var a:TArbol; raiz:TElemento; i,d:TArbol); begin
new(a);
copiarElemento(a^.raiz, raiz);
aux^.izq := i;
aux^.dch := d;
end;
function esArbolVacio(a:TArbol):boolean; begin
esArbolVacio := a = NIL;
end;
procedure getRaiz(a:TArbol; var e:TElemento); begin
copiarElemento(e, a^.raiz);
end;
procedure getIzq(a:TArbol; var a_out:TArbol); begin
a_out := a^.izq;
end;
procedure getDch(a:TArbol; var a_out:TArbol); begin
a_out := a^.dch;
end;
end.
uArbolUtils.pas
unit uArbolUtils;
interface
uses uArbol
implementation
function numHojas(a:TArbol):integer;
var hi, hd:TArbol;
begin
if not esArbolVacio(a) then begin
getIzq(a, hi);
getDch(a, hd);
numHojas := numHojas(hi) + numHojas(hd);
if esHoja(a) then numHojas := numHojas + 1;
end
else numHojas := 0;
end;
function numNodos(a:TArbol):integer;
var hi, hd:TArbol;
begin
if not esArbolVacio(a) then begin
getIzq(a, hi);
getDch(a, hd);
numNodos := numNodos(hi) + numNodos(hd) + 1;
end
else numNodos := 0;
end;
function profundidad(a:TArbol):integer;
var hi, hd:TArbol;
begin
if not esArbolVacio(a) then begin
getIzq(a, hi);
getDch(a, hd);
numNodos := max(numNodos(hi), numNodos(hd)) + 1;
end
else numNodos := 0;
end;
function max(a, b:integer):integer;
begin
if a > b then max := a
else max := b;
end;
function esHoja(a:TArbol):boolean;
var hi, hd:TArbol;
begin
esHoja := False;
if not esArbolVacio(a) then begin
getIzq(a, hi);
getDch(a, hd);
esHoja := esArbolVacio(hi) and esArbolVacio(hd);
end
end;
function nivelElemento(a:TArbol;e:TElemento):integer;
var
r:TElemento;
i,d:TArbol;
ni,nd:integer;
begin
if esArbolVacio(a) then
nivelElemento := 0
else begin
getRaiz(a,r);
getIzq(a,i);
getDch(a,d);
if esIgual(r,e) then
NivelElemento:=1;
else begin
ni := NivelElemento(i);
nd := NivelElemento(d);
if (ni > 0) AND (nd > 0) then
NivelElemento:= 1 + min(ni,nd);
else if ni > 0 then
NivelElemento:= 1 + ni;
else if nd > 0 then
NivelElemento:= 1 + nd;
else NivelElemento:= 0;
end;
end;
procedure espejo(var a:TArbol);
var i,d:TArbol;
r:TElemento;
begin
if not esArbolVacio(a) then begin
getIzq(a, i);
getDch(a, d);
getRaiz(a, r);
crearArbolVacio(a, r, d,i);
espejo(i);
espejo(d);
end
end;
end.
uArbolBB.pas
unit uArbolBB;
interface
uses uElemento;
type
TArbol = ^TNodo;
TNodo = RECORD
raiz: TElemento;
izq, dch:TArbol;
END;
implementation
end.
PROCEDURE eliminar(var a:TArbolBB; e:TElemento);
var aux:TArbolBB;
auxe:TElemento;
begin
if not esArbolBBVacio(a) then begin
// Elemento encontrado
if esIgual(a^.raiz, e) then begin
if esArbolBBVacio(a^.hijoD) then begin // No hace falta rotacion (hijo D vacio)
aux := a; // Guardar nodo
a := a^.hijoI; // Reemplazar nodo
dispose(aux); // Liberar memoria
end
else if (esArbolBBVacio(a^.hijoI)) then begin // No hace falta rotacion (hijo I vacio)
aux := a;
a := a^.hijoD;
dispose(aux)
end;
else begin // Rotacion necesaria
minimo(auxe, a^hijoD); // Consultar el menor/peor de la rama dch
copiarRaiz(a^.raiz, auxe); // Covertir dicho elemento en la nueva raiz del nodo que vamos a eliminar(sustituir)
eliminar(a^.hijoD, auxe); // Eliminar el valor minimo de dch ya que lo hemos movido
end;
end
// Buscando elemento
else begin
if esMejor(e, a^.raiz) then // EsMenor
eliminar(a^.hijoI, e);
else // EsMayor
eliminar(a^.hijoD, e);
end;
end;
end;
FUNCTION pertenece(var a:TArbolBB; e:TElemento):boolean; begin
// No encontrado
if esArbolBBVacio(a) then pertenece := false
// Buscando
else begin
if esIgual(e, a^.raiz) then // Encontrado
pertenece := true
else if esMejor(e, a^.raiz) then // EsMenor
pertenece := pertenece(a^.hijoI, e)
else // EsMayor
pertenece := pertenece(a^.hijoD, e);
end;
end;
PROCEDURE minimo(var e:TElemento; a:TArbolBB); begin // Mejor()
if not esArbolVacio(a) then begin
if esArbolBBVacio(a^.hijoI) then
copiarElemento(e, a^.raiz)
else
minimo(e, a^.hijoI)
end
end;
Recorrido
type
TArbol = ^Tnodo;
TNodo = Record
raiz: TElemento;
hi: TArbol;
hd: TArbol;
end;
//------------------procedimiento recorrido--------------
procedure recorrido (a:TArbol);
var
r: TElemento; (*Raiz*)
i,d: TArbol; (*Izquierda - Derecha*)
Begin
if not EsVacio(a) then
begin
getRaiz(a,r);
getHijoI(a,i);
getHijoD(a,d);
//mostrar(r); {Preorden}
recorrido(i);
//mostrar(r); {Inorden}
recorrido(d);
//mostrar(r); {Posorden}
end;
end;
Frontera
Esta operación devuelve la lista de hojas de un arbol
type
TArbol = ^Tnodo;
TNodo = Record
raiz: TElemento;
hi: TArbol;
hd: TArbol;
end;
//------------------procedimiento Frontera--------------
procedure frontera (a: TArbol; Var l:Tlista);
var
r: TElemento;
i,d: TArbol;
begin
if not esvacio(a) then
begin
raiz(a,r);
hi(a,i);
hd(a,d);
if esHoja(a) then
construir(l,r);
frontera(i,l);
frontera (d,l);
