Wikipedia

Diferencia entre revisiones de «Árbol binario de búsqueda»

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
InternetArchiveBot (discusión · contribs.)
Bots
1 970 138 ediciones
Rescatando 1 referencia(s) y marcando 0 enlace(s) como roto(s)) #IABot (v2.0
Semibot (discusión · contribs.)
Bots
1 024 423 ediciones
m Bot: reemplazando etiqueta source desaconsejada
Línea 27:
Un árbol binario de búsqueda no deja de ser un caso particular de árbol binario, así usando la siguiente especificación de árbol binario en [[Maude (lenguaje de programación)|maude]]:
 
<fontspan colorstyle="color:#AF0000;">'''fmod'''</fontspan> ARBOL-BINARIO {X :: TRIV}<fontspan colorstyle="color:#C8AA00;">'''is'''</fontspan>
<fontspan colorstyle="color:#AF0000;">'''sorts'''</fontspan> ArbolBinNV{X} ArbolBin{X} .
<fontspan colorstyle="color:#AF0000;">'''subsort'''</fontspan> ArbolBinNV{X} < ArbolBin{X} .
<fontspan colorstyle="color:#008000;">'''*** generadores'''</fontspan>
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> crear : -> ArbolBin{X} [<fontspan colorstyle="color:#0080AF;">'''ctor'''</fontspan>] .
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> arbolBin : X$Elt ArbolBin{X} ArbolBin{X} -> ArbolBinNV{X} [<fontspan colorstyle="color:#0080AF;">'''ctor'''</fontspan>] .
<fontspan colorstyle="color:#AF0000;">'''endfm'''</fontspan>
 
podemos hacer la siguiente definición para un árbol binario de búsqueda (también en maude):
 
<fontspan colorstyle="color:#AF0000;">'''fmod'''</fontspan> ARBOL-BINARIO-BUSQUEDA {X :: ORDEN} <fontspan colorstyle="color:#C8AA00;">'''is'''</fontspan>
<fontspan colorstyle="color:#AF0000;">'''protecting'''</fontspan> ARBOL-BINARIO{VOrden}{X} .
<fontspan colorstyle="color:#AF0000;">'''sorts'''</fontspan> ABB{X} ABBNV{X} .
<fontspan colorstyle="color:#AF0000;">'''subsort'''</fontspan> ABBNV{X} < ABB{X} .
<fontspan colorstyle="color:#AF0000;">'''subsort'''</fontspan> ABB{X} < ArbolBin{VOrden}{X} .
<fontspan colorstyle="color:#AF0000;">'''subsort'''</fontspan> ABBNV{X} < ArbolBinNV{VOrden}{X} .
<fontspan colorstyle="color:#008000;">'''*** generadores'''</fontspan>
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> crear : -> ArbolBin{X} [<fontspan colorstyle="color:#0080AF;">'''ctor'''</fontspan>] .
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> arbolBin : X$Elt ArbolBin{X} ArbolBin{X} -> ArbolBinNV{X} [<fontspan colorstyle="color:#0080AF;">'''ctor'''</fontspan>] .
<fontspan colorstyle="color:#AF0000;">'''endfm'''</fontspan>
 
con la siguiente [[teoría]] de [[orden]]:
<fontspan colorstyle="color:#AF0000;">'''fth'''</fontspan> ORDEN <fontspan colorstyle="color:#C8AA00;">'''is'''</fontspan>
<fontspan colorstyle="color:#AF0000;">'''protecting'''</fontspan> BOOL .
<fontspan colorstyle="color:#AF0000;">'''sort'''</fontspan> Elt .
<fontspan colorstyle="color:#008000;">'''*** operaciones'''</fontspan>
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> _<_ : Elt Elt -> Bool .
<fontspan colorstyle="color:#AF0000;">'''endfth'''</fontspan>
 
para que un árbol binario pertenezca al tipo árbol binario de búsqueda debe cumplir la condición de ordenación siguiente que iría junto al módulo ARBOL-BINARIO-BUSQUEDA:
 
