Arbre binari de cerca

De Viquipèdia
Dreceres ràpides: navegació, cerca

Un arbre binari de cerca és un tipus particular d'arbre binari que presenta una estructura de dades en forma d'arbre utilitzada en informàtica.

Descripció[modifica | modifica el codi]

Un arbre binari de cerca (ABB) és un arbre binari definit de la següent manera:

Tot arbre buit és un arbre binari de cerca.

Un arbre binari no buit, d'arrel R, és un arbre binari de cerca si:
• En cas de tenir subarbre esquerre, l'arrel R ha de ser major que el valor màxim
 emmagatzemat al subarbre esquerre, i que el subarbre esquerre sigui un arbre binari
 de cerca.
• En cas de tenir subarbre dret, l'arrel R ha de ser menor que el valor mínim
 emmagatzemat al subarbre dret, i que el subarbre dret sigui un arbre binari
 de cerca.

Per a una fàcil comprensió, queda resumit en el fet que és un arbre binari que compleix que el subarbre esquerre de qualsevol node (si no buit) conté valors menors que el que conté aquest node, i el subarbre dret (si no buit) conté valors grans.

Per a aquestes definicions es considera que hi ha una relació d'ordre establerta entre els elements dels nodes. Que certa relació estigui definida, o no, depèn de cada llenguatge de programació. D'aquí es dedueix que hi pot haver diferents arbres binaris de cerca per a un mateix conjunt d'elements.

L'alçada h al pitjor dels casos sempre la mateixa mida que el nombre d'elements disponibles. I en el millor dels casos ve donada per l'expressió  h = Ceil (log_2 (c+1)) , on Ceil indica arrodoniment per excés.

Arbre binari de cerca

Exemple d' Arbre Binari de Cerca

L'interès dels arbres binaris de cerca (ABB) és que el seu recorregut en inorder proporciona els elements ordenats de forma ascendent i en que la recerca d'algun element sol ser molt eficient.

Depenent de les necessitats de l'usuari que tracti amb una estructura d'aquest tipus es podrà permetre la igualtat estricta en algun, en cap o en ambdós dels subarbre que pengen de l'arrel. Permetre l'ús de la igualtat provoca l'aparició de valors dobles i fa la recerca més complexa.

Un arbre binari de cerca no deixa de ser un cas particular d'arbre binari, així ho amb la següent especificació d'arbre binari en Maude:

  FMODA   ARBOL-BINARI{X:: Trives}  is  
  sorts   ArbolBinNV{X}ArbolBin{X}.
  subsort   ArbolBinNV{X}<ArbolBin{X}.
  *** generadors  
  op   crear: → ArbolBin{X}[  ctor  ].
  op   arbolBin: X $ ELT ArbolBin{X}ArbolBin{X}→ ArbolBinNV{X}[  ctor  ].
  endfm  

podem fer la següent definició per a un arbre binari de cerca (també en Maude):

  FMODA   ARBOL-BINARI-RECERCA{X:: ORDRE}  is  
  Protecting   ARBOL-BINARI{Vorden}{X}.
  sorts   ABB{X}ABBNV{X}.
  subsort   ABBNV{X}<ABB{X}.
  subsort   ABB{X}<ArbolBin{Vorden}{X}.
  subsort   ABBNV{X}<ArbolBinNV{Vorden}{X}.
  *** generadors  
  op   crear: → ArbolBin{X}[  ctor  ].
  op   arbolBin: X $ ELT ArbolBin{X}ArbolBin{X}→ ArbolBinNV{X}[  ctor  ].
  endfm  

amb la següent teoria de ordre:

  fth   ORDRE   is  
  Protecting   BOOL.
  sort   ELT.
  *** operacions  
  op   _ <_: ELT ELT → Bool.
  endfth  

perquè un arbre binari pertanyi al tipus arbre binari de cerca ha de complir la condició d'ordenació següent que aniria al costat del mòdul ARBOL-BINARI-RECERCA:

  var   R: X $ ELT.
  vars   INV DNV: ABBNV{X}.
  vars   I D: ABB{X}.
  mb   crear: ABB{X}.
  mb   arbolBin (R, crear, crear): ABBNV{X}.
  CMB   arbolBin (R, INV, crear): ABBNV{X}  if   R> màx (INV).
  CMB   arbolBin (R, crear, DNV): ABBNV{X}  if   R <min (DNV).
  CMB   arbolBin (R, INV, DNV): ABBNV{X}  if   (R> màx (INV)) and (R <min (DNV)).
  ops   mín màx: ABBNV{X}→ X $ ELT.
  eq   min (arbolBin (R, crear, D)) = R.
  eq   min (arbolBin (R, INV, D)) = min (INV).
  eq   màx (arbolBin (R, I, crear)) = R.
  eq   màx (arbolBin (R, I, DNV)) = màx (DNV).

