En ciències de la computació, un arbre binari de cerca (BST, de l'anglès Binary Search Tree) és un tipus particular d'arbre binari que presenta una estructura de dades en forma d'arbre.

Descripció Un arbre binari de cerca és un arbre binari definit de la següent manera:

Dit de manera resumida, és un arbre binari en què 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 més grans. Per tant, segons aquesta definició, 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 total de l'arbre (h) al pitjor dels casos tindrà la mateixa mida que el nombre d'elements disponibles. I en el millor dels casos ve donada per l'expressió , on indica arrodoniment a l'alça.

Arbre binari de cerca

miniatura|Exemple d' Arbre Binari de Cerca L'interès dels arbres binaris de cerca és que el seu recorregut en inorder proporciona els elements ordenats de forma ascendent i 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 subarbres 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. Amb la següent especificació d'arbre binari en Maude:

fmod TREE-BINARY {X :: TRIV} is sorts TreeBinNV{X} TreeBin{X} . subsort TreeBinNV{X} < TreeBin{X} . *** generadors op create : -> TreeBin{X}[ctor] . op treeBin : X$Elt TreeBin{X} TreeBin{X} -> TreeBinNV{X}[ctor] . endfm

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

fmod TREE-BINARY-SEARCH {X :: ORDER} is protecting TREE-BINARY{VOrder}{X} . sorts BST{X} BSTNV{X} . subsort BSTNV{X} < BST{X} . subsort BST{X} < TreeBin{VOrder}{X} . subsort BSTNV{X} < TreeBinNV{VOrder}{X} . *** generadors op create : -> TreeBin{X}[ctor] . op treeBin : X$Elt TreeBin{X} TreeBin{X} -> TreeBinNV{X}[ctor] . endfm

amb la següent teoria d'ordre:

fth ORDER 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 TREE-BINARY-SEARCH:

var R : X$Elt . vars INV DNV : BSTNV{X} . vars I D : BST{X} . mb create : BST{X} . mb treeBin(R, create, create) : BSTNV{X} . cmb treeBin(R, INV, create) : BSTNV{X} if R > max(INV) . cmb treeBin(R, create, DNV) : BSTNV{X} if R < min(DNV) . cmb treeBin(R, INV, DNV) : BSTNV{X} if (R > max(INV)) and (R < min(DNV)) . ops min max : BSTNV{X} -> X$Elt . eq min(treeBin(R, create, D)) = R . eq min(treeBin(R, INV, D)) = min(INV) . eq max(treeBin(R, I, create)) = R . eq max(treeBin(R, I, DNV)) = max(DNV) .

Implementació en Python:

class node: left, right, data = None, None, 0 def __init__(self, data): # Crea un node self.left = None self.right = None self.data = data

class binaryTree: def __init__(self): # Inicia l'arrel self.root = None

def insertNode(self, data): # Crea un nou node i el retorna return node(data)

def insert(self, root, data): # Inserta un valor nou a l'arbre if root == None: # Si no hi ha nodes a l'arbre, l'agrega return self.insertNode(data) else: # Si hi ha nodes a l'arbre, el recorre if data <= root.data: # Si el valor és menor que el guardat, va al subarbre esquerre root.left = self.insert(root.left, data) else: # Si no, va al subarbre dret root.right = self.insert(root.right, data) return root

Operacions 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 quina és major 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.

Cerca La cerca a l'arbre consisteix en accedir a l'arrel; si l'element a localitzar coincideix amb aquest llavors la cerca es dona per conclosa, 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 cerca 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₂(n+1) i n, essent n el nombre de nodes. La recerca d'un element en un 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 search_BST(abb t, key k) { abb p; data e; e=NULL; p=t; if (!isNull(p)) { while (!isNull(p) && (p->k!=k)) { if (k < p->k) p = p->l; if (p->k < k) p = p->r; } if (!isNull(p) &&(p->d!=NULL)) { e = copyData(p->d);

return e; }

Vegeu ara la versió recursiva en aquest mateix llenguatge:

int search(tTree *a, int elem) { if (a == NULL) { return 0; } else if (a->key < elem) { return search(a->hRight, elem); } else if (a->key > elem) { return search(a->hLeft, elem); } else { return 1;

Un altre exemple, en Python:

def search_binary_tree(node, key): if node is None: return None # No s'ha trobat 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 search(T: ABR, y: integer): ABR begin if (T=nil) or (^T.root=y) then search:=T; else if (^T.root<y) then search:=search(^T.right,y); else search:=search(^T.left,y); end;

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

op this? : X$Elt ABB{X} -> Bool . var R R1 R2 : X$Elt . vars I D : ABB{X} . eq this?(R, create) = false . eq this?(R1, treeBin(R2, I, D)) = if R1 == R2 then true else if R1 < R2 then this?(R1, I) else this?(R1, D) end end .

Inserció La inserció és similar a la cerca, es pot donar una solució tant iterativa com recursiva. Si tenim inicialment com a 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.

center|miniatura|800px|Evolució de la inserció de l'element "5" en un arbre binari de cerca Com en el cas de la cerca pot haver diverses variants a l'hora d'implementar la inserció en el ADT (de l'anglès, Abstract Data Type), 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ó. Aquesta operació modifica l'arbre, perdent la versió anterior d'aquest.

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

PROC InsertarSBT (arbre: Tabba; dada: TElement) VARIABLES nou_node, PAV, pret: Tabba nova_clau: Tclau elements: TElement INICI nou_node <- NOU (TNodeSBT) nou_node^. esquerra <- NUL nou_node^. dreta <- NUL nou_node^. elem <- dada SI SBTBuit(arbre) LLAVORS arbre <- nou_node EN_CAS_CONTRARI nova_clau <- dada.clau PAV <- arbre // Punter Avançat pret <- NUL // Punter retardat MENTRE (PAV <- NUL) FER pret <- PAV elements = PAV^. elem SI (nova_clau < ele.clau) LLAVORS PAV <- PAV^. esquerra EN_CAS_CONTRARI PAV <- PAV^. dreta FI_SI FI_MENTRE elements = pret^. elem SI (nova_clau < ele.clau) LLAVORS pret^. esquerra <- nou_node EN_CAS_CONTRARI pret^. dreta <- nou_node FI_SI FI_SI FI

PROC InsertarSBT (arbre: Tabba; dada: TElement) VARIABLES elements: TElement INICI SI (SBTBuit(arbre)) LLAVORS arbre <- NOU (TNodeSBT) arbre^. esquerra <- NUL arbre^. dreta <- NUL arbre^. elem <- dada EN_CAS_CONTRARI elements = InfoSBT (arbre) SI (dada.clau < ele.clau) LLAVORS InsertarSBT (arbre^. esquerra, dada) EN_CAS_CONTRARI InsertarSBT (arbre^. dreta, dada) FI_SI FI_SI FI

Es pot 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 insert(tTree **a, int elem) { if (*a == NULL) { *a = (tTree *) malloc(sizeof(tTree)); (*a)->key = elem; (*a)->hLeft = NULL; (*a)->hRight = NULL; } else if ((*a)->key < elem) { insert(&(*a)->hRight, elem); } else if ((*a)->key > elem) { insertar(&(*a)->hLeft, elem);

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

Un altre exemple en Pascal:

Procedure Insertion(var T:ABR, y:integer) var last_node:ABR; current_node:ABR; new_node:ABR; begin last_node:=nil; current_node:=T; while (current_node<>nil) do begin last_node:=current_node; if (current_node^.root<y) then current_node:=current_node^.right else current_node:=current_node^.left; end; new(new_node); ^new_node.root:=y; ^new_node.left:=nil; ^new_node.right:=nil; if last_node=nil then T:=new_node else if last_node^.root<y then last_node^.right:=new_node else last_node^.left:=new_node; end;

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

op insert : X$Elt BST{X} -> BSTNV{X} . var R R1 R2 : X$Elt . vars I D : BST{X} . eq insert(R, create) = treeBin(R, create, create) . eq insert(R1, treeBin(B2, I, D)) = if R1 < R2 then treeBin(R2, insert(R1, I), D) else treeBin(R2, I, insert(R1, D)) end .

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

Esborrat L'operació d'esborrat no és tan senzilla com les de recerca i inserció. Hi ha diversos casos a tenir en consideració:s. Robert Sedgewick, Kevin Wayne: Algorithms Fourth Edition. Pearson Education, 2011, , p. 410.

Esborrar un node sense fills o node fulla : simplement s'esborra i s'estableix a nul l'apuntador del seu predecessor. marc|center|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 predecessor. marc|center|Node d'esborrar 70 Esborrar un node amb dos subarbres 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 existeix la possibilitat de realitzar qualsevol dels dos reemplaçaments: marc|center|Node d'esborrar 59

El següent algorisme en C realitza l'esborrament en un BST. El procediment replace busca la major clau del subarbre esquerre i l'assigna al node a eliminar.

void replace(tTree **a, tTree **aux); /*Prototip de la funció replace */ void remove(tTree **a, int elem) { tTree *aux;