<fontspan colorstyle="color:#800080;">'''var'''</fontspan> R : X$Elt .
<fontspan colorstyle="color:#800080;">'''vars'''</fontspan> INV DNV : ABBNV{X} .
<fontspan colorstyle="color:#800080;">'''vars'''</fontspan> I D : ABB{X} .
<fontspan colorstyle="color:#C8AA00;">'''mb'''</fontspan> crear : ABB{X} .
<fontspan colorstyle="color:#C8AA00;">'''mb'''</fontspan> arbolBin(R, crear, crear) : ABBNV{X} .
<fontspan colorstyle="color:#C8AA00;">'''cmb'''</fontspan> arbolBin(R, INV, crear) : ABBNV{X} <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> R > max(INV) .
<fontspan colorstyle="color:#C8AA00;">'''cmb'''</fontspan> arbolBin(R, crear, DNV) : ABBNV{X} <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> R < min(DNV) .
<fontspan colorstyle="color:#C8AA00;">'''cmb'''</fontspan> arbolBin(R, INV, DNV) : ABBNV{X} <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> (R > max(INV)) and (R < min(DNV)) .
<fontspan colorstyle="color:#800080;">'''ops'''</fontspan> min max : ABBNV{X} -> X$Elt .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> min(arbolBin(R, crear, D)) = R .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> min(arbolBin(R, INV, D)) = min(INV) .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> max(arbolBin(R, I, crear)) = R .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> max(arbolBin(R, I, DNV)) = max(DNV) .
 
<sourcesyntaxhighlight lang="python">
class nodo:
izq , der, dato = None, None, 0
Línea 81:
self.der = None
self.dato = dato
</syntaxhighlight>
</source>
 
<sourcesyntaxhighlight lang="python">
class arbolBinario:
def __init__(self):
Línea 107:
raiz.der = self.insertar(raiz.der, dato)
return raiz
</syntaxhighlight>
</source>
 
== Operaciones ==
Línea 123:
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:
 
<sourcesyntaxhighlight lang="c">
data Buscar_ABB(abb t,clave k)
{
Línea 150:
return e;
}
</syntaxhighlight>
</source>
 
Véase ahora la versión recursiva en ese mismo lenguaje:
 
<sourcesyntaxhighlight lang="c">
int buscar(tArbol *a, int elem)
{
Línea 174:
}
}
</syntaxhighlight>
</source>
 
Otro ejemplo en [[Python]]:
 
<sourcesyntaxhighlight lang="python">
def buscar(raiz, clave):
# busca el valor clave dentro del arbol
Línea 193:
return buscar(raiz.der, clave)
 
</syntaxhighlight>
</source>
 
En [[Lenguaje de programación Pascal|Pascal]]:
 
<sourcesyntaxhighlight lang="pascal">
Function busqueda(T:ABR, y: integer):ABR
begin
Línea 208:
busqueda:=busqueda(^T.izq,y);
end;
</syntaxhighlight>
</source>
 
Una especificación en maude para la operación de búsqueda quedaría de la siguiente forma:
 
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> esta? : X$Elt ABB{X} -> Bool .
<fontspan colorstyle="color:#800080;">'''var'''</fontspan> R R1 R2 : X$Elt .
<fontspan colorstyle="color:#800080;">'''vars'''</fontspan> I D : ABB{X} .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> esta?(R, crear) = <fontspan colorstyle="color:#C8AA00;">'''false'''</fontspan> .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> esta?(R1, arbolBin(R2, I, D)) = <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> R1 == R2 <fontspan colorstyle="color:#C8AA00;">'''then '''</fontspan>
<fontspan colorstyle="color:#C8AA00;">'''true'''</fontspan>
<fontspan colorstyle="color:#C8AA00;">'''else '''</fontspan>
<fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> R1 < R2 <fontspan colorstyle="color:#C8AA00;">'''then'''</fontspan>
esta?(R1, I)
<fontspan colorstyle="color:#C8AA00;">'''else '''</fontspan>
esta?(R1, D)
<fontspan colorstyle="color:#C8AA00;">'''fi'''</fontspan>
<fontspan colorstyle="color:#C8AA00;">'''fi'''</fontspan> .
 
=== Inserción ===
Línea 294:
Se ha podido apreciar la simplicidad que ofrece la versión recursiva, este algoritmo es la traducción en [[Lenguaje de programación C|C]]. El árbol es pasado por [[Argumento (Ciencias de la computación)|referencia]] para que los nuevos enlaces a los subárboles mantengan la coherencia.
 
<sourcesyntaxhighlight lang="c">
void insertar(tArbol **a, int elem)
{
Línea 309:
insertar(&(*a)->hIzquierdo, elem);
}
</syntaxhighlight>
</source>
 
En [[Python]] el mecanismo de inserción se define, por ejemplo, dentro de la clase que defina el ABB (ver más arriba).
Línea 315:
Otro ejemplo en [[Lenguaje de programación Pascal|Pascal]]:
 
<sourcesyntaxhighlight lang="pascal">
Procedure Insercion(var T:ABR, y:integer)
var
Línea 344:
ultimo^.izq:=nuevo;
end;
</syntaxhighlight>
</source>
 
