PDF de programación - Árbol binario de búsqueda

¶Arbol binario de b¶usqueda .

Estructura de datos eflciente que permite buscar, insertar y borrar cualquier elemento o
cualquier rango de elementos.

Un ¶arbol binario de b¶usqueda es un ¶arbol binario, que puede ser vac¶‡o y si no es vac¶‡o
cumple las siguientes propiedades:

† Todos los elementos tienen una clave y no existen dos elementos con igual clave.

† Las claves (si existen) del sub¶arbol izquierdo son menores que la clave en la ra¶‡z.

variables

iz,dr,a

x,y

:

:

ecuaciones

arbol-busca

elem

min(arbol-vacio)

= errorarbol¡busca

min(plantar(iz,x,dr))

= x ( vacio?(iz)

min(plantar(iz,x,dr))

= min(iz) ˆ : vacio?(iz)

insertar(y,arbol-vacio)

= plantar(arbol-vacio,y,arbol-vacio)

insertar(x,plantar(iz,x,dr)) = plantar(iz,x,dr)

† Las claves (si existen) del sub¶arbol derecho son menores que la clave en la ra¶‡z.

insertar(y,plantar(iz,x,dr)) = plantar(insertar(y,iz),x,dr) ( y < x

† Los sub¶arboles izquierdo y derecho son tambi¶en ¶arboles binarios de b¶usqueda.

insertar(y, plantar(iz,x,dr)) = plantar(iz,x,insertar(y,dr)) ( y > x

¶Arbol de binario b¶usqueda. Especiflcaci¶on

especiflcaci¶on ARBOL-BUSCA[A es ELEM-ORD] es

usa BOOL

instancia privada ARBOL-BIN[B es ELEM] donde B.elem es A.elem

tipos arbol-busca

operaciones

insertar

buscar

borrar

esta

privada min

:

:

:

:

:

elem arbol-busca ! arbol-busca

elem arbol-busca ! arbol-busca

elem arbol-busca ! arbol-busca

elem arbol-busca ! bool

arbol-busca

! elem

buscar(x,arbol-vacio)

= arbol-vacio

buscar(x,plantar(iz,x,dr))

= plantar(iz,x,dr)

buscar(y,plantar(iz,x,dr))

= buscar(y,iz) ( y < x

buscar(y, plantar(iz,x,dr))

= buscar(y,dr) ( y > x

borrar(y,arbol-vacio)

= arbol-vacio

borrar(x,plantar(iz,x,dr)) = dr ( vacio?(iz)

borrar(x,plantar(iz,x,dr)) = iz ( vacio?(dr)

borrar(x,plantar(iz,x,dr)) = plantar(iz,min(dr),borrar(min(dr),dr))

( : vacio?(iz) ^: vacio?(dr)

borrar(y,plantar(iz,x,dr)) = plantar(borrar(y,iz),x,dr) ( y < x

borrar(y,plantar(iz,x,dr)) = plantar(iz,x,borrar(y,dr)) ( y > x

esta(x,a)

= : vacio?(buscar(x,a))

fespeciflcaci¶on

1

2

3

4

¶Arbol de b¶usqueda binario. Implementaci¶on

B¶usqueda del elemento menor

template <class TipoClave>
class ArbolBinarioBusqueda
f

public:

// m¶etodos de ¶arbol binario
nodo_arbol<TipoClave> * Busqueda(const TipoClave &x);
nodo_arbol<TipoClave> * Busqueda(nodo_arbol<TipoClave> * b, const TipoClave &x);
bool insertar( const TipoClave & x );
bool borrar( TipoClave & x );

private:

nodo_arbol<TipoClave> *raiz;

TipoClave Buscar_Min(nodo_arbol<TipoClave> * );

g;

// Esta funci¶on es llamada con al menos un elemento en su hijo derecho

template <class TipoClave>

TipoClave ArbolBinarioBusqueda<TipoClave>::

Buscar_Min(nodo_arbol<TipoClave>* aux )

f

g

while (aux -> izq != NULL)

aux = aux -> izq;

return aux->elemento;

Inserci¶on de un elemento

Complejidad: O(h) donde h es la profundidad del ¶arbol

B¶usqueda de un elemento

template <class TipoClave>

nodo_arbol<TipoClave> * ArbolBinarioBusqueda<TipoClave>

::Busqueda(const TipoClave &x)
f

return Busqueda(raiz,x);

g

template <class TipoClave>

nodo_arbol<TipoClave> * ArbolBinarioBusqueda<TipoClave>::

Busqueda(nodo_arbol<TipoClave> * b, const TipoClave &x)

f

if ( b == 0 )

return 0;

if ( x == b->elemento )

return b;

if ( x < b->elemento )

return Busqueda(b->izq,x);

return Busqueda(b->der,x);

g

Complejidad: O(h) donde h es la profundidad del ¶arbol

5

6

template <class TipoClave>

bool ArbolBinarioBusqueda<TipoClave>::insertar( const TipoClave & x )
f

// busqueda del lugar a insertar x, q es el padre de p

nodo_arbol<TipoClave> *p = raiz, *q=0 ;

while( p )
f

q = p;

if( x == p-> elemento ) return false;

if( x < p->elemento ) p = p->izq;

else p = p->der;

g

p = new nodo_arbol<TipoClave>;

p->izq = p->der = 0;

p-> elemento = x;

if (!raiz) raiz = p;

else if ( x < q->elemento ) q->izq = p;

else q->der = p;

return true;

g

7

8

Borrado de un elemento

if( !p )

† Si el elemento a borrar es una hoja del ¶arbol el campo correspondiente del padre se

return false;

// Si no se ha encontrado acabo

pone a null y se libera la memoria.

† Si el elemento a borrar tiene un ¶unico hijo, el hijo toma el lugar del nodo que se

elimina y se libera la memoria del nodo que se elimina.

† Si el elemento a borrar tiene dos hijos, el elemento se sustituye por el mayor de los

elementos del sub¶arbol izquierdo o por el menor de los elementos del sub¶arbol
derecho. A continuaci¶on se procede a eliminar este elemento y se libera la memoria.

Complejidad: O(h) donde h es la profundidad del ¶arbol

template <class TipoClave>

bool ArbolBinarioBusqueda<TipoClave>::borrar( TipoClave & x )
f

// busqueda del elemento x, q es el padre de p

nodo_arbol<TipoClave> *p = raiz, *q=0 ;

bool encontrado = false;

while( p && encontrado == false )
f

if ( x == p->elemento )

encontrado = true;

else
f

q = p;

if( x < p->elemento )

p = p->izq;

else

p = p->der;

g

g
// p apunta al elemento a borrar

// q apunta al padre del elemento a borrar

if( p->izq == NULL && p->der == NULL ) // si es una hoja
f

if ( !q && p == raiz)

// si es la raiz

f

g

raiz = NULL;

delete p;

return true;

if( q->izq == p )

q->izq = NULL;

else if( q->der == p )

q->der = NULL;

delete p;

return true;

// se elimina y finaliza

g

9

11

if( p->izq != NULL && p->der == NULL ) // si tiene un hijo
f

// si es la raiz

if ( !q && p == raiz)
f

raiz = p->izq;

delete p;

return true;

g
if( q->izq == p )

q->izq = p->izq;

else if( q->der == p )

q->der = p->izq;

delete p;

return true;

// se elimina y finaliza

g
if( p->izq == NULL && p->der != NULL ) // si tiene un hijo
f

if ( !q && p == raiz)

// si es la raiz

f

raiz = p->der;

delete p;

return true;

g

10

12

if( q->izq == p )

q->izq = p->der;

else if( q->der == p )

q->der = p->der;

delete p;

return true;

// se elimina y finaliza

g
if( p->izq != NULL && p->der != NULL ) // si tiene dos hijos
f

TipoClave x = Buscar_Min(p->der);

borrar(x);

p->elemento = x;

g

g

¶Arbol de b¶usqueda binario balanceado.

La profundidad de un ¶arbol de b¶usqueda binario de n elementos puede llegar a ser n.
Los ¶Arboles de b¶usqueda balanceados permiten realizar las operaciones de b¶usqueda,
insercci¶on y borrado con complejidad O(log(n)).

Los tipos m¶as conocidos de ¶arboles de b¶usqueda balanceados son:

† AVL

† 2-3

† 2-3-4

† rojo/negro

† ¶Arboles B

13

14