Operacions[modifica | modifica el codi]

Totes les operacions realitzades sobre arbres binaris de cerca estan basades en la comparació dels elements o clau dels mateixos, per la qual cosa cal una subrutina, que pot estar predefinida en el llenguatge de programació, que els compari i pugui establir una relació d'ordre entre ells, és a dir, que donats dos elements sigui capaç de reconèixer que és més gran i quina menor. Es parla de clau d'un element perquè en la majoria dels casos el contingut dels nodes serà un altre tipus d'estructura i cal que la comparació es faci sobre algun camp al que s'anomena clau.

Recerca[modifica | modifica el codi]

Hi consisteix accedir a l'arrel de l'arbre, si l'element a localitzar coincideix amb aquest la Hi ha conclòs amb èxit, si l'element és menor es busca en el subarbre esquerre i si és major en el dret. Si s'arriba a un node fulla i l'element no ha estat trobat se suposa que no existeix en l'arbre. Cal destacar que la recerca en aquest tipus d'arbres és molt eficient, representa una funció logarítmica. El màxim nombre de comparacions que necessitaríem per saber si un element es troba en un arbre binari de cerca estaria entre [log 2 (N+1)] i N, essent N el nombre de nodes. La recerca d'un element en un ABB (Arbre Binari de Cerca) es pot realitzar de dues formes, iterativa o recursiva.

Exemple de versió iterativa al llenguatge de programació C, suposant que estem buscant una clau allotjada en un node on hi ha el corresponent "dada" que necessitem trobar:

data Buscar_ABB (ABB t, clau k)
{
 ABB p;
 dada i;
 i = 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))
 {
 i = copiaDato (p→ d);
 }
 }
 return i;
}

Vegeu ara la versió recursiva en aquest mateix llenguatge:

int cerca (tArbol * a, int elem)
{
 if (a == NULL)
 return 0;
 else if (a→ clau <elem)
 return cerca (a→ hDerecho, Elem);
 else if (a→ clau> elem)
 return cerca (a→ hIzquierdo, Elem);
 else
 return 1;
}

Un altre exemple a 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

A Pascal:

Function cerca (T: ABR, i: integer): ABR
begin
 if (T = nil) or (^T.raiz = i) then
 cerca: = T;
 else
 if (^T.raiz <i) then
 cerca: = cerca (^T.dch, i);
 else
 cerca: = cerca (^T.izq, i);
end;

Una especificació en Maude per a l'operació de cerca quedaria de la següent manera:

  op   aquesta? : X $ ELT ABB{X}→ Bool.
  var   R R1 R2: X $ ELT.
  vars   I D: ABB{X}.
  eq   aquesta? (R, crear) =   false  .
  eq   aquesta? (R1, arbolBin (R2, I, D)) =   if   R1 == R2   then  
  true  
  else  
  if   R1 <R2   then  
aquesta? (R1, I)
  else  
aquesta? (R1, D)
  fil  
  fil  .

Inserció[modifica | modifica el codi]

La inserció és similar a la recerca i es pot donar una solució tant iterativa com recursiva. Si tenim inicialment com paràmetre un arbre buit es crea un nou node com a únic contingut l'element a inserir. Si no ho està, es comprova si l'element donat és menor que l'arrel de l'arbre inicial amb el que s'insereix en el subarbre esquerre i si és major s'insereix en el subarbre dret. D'aquesta manera les insercions es fan a les fulles.

Evolució de la inserció de l'element "5" en un ABB

Com en el cas de la cerca pot haver diverses variants a l'hora d'implementar la inserció en el TAD (Tipus Abstracte de Dades), i és la decisió a prendre quan l'element (o clau de l'element) a inserir ja es troba en l'arbre, pot ser que aquest sigui modificat o que sigui ignorada la inserció. És obvi que aquesta operació modifica l'ABB perdent la versió anterior del mateix.

A continuació hi ha les dues versions de l'algorisme a pseudolenguaje, iterativa i recursiva, respectivament.

