Arboles

ÁRBOLES BINARIOS DE BÚSQUEDA (ABB)
INTRODUCCIÓN
- Un árbol binario de búsqueda (ABB) es un árbol binario con la propiedad de que todos los elementos almacenados en el subárbol izquierdo de cualquier nodo x son menores que el elemento almacenado en x , y todos los elementos almacenados en el subárbol derecho de x son mayores que el elemento almacenado en x. - Una interesante propiedad es que sise listan los nodos del ABB en inorden nos da la lista de nodos ordenada. Esta propiedad define un método de ordenación similar al Quicksort, con el nodo raíz jugando un papel similar al del elemento de partición del Quicksort aunque con los ABB hay un gasto extra de memoria mayor debido a los punteros. La propiedad de ABB hace que sea muy simple diseñar un proce dimiento para realizar labúsqueda.

- El espacio requerido para el almacenamiento es O(n). Donde n es el número de nodos del árbol.

LA CLASE ABSTRACTA

Class ABB { Public: typedef struct nodo *Iterador; ABB(); ABB (const ABB& v); ABB& operator = (const ABB &v); Iterador primero() const; Iterador siguiente(Iterador i) const; Iterador final() const; const Tbase& etiqueta(const Iterador n) const; Iterador buscar(const Tbase&e) const; bool insertar(const Tbase& e); Iterador borrar(const Iterador p); void equilibrar(); void clear(); int size() const; bool empty() const; bool operator == (const ABB& v) const; bool operator != (const ABB& v) const; ~ABB(); Private:

struct nodo { Tbase etiqueta; struct nodo *izqda; struct nodo *drcha; struct nodo *padre; }; struct nodo *laraiz; int nelementos; void destruir(nodo * n);void copiar(nodo *& dest, nodo * orig); void enganchar(nodo *&r, nodo **m, int n); }

Implementación
template inline ABB::ABB() { laraiz=0; nelementos=0; }

template ABB::ABB (const ABB& v) { copiar (laraiz,v.laraiz);

if (laraiz!=0) laraiz->padre= 0; nelementos=v.nelementos; }

template void ABB::destruir(nodo * n) { if (n!=0) { destruir(n->izqda); destruir(n->drcha); delete n; } }template void ABB::copiar(nodo *& dest, nodo * orig) { if (orig==0) dest= 0; else { dest= new nodo; dest->etiqueta= orig->etiqueta; copiar (dest->izqda,orig->izqda); copiar (dest->drcha,orig->drcha); if (dest->izqda!=0) dest->izqda->padre= dest; if (dest->drcha!=0) dest->drcha->padre= dest;

} }

template void ABB::enganchar (nodo* & r, nodo **m, int n) { int i; i=n/2; r=m[i]; if (i>0) {enganchar(r->izqda,m,i); r->izqda->padre=r; } else r->izqda= 0; if (n-i-1>0) { enganchar(r->drcha,m+i+1,n-i-1); r->drcha->padre=r; } else r->drcha=0; }

template ABB& ABB::operator=(const ABB& v) { if (this!=&v) { destruir(laraiz); copiar (laraiz,v.laraiz);

if (laraiz!=0) laraiz->padre= 0; nelementos=v.nelementos; } return *this; }

template ABB::Iterador ABB::primero() const { nodo *p;if (laraiz==0) return 0; else { p=laraiz; while (p->izqda!=0) p= p->izqda; return p; } }

template ABB::Iterador const { nodo *padre; bool subir; assert(i!=0); if (i->drcha!=0) {

ABB::siguiente(Iterador

i)

i=i->drcha; while (i->izqda!=0) i=i->izqda; } else { subir=true; while (subir) { padre= i->padre; if (padre==0) { i=0; subir=false; } else if (padre->drcha!=i) { i= padre;subir=false; } else i= padre; } } return i; }

template inline ABB::Iterador { return 0; }

ABB::final() const

template inline const Tbase& ABB::etiqueta(const const { assert(p!=0); return (p->etiqueta); }

Iterador

p)

template ABB::Iterador ABB::buscar(const const { Iterador i; i=laraiz; while (i!=0) { if (i->etiquetadrcha; else if (eetiqueta) i=i->izqda; else return i; } returnfinal(); }

Tbase&

e)

template inline bool ABB::insertar(const Tbase& e) { bool fin,dev; nodo *p;

if (laraiz==0) { laraiz = new nodo; laraiz->padre= laraiz->izqda= laraiz->drcha= 0; laraiz->etiqueta= e; nelementos++; return true; } else { p= laraiz; fin=false; while (!fin) { if (eetiqueta) { if (p->izqda==0) { p->izqda= new nodo; p->izqda->padre=p; p=p->izqda; p->drcha= p->izqda= 0;...