Véase también un ejemplo de algoritmo recursivo de inserción en un ABB en el lenguaje de programación [[Maude (lenguaje de programación)|Maude]]:
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> insertar : X$Elt ABB{X} -> ABBNV{X} .
<fontspan colorstyle="color:#800080;">'''var'''</fontspan> R R1 R2 : X$Elt .
<fontspan colorstyle="color:#800080;">'''vars'''</fontspan> I D : ABB{X} .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> insertar(R, crear) = arbolBin(R, crear, crear) .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> insertar(R1, arbolBin(R2, I, D)) = <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> R1 < R2 <fontspan colorstyle="color:#C8AA00;">'''then'''</fontspan>
arbolBin(R2, insertar(R1, I), D)
<fontspan colorstyle="color:#C8AA00;">'''else '''</fontspan>
arbolBin(R2, I, insertar(R1, D))
<fontspan colorstyle="color:#C8AA00;">'''fi'''</fontspan> .
 
La operación de inserción requiere, en el peor de los casos, un tiempo proporcional a la altura del árbol.
Línea 372:
El siguiente algoritmo en [[Lenguaje de programación C|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.
 
<sourcesyntaxhighlight lang="c">
void reemplazar(tArbol **a, tArbol **aux); /*Prototipo de la funcion ''reemplazar''*/
void borrar(tArbol **a, int elem)
Línea 410:
reemplazar(&(*a)->hDerecho, aux);
}
</syntaxhighlight>
</source>
 
Otro ejemplo en [[Lenguaje de programación Pascal|Pascal]].
 
<sourcesyntaxhighlight lang="pascal">
Procedure Borrar(var T:ABR, x:ABR)
var
Línea 451:
free(aBorrar);
end;
</syntaxhighlight>
</source>
 
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 arbolBin. Esta especificación hace uso de la componente clave a partir de la cual se ordena el árbol.
 
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> eliminar : X$Elt ABB{X} -> ABB{X} .
<fontspan colorstyle="color:#800080;">'''varS'''</fontspan> R M : X$Elt .
<fontspan colorstyle="color:#800080;">'''vars'''</fontspan> I D : ABB{X} .
<fontspan colorstyle="color:#800080;">'''vars'''</fontspan> INV DNV : ABBNV{X} .
<fontspan colorstyle="color:#C8AA00;">'''ops'''</fontspan> max min : ArbolBin{X} -> X$Elt .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> min(arbolBin(R, crear, D)) = R .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> max(arbolBin(R, I, crear)) = R .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> min(arbolBin(R, INV, D)) = min(INV) .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> max(arbolBin(R, I, DNV )) = max(DNV) .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> eliminar(M, crear) = crear .
<fontspan colorstyle="color:#C8AA00;">'''ceq'''</fontspan> eliminar(M, arbolBin(R, crear, D)) = D <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> M == clave(R) .
<fontspan colorstyle="color:#C8AA00;">'''ceq'''</fontspan> eliminar(M, arbolBin(R, I, crear)) = I <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> M == clave(R) .
<fontspan colorstyle="color:#C8AA00;">'''ceq'''</fontspan> eliminar(M, arbolBin(R, INV, DNV)) = arbolBin(max(INV), eliminar(clave(max(INV)), INV), DNV) <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> M == clave(R) .
<fontspan colorstyle="color:#C8AA00;">'''ceq'''</fontspan> eliminar(M, arbolBin(R, I, D)) = arbolBin(R, eliminar(M, I), D) <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> M < clave(R) .
<fontspan colorstyle="color:#C8AA00;">'''ceq'''</fontspan> eliminar(M, arbolBin(R, I, D)) = arbolBin(R, I, eliminar(M, D)) <fontspan colorstyle="color:#C8AA00;">'''if'''</fontspan> clave(R) < M .
 
=== Otras Operaciones ===
Línea 476:
Su implementación en maude es la siguiente:
 
<fontspan colorstyle="color:#800080;">'''op'''</fontspan> esABB? : ABB{X} -> Bool .
<fontspan colorstyle="color:#800080;">'''var'''</fontspan> R : X$Elt .
<fontspan colorstyle="color:#800080;">'''vars'''</fontspan> I D : ABB{X} .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> esABB?(crear) = <fontspan colorstyle="color:#C8AA00;">'''true'''</fontspan> .
<fontspan colorstyle="color:#C8AA00;">'''eq'''</fontspan> esABB?(arbolbBin(R, I, D)) =
(Max(I) < R) and (Min(D) > R) and
(esABB?(I)) and (esABB?(D)) .
Línea 553:
Recorridos en [[Lenguaje de programación C|C]] con funciones recursivas
 
<sourcesyntaxhighlight lang="c">
struct Nodo{
char nombre[30];
Línea 589:
}
}
</syntaxhighlight>
</source>
 
== Tipos de árboles binarios de búsqueda ==
Obtenido de «https://es.wikipedia.org/wiki/Árbol_binario_de_búsqueda»