PROC InsertarABB (arbre: Tabba; dada: TElemento)
VARIABLES
 nuevonodo, PAV, pret: Tabba
 clavenueva: Tclave
 elements: TElemento
INICI
 nuevonodo <- NOU (TNodoABB)
 nuevonodo^. esquerra <- NUL
 nuevonodo^. der <- NUL
 nuevonodo^. elem <- dada
 SI ABBVacío (arbre) LLAVORS
 arbre <- nuevonodo
 ENOTROCASO
 clavenueva <- dato.clave
 PAV <- arbre//Punter Avançat
 pret <- NUL//Punter retardat
 MENTRE (PAV <- NUL) FER
 pret <- PAV
 elements = PAV^. elem
 SI (clavenueva <ele.clave) LLAVORS
 PAV <- PAV^. esq
 A UN ALTRE CAS
 PAV <- PAV^. DCH
 FINSI
 FINMIENTRAS
 elements = pret^. elem
 SI (clavenueva <ele.clave) LLAVORS
 pret^. esquerra <- nuevonodo
 A UN ALTRE CAS
 pret^. DCH <- nuevonodo
 FINSI
 FINSI
FI
PROC InsertarABB (arbre: Tabba; dada: TElemento)
VARIABLES
 elements: TElemento
INICI
 SI (ABBVacío (arbre)) LLAVORS
 arbre <- NOU (TNodoABB)
 arbre^. esquerra <- NUL
 arbre^. der <- NUL
 arbre^. elem <- dada
 A UN ALTRE CAS
 elements = InfoABB (arbre)
 SI (dato.clave <ele.clave) LLAVORS
 InsertarABB (arbre^. Esquerra, dada)
 A UN ALTRE CAS
 InsertarABB (arbre^. DCH, dada)
 FINSI
 FINSI
FI

S'ha pogut apreciar la simplicitat que ofereix la versió recursiva, aquest algorisme és la traducció en C. L'arbre és passat per referència perquè els nous enllaços als subarbre mantinguin la coherència.

void inserir (tArbol ** a, int elem)
{
 if (* a == NULL)
 {
 * A = (tArbol *) malloc (sizeof (tArbol));
 (* A) → clau = elem;
 (* A) → hIzquierdo = NULL;
 (* A) → hDerecho = NULL;
 }
 else if ((* a) → clau <elem)
 inserir (& (* a) → hDerecho, Elem);
 else if ((* a) → clau> elem)
 inserir (& (* a) → hIzquierdo, Elem);
}

Exemple a 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))

Un altre exemple a Pascal:

Procedure Inserció (var T: ABR, i: integer)
var
 últim: ABR;
 actual: ABR;
 nou: ABR;
begin
 últim: = nil;
 actual: = T;
 while (actual <> nil) do
 begin
 últim: = actual;
 if (^actual.raiz <i) then
 actual: =^actual.dch;
 else
 actual: =^actual.izq;
 end;
 new (nou);
 ^Nuevo.raiz: = i;
 ^Nuevo.izq: = nil;
 ^Nuevo.dch: = nil;
 if últim = nil then
 T: = nou;
 else
 if^ultimo.raiz <i then
 ^Ultimo.dch: = nuovo;
 else
 ^Ultimo.izq: = nou;
end;

Vegeu també un exemple d'algorisme recursiu d'inserció en un ABB en el llenguatge de programació Maude:

  op   inserir: X $ ELT ABB{X}→ ABBNV{X}.
  var   R R1 R2: X $ ELT.
  vars   I D: ABB{X}.
  eq   inserir (R, crear) = arbolBin (R, crear, crear).
  eq   inserir (R1, arbolBin (R2, I, D)) =   if   R1 <R2   then  
arbolBin (R2, inserir (R1, I), D)
  else  
arbolBin (R2, I, inserir (R1, D))
  fil  .

L'operació d'inserció requereix, en el pitjor dels casos, un temps proporcional a l'altura de l'arbre.

Esborrat[modifica | modifica el codi]

L'operació d'esborrat no és tan senzilla com les de recerca i inserció. Hi ha diversos casos a tenir en consideració:

  • Esborrar un node sense fills o node full : simplement s'esborra i s'estableix a nul l'apuntador del seu pare.
Node d'esborrar 74
  • Esborrar un node amb un subarbre fill : s'esborra el node i s'assigna el seu subarbre fill com subarbre del seu pare.
