Árbol binario de búsqueda
De Wikipedia, la enciclopedia libre
Un árbol binario de búsqueda es un tipo particular de árbol binario, una estructura de datos usada en informática.
Tabla de contenidos |
[editar] Descripción
Un árbol binario de búsqueda (ABB) es un árbol binario definido de la siguiente forma:
Todo árbol vacío es un árbol binario de búsqueda.
Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
·En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo
almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol de búsqueda.
·En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo almacenado
en el subárbol derecho, y que el subárbol derecho sea un árbol de búsqueda.
Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.
Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación este definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.
La altura h en el peor de los casos siempre el mismo tamaño que el número de elementos disponibles. Y en el mejor de los casos viene dada por la expresión h = ceil(log2(c + 1)), donde ceil indica redondeo por exceso.
El interés de los árboles binarios de búsqueda radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.
Dependiendo de las necesidades del usuario que trate con una estructura de este tipo se podrá permitir la igualdad estricta en alguno, en ninguno o en ambos de los subárboles que penden de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja.
[editar] Operaciones
Todas las operaciones realizadas sobre árboles binarios de búsqueda están basadas en la comparación de los elementos o clave de los mismos, por lo que es necesaria una subrutina, que puede estar predefinida en el lenguaje de programación, que los compare y pueda establecer una relación de orden entre ellos, es decir, que dados dos elementos sea capaz de reconocer cual es mayor y cual menor. Se habla de clave de un elemento porque en la mayoría de los casos el contenido de los nodos será otro tipo de estructura y es necesario que la comparación se haga sobre algún campo al que se denomina clave.
[editar] Búsqueda
La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.
Ejemplo de versión iterativa en el lenguaje de programación C, suponiendo que estamos buscando una clave alojada en un nodo donde está el correspondiente "dato" que precisamos encontrar:
data Buscar_ABB(abb t,clave k) { abb p; dato e; e=NULL; p=t; if (!estaVacio(p)) { while (!estaVacio(p) && (p->k!=k) ) { if (k < p->k) { p=p->l; } if (p->k < k) { p=p->r; } } if (!estaVacio(p) &&(p->d!=NULL) ) { e=copiaDato(p->d); } } return e; }
Véase ahora la versión recursiva en ese mismo lenguaje:
int buscar(tArbol *a, int elem) { if (a == NULL) return 0; else if (a->clave < elem) return buscar(a->hDerecho, elem); else if (a->clave > elem) return buscar(a->hIzquierdo, elem); else return 1; }
Otro ejemplo en Python:
def search_binary_tree(node, key): if node is None: return None # not found if key < node.key: return search_binary_tree(node.left, key) else if key > node.key: return search_binary_tree(node.right, key) else: return node.value
En Pascal:
Function busqueda(T:ABR, y: integer):ABR begin if (T=nil) or (^T.raiz=y) then busqueda:=T; else if (^T.raiz<y) then busqueda:=busqueda(^T.dch,y); else busqueda:=busqueda(^T.izq,y); end;
Ahora vamos a definir los generadores crear y arbolbBin en Maude, quedaría :
fmod ARBOL-BINARIO-BUSQUEDA {X :: TRIV} is
sorts ArbolbBin{X} ArbolbBin{X} .
subsort ArbolbBinNV{X} < ArbolbBin{X} .
*** generadores
op crear : -> ArbolbBin{X} [ctor] .
op arbolBinario : X$Elt ArbolbBin{X} ArbolB{X} -> ArbolBNV{X} [ctor] .
endfm
Donde X es una teoría de orden:
fth ORDEN is
protecting BOOL .
sort Elt .
*** operaciones
op _<_ : Elt Elt -> Bool .
endfth
Por último, la especificación de la operación de búsqueda:
op esta? : X$Elt ArbolbBin{X} -> Bool .
var R R1 R2 : X$Elt .
vars I D : ArbolbBin{X} .
eq esta?(R, crear) = false .
eq esta?(R1, arbolbBin(R2, I, D)) = if R1 == R2 then
true
else
if R1 < R2 then
esta?(R1, I)
else
esta?(R1, D)
fi
fi .
[editar] Inserción
La inserción es similar a la búsqueda, por tanto también es posible una versión iterativa con los mismos resultados que una recursiva. Se procede de la siguiente forma, si el árbol pasado como parámetro está vacío se crea un nuevo nodo para él cuyo contenido correspondiente sería el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que el de la raíz del árbol con lo que se inserta en el subárbol izquierdo, o mayor, insertándose en el subárbol derecho. Se observa que de este modo las inserciones se realizan en las hojas, es la forma más simple de llevar a cabo esta tarea, aunque no la única. Además, permite mantener la estructura (forma) del árbol anterior a la inserción.
Como en el caso de la búsqueda puede haber varias variantes a la hora de implementar la inserción en el TAD (Tipo Abstracto de Datos), y es la decisión a tomar cuando el elemento (o clave del elemento) a insertar ya se encuentra en el árbol, puede que éste sea modificado o que sea ignorada la inserción. Es obvio que esta operación modifica el ABB perdiendo la versión anterior del mismo.
A continuación se muestran las dos versiones del algoritmo en pseudolenguaje, iterativa y recursiva, respectivamente.
PROC InsertarABB(árbol:TABB; dato:TElemento)
VARIABLES
nuevonodo,pav,pret:TABB
clavenueva:Tclave
ele:TElemento
INICIO
nuevonodo <- NUEVO(TNodoABB)
nuevonodo^.izq <- NULO
nuevonodo^.der <- NULO
nuevonodo^.elem <- dato
SI ABBVacío (árbol) ENTONCES
árbol <- nuevonodo
ENOTROCASO
clavenueva <- dato.clave
pav <- árbol // Puntero Avanzado
pret <- NULO // Puntero Retrasado
MIENTRAS (pav <- NULO) HACER
pret <- pav
ele = pav^.elem
SI (clavenueva < ele.clave ) ENTONCES
pav <- pav^.izq
EN OTRO CASO
pav <- pav^.dch
FINSI
FINMIENTRAS
ele = pret^.elem
SI (clavenueva < ele.clave ) ENTONCES
pret^.izq <- nuevonodo
EN OTRO CASO
pret^.dch <- nuevonodo
FINSI
FINSI
FIN
PROC InsertarABB(árbol:TABB; dato:TElemento)
VARIABLES
ele:TElemento
INICIO
SI (ABBVacío(árbol)) ENTONCES
árbol <- NUEVO(TNodoABB)
árbol^.izq <- NULO
árbol^.der <- NULO
árbol^.elem <- dato
EN OTRO CASO
ele = InfoABB(árbol)
SI (dato.clave < ele.clave) ENTONCES
InsertarABB(árbol^.izq, dato)
EN OTRO CASO
InsertarABB(árbol^.dch, dato)
FINSI
FINSI
FIN
Se ha podido apreciar la simplicidad que ofrece la versión recursiva, este algoritmo es la traducción en C. El árbol es pasado por referencia para que los nuevos enlaces a los subárboles mantengan la coherencia.
void insertar(tArbol **a, int elem) { if (*a == NULL) { *a = (tArbol *) malloc(sizeof(tArbol)); (*a)->clave = elem; (*a)->hIzquierdo = NULL; (*a)->hDerecho = NULL; } else if ((*a)->clave < elem) insertar(&(*a)->hDerecho, elem); else if ((*a)->clave > elem) insertar(&(*a)->hIzquierdo, elem); }
Ejemplo en Python:
def binary_tree_insert(node, key, value): if node is None: return TreeNode(None, key, value, None) if key == node.key: return TreeNode(node.left, key, value, node.right) if key < node.key: return TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right) else: return TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))
Otro ejemplo en Pascal:
Procedure Insercion(var T:ABR, y:integer) var ultimo:ABR; actual:ABR; nuevo:ABR; begin ultimo:=nil; actual:=T; while (actual<>nil) do begin ultimo:=actual; if (^actual.raiz<y) then actual:=^actual.dch; else actual:=^actual.izq; end; new(nuevo); ^nuevo.raiz:=y; ^nuevo.izq:=nil; ^nuevo.dch:=nil; if ultimo=nil then T:=nuevo; else if ^ultimo.raiz<y then ^ultimo.dch:=nuovo; else ^ultimo.izq:=nuevo; end;
Véase también un ejemplo de algoritmo recursivo de inserción en un ABB en el lenguaje de programación Maude:
op insertar : X$Elt ArbolbBin{X} -> ArbolbBinNV{X} .
var R R1 R2 : X$Elt .
vars I D : ArbolbBin{X} .
eq insertar(R, crear) = arbolbBin(R, crear, crear) .
eq insertar(R1, arbolbBin(R2, I, D)) = if R1 < R2 then
arbolbBin(R2, insertar(R1, I), D)
else
arbolbBin(R2, I, insertar(R1, D))
fi .
La operación de inserción requiere, en el peor de los casos, un tiempo proporcional a la altura del árbol.
[editar] Borrado
La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración:
- Borrar un nodo sin hijos ó nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.
- Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.
- Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos:
El siguiente algoritmo en C realiza el borrado en un ABB. El procedimiento reemplazar busca la mayor clave del subárbol izquierdo y la asigna al nodo a eliminar.
void borrar(tArbol **a, int elem) { void reemplazar(tArbol **a, tArbol **aux); tArbol *aux; if (*a == NULL) return; if ((*a)->clave < elem) borrar(&(*a)->hDerecho, elem); else if ((*a)->clave > elem) borrar(&(*a)->hIzquierdo, elem); else if ((*a)->clave == elem) { aux = *a; if ((*a)->hIzquierdo == NULL) *a = (*a)->hDerecho; else if ((*a)->hDerecho == NULL) *a = (*a)->hIzquierdo; else reemplazar(&(*a)->hIzquierdo, &aux); free(aux); } } void reemplazar(tArbol **a, tArbol **aux) { if ((*a)->hDerecho == NULL) { (*aux)->clave = (*a)->clave; *aux = *a; *a = (*a)->hIzquierdo; } else reemplazar(&(*a)->hDerecho, aux); }
Otro ejemplo en Pascal.
Procedure Borrar(var T:ABR, x:ABR) var aBorrar:ABR; anterior:ABR; actual:ABR; hijo:ABR; begin if (^x.izq=nil) or (^x.dch=nil) then aBorrar:=x; else aBorrar:=sucesor(T,x); actual:=T; anterior:=nil; while (actual<>aBorrar) do begin anterior:=actual; if (^actual.raiz<^aBorrar.raiz) then actual:=^actual.dch; else actual:=^actual.izq; end; if (^actual.izq=nil) then hijo:=^actual.dch; else hijo:=^actual.izq; if (anterior=nil) then T:=hijo; else if (^anterior.raiz<^actual.raiz) then ^anterior.dch:=hijo; else ^anterior.izq:=hijo; if (aBorrar<>x) then ^x.raiz:=^aBorrar.raiz; free(aBorrar); end;
Véase también un ejemplo de algoritmo recursivo de borrado en un ABB en el lenguaje de programación Maude, considerando los generadores crear y arbolbBin. Esta especificación hace uso de la componente clave a partir de la cual se ordena el árbol.
op eliminar : X$Clave ArbolbBin{X} -> ArbolbBin{X} .
varS R M : X$Elt .
vars I D : ArbolbBin{X} .
vars INV DNV : ArbolbBinNV{X} .
ops max min : ArbolbBin{X} -> X$Elt .
eq min(arbolbBin(R, crear, D)) = R .
eq max(arbolbBin(R, I, crear)) = R .
eq min(arbolbBin(R, INV, D)) = min(INV) .
eq max(arbolbBin(R, I, DNV )) = max(DNV) .
eq eliminar(M, crear) = crear .
ceq eliminar(M, arbolbBin(R, crear, D)) = D if M == clave(R) .
ceq eliminar(M, arbolbBin(R, I, crear)) = I if M == clave(R) .
ceq eliminar(M, arbolbBin(R, INV, DNV)) = arbolbBin(max(INV), eliminar(clave(max(INV)), INV), DNV) if M == clave(R) .
ceq eliminar(M, arbolbBin(R, I, D)) = arbolbBin(R, eliminar(M, I), D) if M < clave(R) .
ceq eliminar(M, arbolbBin(R, I, D)) = arbolbBin(R, I, eliminar(M, D)) if clave(R) < M .
[editar] Recorridos
Cabe notar que los recorridos en los arboles binarios de búsqueda nos ofrecen los elementos ordenados según su clave. Así al hacer el recorrido en inorden de un ABB obtenemos los elementos ordenados de forma ascendente.
[editar] Véase también
