Conjunto Sobre ABBs.c2

Implementación de conjuntos sobre ABB en C++
Algoritmos y Estructuras de Datos II
2.do cuatrimestre de 2019

Introducción
I Vamos a implementar una interfaz de conjunto en C++

I La representación interna consistirá en un árbol binario de
búsqueda (ABB)
I Utilizaremos memoria dinámica
Árboles binarios de búsqueda (ABB)
Un árbol binario es un ABB si es nil o satisface todas las siguientes

condiciones:
I Todos los nodos del subárbol izquierdo son menores que la
raı́z.
I Todos los nodos del subárbol derecho son mayores que la raı́z.
I Los subárboles izquierdo y derecho son ABBs.
Figure 12.2: Queries on a binary search tree. To search for the ke

the path 15 → 6 → 7 → 13 from the root. The minimum key in th
found by following left pointers from the root. The maximum key
Implementación en C++
I Vamos a implementar una clase Conjunto<T> paramétrica en

un tipo T con un orden total estricto <
I Primero plantearemos el esquema de la clase
I Luego la parte pública (interfaz)
I Luego la parte privada (representación y operaciones
auxiliares)
I Por último, la implementación de los métodos
Interfaz
I Queremos dotar a nuestra clase de una interfaz de conjunto

I ¿Qué operaciones serán visibles para el usuario?
En particular, para el taller, nos conformamos con:
I Crear un conjunto nuevo (vacı́o)
I Insertar un elemento
I Decidir si un elemento pertenece al conjunto
I Remover un elemento
I Obtener la cantidad de elementos
I Mostrar los elementos
I ¿Alguna otra operación que podrı́a resultar útil? (dado que T
tiene orden total estricto)
I Obtener el mı́nimo
I Obtener el máximo
I Obtener el elemento siguiente a otro dado
Interfaz
template <class T>
class Conjunto {
public:
Conjunto();
void insertar(const T&);
bool pertenece(const T&) const;
void remover(const T&);
const T& minimo() const;
const T& maximo() const;
unsigned int cardinal() const;
void mostrar(std::ostream&) const;
const T& siguiente(const T&) const;
private :
/*...*/
};
I ¿Por qué mı́nimo y máximo devuelven Const T?
Representación de los nodos
I Definimos una estructura Nodo para representar los nodos del

ABB
I La estructura estará en la parte privada de la clase ABB (no
queremos exportarla)
I La estructura va a contener un valor del tipo T y dos
punteros: uno al hijo izquierdo y el otro al hijo derecho
I La estructura tendrá un constructor que recibirá el valor de
tipo T como único argumento e inicializará los dos punteros a
NULL
private:
struct Nodo {
T valor;
Nodo* izq;
Nodo* der;
Nodo(const T& v) :
valor(v), izq(NULL), der(NULL) {
}
};
/*...*/
private:
struct Nodo {
T valor;
Nodo* izq;
Nodo* der;
Nodo(const T& v) :
valor(v), izq(NULL), der(NULL) {
}
};
Nodo* raiz;
raiz es la única variable de instancia y apunta al nodo raı́z del
ABB, o es NULL si el ABB no tiene nodos
¿En qué se diferencia con la estructura de la lista doblemente
enlazada?
private:
struct Nodo {
T valor;
Nodo* prev;
Nodo* sig;
Nodo(const T& v) :
valor(v), prev(NULL), sig(NULL) {
}
};
Nodo* cab;
¿Representan lo mismo? ¿Se comportan igual?
Los diferencia el invariante de representación (rep)

Irep
I El nodo raiz es null

Irep

I O bien
I Todos los nodos son alcanzables y
I No tiene ciclos y
I Todos los valores a la izq de la raiz son menores al valor en la
raiz y
I Todos los valores a la der de la raiz son mayores al valor en la
raiz
Irep

I O bien
I Todos los nodos son alcanzables y
I No tiene ciclos y
I Todos los valores a la izq de la raiz son menores al valor en la
raiz y
I Todos los valores a la der de la raiz son mayores al valor en la
raiz y
I Se cumple recursivamente el Irep para los dos subárboles
Pertenencia de un elemento
I Empezamos en la raı́z, si existe, si no devolver False

I Si el elemento está en la raı́z, devolvemos True
I Si no, decidimos en qué nodo continuar en base a < (gracias
al invariante de representación de los ABB).
I Consideramos a este nodo como la raı́z del subárbol
correspondiente y repetimos.
Figure 12.2: Queries on a binary search tree. To search for the ke