Node d'esborrar 70
  • Esborrar un node amb dos subarbre fill : la solució està en reemplaçar el valor del node pel del seu predecessor o pel del seu successor en inorder i posteriorment esborrar aquest node. El seu predecessor en inorder serà el node més a la dreta del seu subarbre esquerre (major node del subarbre esquerre), i el seu successor el node més a l'esquerra del seu subarbre dret (menor node del subarbre dret). En la següent figura es mostra com hi ha la possibilitat de realitzar qualsevol dels dos reemplaçaments:
Node d'esborrar 59

El següent algorisme en C realitza el esborrat en un ABB. El procediment reemplaçar busca la major clau del subarbre esquerre i la assigna al node a eliminar.

void esborrar (tArbol ** a, int elem)
{
 void reemplaçar (tArbol ** a, tArbol ** aux);
 tArbol * aux;
 
 if (* a == NULL)
 return;
 
 if ((* a) → clau <elem)
 esborrar (& (* a) → hDerecho, Elem);
 else if ((* a) → clau> elem)
 esborrar (& (* a) → hIzquierdo, Elem);
 else if ((* a) → clau == elem)
 {
 aux = * a;
 if ((* a) → hIzquierdo == NULL)
 * A = (* a) → hDerecho;
 else if ((* a) → hDerecho == NULL)
 * A = (* a) → hIzquierdo;
 else
 reemplaçar (& (* a) → hIzquierdo, & aux);
 
 free (aux);
 }
}
 
void reemplaçar (tArbol ** a, tArbol ** aux)
{
 if ((* a) → hDerecho == NULL)
 {
 (* Aux) → clau = (* a) → clau;
 * Aux = * a;
 * A = (* a) → hIzquierdo;
 }
 else
 reemplaçar (& (* a) → hDerecho, aux);
}

Un altre exemple a Pascal.

Procedure Esborrar (var T: ABR, x: ABR)
var
 aBorrar: ABR;
 anterior: ABR;
 actual: ABR;
 fill: ABR;
begin
 if (^x.izq = nil) or (^x.dch = nil) then
 aBorrar: = x;
 else
 aBorrar: = successor (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
 fill: =^actual.dch;
 else
 fill: =^actual.izq;
 if (anterior = nil) then
 T: = fill;
 else
 if (^anterior.raiz <^actual.raiz) then
 ^Anterior.dch: = fill;
 else
 ^Anterior.izq: = fill;
 if (aBorrar <> x) then
 ^X.raiz: =^aBorrar.raiz;
 free (aBorrar);
end;

Vegeu també un exemple d'algorisme recursiu de supressió en un ABB en el llenguatge de programació Maude, considerant els generadors crear i arbolBin. Aquesta especificació fa ús de la component clau a partir de la qual s'ordena l'arbre.

  op   eliminar: X $ ELT ABB{X}→ ABB{X}.
  vars   R M: X $ ELT.
  vars   I D: ABB{X}.
  vars   INV DNV: ABBNV{X}.
  ops   màx mín: ArbolBin{X}→ X $ ELT.
  eq   min (arbolBin (R, crear, D)) = R.
  eq   màx (arbolBin (R, I, crear)) = R.
  eq   min (arbolBin (R, INV, D)) = min (INV).
  eq   màx (arbolBin (R, I, DNV)) = màx (DNV).
  eq   eliminar (M, crear) = crear.
  CEQ   eliminar (M, arbolBin (R, crear, D)) = D   if   M == clau (R). 
  CEQ   eliminar (M, arbolBin (R, I, crear)) = I   if   M == clau (R). 
  CEQ   eliminar (M, arbolBin (R, INV, DNV)) = arbolBin (màx (INV), eliminar (clau (màx (INV)), INV), DNV)   if   M == clau (R).
  CEQ   eliminar (M, arbolBin (R, R, D)) = arbolBin (R, eliminar (M, I), D)   if   M <clau (R).
  CEQ   eliminar (M, arbolBin (R, R, D)) = arbolBin (R, I, eliminar (M, D))   if   clau (R) <M.

Altres Operacions[modifica | modifica el codi]

Una altra opereción seria per exemple comprovar que un arbre binari és un arbre binari de cerca. La seva implementació en Maude és la següent:

  op   esABB? : ABB{X}→ Bool.
  var   R: X $ ELT.
  vars   I D: ABB{X}.
  eq   esABB? (crear) =   true  .
  eq   esABB? (arbolbBin (R, R, D)) =
(Max (I) <R) and (Min (D)> R) and
(EsABB? (I)) and (esABB? (D)).

Recorreguts[modifica | modifica el codi]

Es pot fer un recorregut d'un arbre en profunditat o en amplada.

Els recorreguts en amplada són per nivells, es realitza horitzontalment des de l'arrel a tots els fills abans de passar a la descendència d'algun dels fills.

El recorregut en profunditat porta al camí des de l'arrel cap al descendent més llunyà del primer fill i després continua amb el fill.

Una propietat dels ABB és que en fer un recorregut en profunditat inorder obtenim els elements ordenats de forma ascendent.

Exemple arbre binari de cerca

Resultat de fer el recorregut a:

Inorder = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72].

