ÁRBOLES BINARIOS
DE BÚSQUEDA
ÁRBOLES BINARIOS DE
BÚSQUEDA
Un Árbol Binario de Búsqueda (ABB) es un
árbol binario que contiene información
ordenada según una llave (valor) de
búsqueda
En un ABB, para todo nodo n, las llaves del
subárbol izquierdo son menores que la
llave del nodo n y la llave del nodo n es
menor que las llaves del subárbol derecho
ÁRBOLES BINARIOS DE
BÚSQUEDA
Gráficamente
ÁRBOLES BINARIOS DE
BÚSQUEDA
En un ABB, el recorrido Enorden genera
una secuencia en orden ascendente según
la llave
T1 =
Enorden(T1) = A, B, C, D, E, F, H
ÁRBOLES BINARIOS DE
BÚSQUEDA
Ejercicio: Obtener Enorden(T2)
T2 =
ÁRBOLES BINARIOS DE
BÚSQUEDA
Representación
T1 =
T1 =
OPERACIONES SOBRE ABB´s
Búsqueda
Inserción
Eliminación
BÚSQUEDA EN ABB´s
Búsqueda de una llave k en un ABB T
Si T , k no existe
Si T , se compara k con la llave x al
interior del nodo apuntado por T
Si k x, la búsqueda termina
Si k x, la búsqueda continúa en el
subárbol izquierdo de T
Si k x, la búsqueda continúa en el
subárbol derecho de T
BÚSQUEDA EN ABB´s
Búsqueda de la llave 13 en el ABB T
T=
Se compara 13 con 10 buscar en Td
Se compara 13 con 14 buscar en Ti
Se compara 13 con 12 buscar en Td
Se encontró la llave 13
INSERCIÓN EN ABB´s
En un ABB T, el nodo que contendrá una
nueva llave k siempre se inserta como
hoja
T se crea el nodo para k
T se compara k con la llave
x al interior del nodo apuntado por T
Si k x, se avanza por el subárbol
izquierdo de T
Si k x, se avanza por el subárbol
derecho de T
INSERCIÓN EN ABB´s
Insertar, en un ABB T inicialmente vacío,
las llaves 10, 8, 14, 12, 9, 17, 5, 7, 11, 16,
13, 3 y 21
T=
ELIMINACIÓN EN ABB´s
La eliminación de una llave k, en un ABB
T, distingue tres situaciones
No existe un nodo con llave k
El nodo con llave k tiene, a lo más, un
hijo
El nodo con llave k tiene dos hijos.
Luego
Se reemplaza k por m (mayor de las
llaves del subárbol izquierdo ó menor
de las llaves del subárbol derecho) y
se elimina el nodo que la contiene
ELIMINACIÓN EN ABB´s
Eliminación de una llave k contenida en un
nodo hoja
ELIMINACIÓN EN ABB´s
Al eliminar las llaves k = 4 y k = 6, cada
una contenida en un nodo con un único
hijo,
T=
ELIMINACIÓN EN ABB´s
Resulta el siguiente nuevo ABB
T=
ELIMINACIÓN EN ABB´s
Al eliminar la llave k = 8, contenida en un
nodo con dos hijos,
T=
ELIMINACIÓN EN ABB´s
Debe ser remplazada por la mayor de las
llaves del subárbol izquierdo,
T=
ELIMINACIÓN EN ABB´s
Ó, ser remplazada por la menor de las
llaves del subárbol derecho
T=
LA CLASE ABB
#include <cstdlib>
#include <iostream>
using namespace std;
typedef int Base;
typedef char Clave;
struct Elemento{
Clave key;
Base info;
};
struct Nodo {
Clave key;
Base info;
Nodo *izq;
Nodo *der;
};
LA CLASE ABB
typedef Nodo *Arbol;
class Abb {
private:
Arbol B;
Base Busca(Arbol, Clave);
void Inserta(Arbol &, Elemento);
Arbol Menor(Arbol &);
Arbol Mayor(Arbol &);
void Elimina(Arbol &, Clave);
void VeAbb(Arbol);
LA CLASE ABB
public:
Abb();
bool Vacio();
Base Buscar(Clave);
bool Existe(Clave);
Clave GetKey();
Base GetInf();
Elemento GetMenor();
void Insertar(Elemento);
void Eliminar(Clave);
void VerAbb();
void CrearAbb();
};
LA CLASE ABB
Base Abb::Busca(Arbol T, Clave k) {
if (T == NULL)
return -1;
else
if (k < T->key)
return Busca(T->izq, k);
else
if (k > T->key)
return Busca(T->der, k);
else
return T->info;
}
LA CLASE ABB
void Abb::Inserta(Arbol &T, Elemento e) {
if (T == NULL) {
T = new Nodo;
T->key = [Link];
T->info = [Link];
T->izq = NULL;
T->der = NULL;
}
else
if ([Link] < T->key)
Inserta(T->izq, e);
else
if ([Link] > T->key)
Inserta(T->der, e);
}
LA CLASE ABB
Arbol Abb::Menor(Arbol &S) {
if (S->izq != NULL)
return Menor(S->izq);
else
return S;
}
Arbol Abb::Mayor(Arbol &S) {
if (S->der != NULL)
return Mayor(S->der);
else {
Arbol p = S;
S = S->izq;
return p;
}
}
LA CLASE ABB
void Abb::Elimina(Arbol &T, Clave k) {
Arbol q;
if (T != NULL)
if (k == T->key) {
q = T;
if (T->der == NULL)
T = T->izq;
else
if (T->izq == NULL)
T = T->der;
else {
q = Mayor(T->izq);
T->key = q->key;
T->info = q->info;
}
LA CLASE ABB
delete q;
}
else
if (k < T->key)
Elimina(T->izq, k);
else
if (k > T->key)
Elimina(T->der, k);
}
LA CLASE ABB
void Abb ::VeAbb(Arbol T) {
if (T != NULL) {
VeAbb(T->izq);
cout << "Clave: " << T->key << " Info: " << T-
>info << endl;
VeAbb(T->der);
}
}
Abb::Abb() {
B = NULL;
}
LA CLASE ABB
bool Abb::Vacio() {
return B == NULL;
}
bool Abb::Existe(Clave k) {
return Busca(B, k) != -1;
}
Clave Abb::GetKey() {
return B->key;
}
Base Abb::GetInf() {
return B->info;
}
LA CLASE ABB
Elemento Abb::GetMenor() {
Arbol q;
Elemento e;
q = Menor(B);
[Link] = q->key;
[Link] = q->info;
return e;
}
LA CLASE ABB
Base Abb::Buscar(Clave k) {
return Busca(B, k);
}
void Abb::Insertar(Elemento e) {
Inserta(B, e);
}
void Abb::Eliminar(Clave k) {
Elimina(B, k);
}
void Abb::VerAbb() {
VeAbb(B);
}
LA CLASE ABB
void Abb::CrearAbb() {
Elemento e;
int i;
cout << "Ingrese un entero: ";
cin >> i;
while(i != 0) {
[Link] = i;
cout << "Ingrese una letra: ";
cin >> [Link];
Inserta(B, e);
cout << "Ingrese un entero: ";
cin >> i;
}
cout << endl;
}
LA CLASE ABB
Ejercicio
Se dispone de dos Abb’s T1, T2. Implementar la
función Unir(T1, T2), correspondiente a las
operaciones T1 = T1T2 y T2 = .
void Unir(Abb &T1, Abb &T2)
{ Elemento e;
if(![Link]())
{ [Link] = [Link]();
[Link] = [Link]();
[Link](e);
[Link]([Link]);
Unir(T1,T2);
}
}