the path 15 → 6 → 7 → 13 from the root. The minimum key in th
found by following left pointers from the root. The maximum key
right pointers from the root. The successor of the node with key 1
8 p[z] ← y
9 if y = NIL
Insertar un elemento10 then root[T] ← z ⊹ Tree T was
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
I Buscamos en qué lugar del árbol debe ir la nueva clave

Figure 12.3 shows how TREE-INSERT works. Just like the p
I Para ello hacemosITERATIVE-TREE-SEARCH,
una búsqueda de la clave TREE-INSERT
en el árbol begins at the
I Si la búsqueda esdownward. The pointer x traces the path, and the pointer y is
exitosa, la clave ya pertenece al conjunto y
After initialization, the while loop in lines 3–7 causes these tw
no hacemos nadatree, going left or right depending on the comparison of key[z
NIL. This
I Si la búsqueda fracasa, se NIL
debeoccupies
insertartheun
position
nuevowhere
nodowecomo
wish to place
the pointers that cause z to be inserted.
hijo del último nodo de la búsqueda
Figure 12.3: Inserting an item with key 13 into a binary searc

indicate the path from the root down to the position where the
line indicates the link in the tree that is added to insert the item
Borrar un elemento
I Buscamos el nodo que tenemos que borrar.

I Tenemos 3 casos:
I El nodo que tenemos que borrar es una hoja → Lo borramos.
I El nodo que tenemos que borrar tiene un solo hijo → El hijo
pasa a ocupar el lugar del padre.
I El nodo que tenemos que borrar tiene dos hijos.
I ¿Qué nodos pueden ocupar su lugar?
I El inmediato sucesor. ¿Dónde está?
I El inmediato predecesor. ¿Dónde está?
Discusión
I ¿Qué complejidad tienen las siguientes operaciones?

I Pertenece → O(N )
I Insertar → O(N )
I Borrar → O(N )
I Mı́nimo/Máximo → O(N ) / O(1)
donde N es la cantidad de elementos que tiene el conjunto.
¡Ojo! ¡No depende sólo de la estructura en este caso!
¡Depende de si los datos fueron ingresados de manera uniforme o

no!
Iteración
Problema: Dar un algoritmo para recorrer todos los nodos de un

árbol ...
I ... en tiempo lineal (i.e. en O(n))
I ... iterativo
I ¿Por qué, si ya conocemos recorridos recursivos?
Para (después) poder implementar iteradores sobre árboles.
InOrder
I Repaso: inorder(Bin(i, r, d)) ≡

inorder(i) & <r> & inorder(d),
con lo cual, si el árbol es un ABB, esto está ordenado.
I Observación: el primer elemento que tenemos que devolver es
el mı́nimo. Y ya sabemos cómo encontrarlo: yendo siempre
hacia la izquierda.
Tenemos que hallar el sucesor del mı́nimo.
Sucesor de un elemento
I Buscamos el nodo en el árbol que tiene el elemento del que

buscamos el sucesor.
I (caso A) Si el nodo tiene un subárbol derecho, devolvemos el
mı́nimo elemento de dicho subárbol.
I (caso B) Si el nodo no tiene subárbol derecho, hay que subir
en el árbol:
I (caso B.1) Si el nodo es un hijo izquierdo, devolvemos el
elemento del padre.
I (caso B.2) Si el nodo es un hijo derecho, subimos en el árbol
hasta llegar a un nodo por su rama izquierda, y devolvemos ese
elemento.
Sucesor de un elemento, según el Cormen
Pueden encontrar los algoritmos para árboles binarios de búsqueda

(BST en inglés) en el capı́tulo 12 del Cormen.
Algunas alternativas posibles para no tener que conocer el
sucesor(...)
I (1) una pila.

I (2) Tener la cantidad de nodos precalculadas en el nodo.
https://www.geeksforgeeks.org/inorder-tree-traversal-without-
recursion/
Inorden con Pila (1)
I (1) Crear una pila S.

I (2) Inicializar el nodo actual a la raiz.
I (3) Apilar el nodo actual y mover actual a la izquierda(actual
= actual->izq) hasta que actual sea null.
I (4) Si actual no es null y S no esta vacio
I (a) Imprimir la cima(c) de S.
I (b) actual = c->der.
I (b) volver al paso 3
I (5) si actual es null y S esta vacio, terminamos.
Inorden con Pila: Implementacion
void inOrder(struct Node *root) {

stack<Node *> s; Node *actual = root;
while (actual != NULL || s.empty() == false) {
/* buscamos el nodo mas la izq */
while (actual != NULL) {
/* apilamos antes de mover! */
s.push(actual);
actual = actual->izq;
}
actual = s.top(); /* actual deberia ser NULL */
s.pop();
cout << actual->data << " ";
/* ahora reccorremos el subarbol derecho! */
actual = actual->der;
}
}
Inorden con Pila: Ejemplo
Abb b;
b.agregar(3);
b.agregar(1);
b.agregar(4);
b.agregar(0);
b.agregar(2);
b.inorden();
s = [3];
s = [3,1];
s = [3,1,0];
s = [3,1];
0;
s = [3];
1;
s = [3,2];
2;
s = [3];
3;
s = [];
s = [4];
4;
s = [];
Inorden con la cantidad de nodos precalculada (2)
private:
struct Nodo {
T valor;
Nodo* izq;
Nodo* der;
int cant;
Nodo(const T& v) :
valor(v), izq(NULL), der(NULL), cant(0){
}
};
/*...*/
Las hojas tienen 0 hijos
Inorden con la cantidad de nodos precalculada (2)
I La idea es:
I Actualizar cant al agregar/eliminar nodos en O(1)
I En inorden devolver un vector de nodos ordenados
I La posicion se puede calculcar con la cantidad de nodos de
cada subarbol en O(1)
I El vector puede llenarse en O(n)
Inorden con cant: Implementación
void inOrder(vector<T>& v) {
/* considero los nodas anteriores */
int indice = cantIzq();
v[indice] = info;
if (izq != null) izq.inOrder(v);

if (der != null) der.inOrder(v);
}
Inorden con cant: Implementación
void inOrder(vector<T>& v, int cantAnt) {

/* considero los nodas anteriores y los acumulados! */
int indice = cantIzq() + cantAnt;
v[indice] = info;
if (izq != null) izq.inOrder(v, cantAnt);

/* +1 me cuenta a mi mismo! */
if (der != null) der.inOrder(v, indice + 1);
}
I Demotramos O(n) y correctitud por inducción en cantidad de
nodos!
I En el caso iterativo -se puede- pero es mas dificil!
Destructor
¿Se puede aplicar la misma estregia para el destructor?

Destructor
template <class T>

void ABB<T>::destruir(nodo * n) {
if (n!=null) {
destruir(n->izq);
delete n;
destruir(n->der);
}
}
Destructor
template <class T>

if (n!=null) {
destruir(n->izq);
delete n;
// ¡Cuidado, n ya no existe!
destruir(n->der);
}
}
Destructor
template <class T>