Preordre = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72].

Postordre = [6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

Tipus d'arbres binaris de cerca[modifica | modifica el codi]

Hi ha diversos tipus d'arbres binaris de cerca. Els arbres AVL, arbre vermell-negre, són arbres autobalanceables. Els arbre bisellat són arbres també autobalanceables amb la propietat que els elements accedits recentment s'accedirà més ràpid en posteriors accessos. Al turó com en tots els arbres binaris de cerca cada node pare té un valor major q els seus fills ia més és complet, és a dir quan tots els nivells estan plens amb excepció de l'últim que pot no estar-ho.

Hi ha molts tipus d'arbres binaris de cerca. Els arbres AVL i els arbre vermell-negre són dos formes d'arbres binaris de cerca autobalanceables. Un arbre bisellat és un arbre binari de cerca que automàticament mou els elements als quals s'accedeix sovint prop de l'arrel. En els monticles, cada node també manté una prioritat i un node pare té més prioritat que el seu fill.

Dues maneres de configurar un arbre binari de cerca podria ser com un arbre o degenerat.

Un arbre és un arbre amb "n" nivells, on cada nivell d ← n-1, el nombre de nodes existents en el nivell "d" és igual que 2 d . Això vol dir que tots els possibles nodes hi ha en aquests nivells, no hi ha cap forat. Un requeriment addicional per a un arbre binari complet és que per al nivell "n", els nodes han d'estar ocupats d'esquerra a dreta, i no podrà haver un forat a l'esquerra d'un node ocupat.

Un arbre degeneratiu és un arbre que, per a cada node pare, només hi ha associat un node fill. Pel que es comporta com una llista enllaçada.

Comparació de rendiment[modifica | modifica el codi]

D. A. Heger (2004)[1] realitza una comparació entre els diferents tipus d'arbres binaris de cerca per trobar quin tipus ens donaria el millor rendiment per a cada cas. Els monticles es troben com el tipus d'arbre binari de cerca que millor resultat mitjana dóna, mentre que els arbres vermell-negre els que menor rendiment mitjà ens aporta.

Cercant l'Arbre binari de cerca òptim[modifica | modifica el codi]

Si nosaltres no tenim en ment planificar un arbre binari de cerca, i sabem exactament com de freqüent seran visitats cada element podem construir un arbre binari de cerca òptim amb el que aconseguirem que la mitjana de despesa generat a l'hora de buscar un element sigui minimitzat.

Assumint que coneixem els elements i en quin nivell està cada un, també coneixem la proporció de futures recerques que es faran per trobar aquest element. Si és així, podem utilitzar una solució basada en la programació dinàmica.

En canvi, de vegades només tenim l'estimació dels costos de recerca, com passa amb els sistemes que ens mostra el temps que ha necessitat per a realitzar una cerca. Un exemple, si tenim un ABB de paraules usat en un corrector ortogràfic, hauríem equilibrarà l'arbre basat en la freqüència que té una paraula en el Corpus lingüístic, desplaçant paraules com "de" a prop de l'arrel i paraules com " vesànic "a prop de les fulles. Un arbre com a tal podria ser comparat amb els arbres Huffman que tracten de trobar elements que són accedits freqüentment a prop de l'arrel per produir una densa informació; de tota manera, els arbres Huffman només pot guardar elements que contenen dades en els fulls i aquests elements no necessiten ser ordenats.

En canvi, si no sabem la seqüència en què els elements de l'arbre seran accedits, podem utilitzar arbres bisellats que són tan bons com qualsevol arbre de cerca que podem construir per a qualsevol seqüència en particular d'operacions de cerca.

Arbres alfabètics són arbres Huffman amb una restricció d'ordre addicional, o el que és el mateix, arbres de cerca amb modificació tal que tots els elements són emmagatzemats en les fulles.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]