if (n!=null) {
destruir(n->izq);
destruir(n->der);
delete n;
}
}
¡A programar!
En Conjunto.hpp está la declaración de la clase, su parte pública

y la definición de Nodo.

Conjunto Sobre ABBs.c2

Cargado por

Copyright:

Formatos disponibles

Conjunto Sobre ABBs.c2

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Conjunto Sobre ABBs.c2

Cargado por

Copyright:

Formatos disponibles

Implementación de conjuntos sobre ABB en C++

Algoritmos y Estructuras de Datos II

2.do cuatrimestre de 2019

I Vamos a implementar una interfaz de conjunto en C++

Un árbol binario es un ABB si es nil o satisface todas las siguientes

Figure 12.2: Queries on a binary search tree. To search for the ke

I Vamos a implementar una clase Conjunto<T> paramétrica en

I Queremos dotar a nuestra clase de una interfaz de conjunto

I Definimos una estructura Nodo para representar los nodos del

Los diferencia el invariante de representación (rep)

I El nodo raiz es null

I El nodo raiz es null

I El nodo raiz es null

I Empezamos en la raı́z, si existe, si no devolver False

Figure 12.2: Queries on a binary search tree. To search for the ke

I Buscamos en qué lugar del árbol debe ir la nueva clave

Figure 12.3: Inserting an item with key 13 into a binary searc

I Buscamos el nodo que tenemos que borrar.

I ¿Qué complejidad tienen las siguientes operaciones?

¡Ojo! ¡No depende sólo de la estructura en este caso!

¡Depende de si los datos fueron ingresados de manera uniforme o

Problema: Dar un algoritmo para recorrer todos los nodos de un

I Repaso: inorder(Bin(i, r, d)) ≡

I Buscamos el nodo en el árbol que tiene el elemento del que

Pueden encontrar los algoritmos para árboles binarios de búsqueda

I (1) una pila.

I (1) Crear una pila S.

void inOrder(struct Node *root) {

if (izq != null) izq.inOrder(v);

void inOrder(vector<T>& v, int cantAnt) {

if (izq != null) izq.inOrder(v, cantAnt);

¿Se puede aplicar la misma estregia para el destructor?

template <class T>

template <class T>

template <class T>

En Conjunto.hpp está la declaración de la clase, su parte pública

También podría gustarte