Arbre de busca
En ciències de la computació, un arbre de busca és una estructura de senyes de tipo arbre utilisat per a localisar claus concretes dins d'un conjunt. Per a que un arbre puga funcionar com a arbre de busca en cada nodo té que complir-se que la seua clau té que ser més gran que qualsevol clau continguda en la seua subárbol esquerre i menor que qualsevol clau continguda en la seua subárbol dret.[1]
La ventaja dels arbres de busca és la seua eficiència en el temps de busca, ya que l'arbre està raonablement balancejat, lo que vol dir que totes les fulls es troben a profunditats similars. Existixen vàries estructures de senyes de tipo arbre de busca, vàries de les quals també permeten l'inserció i eliminació eficient d'elements, operacions que tenen que mantindre l'equilibri de l'arbre.
Els arbres de busca a sovint són utilisats per a implementar vectores associatius. L'algoritme de l'arbre de busca utilisa la clau del parell clau-valor per a trobar una ubicació, i llavors l'aplicació almagasena el parell sancer en eixa ubicació.
Tipos d'Arbres
Arbre de Busca Binaria
Un arbre de busca binaria és una estructura de senyes basada en nodos a on cada nodo conté una clau i dos subárboles, l'esquerre i el dret. Per a tots els nodos, les claus dels nodos pertanyents al seu subárbol esquerre deuen ser menors que la clau del nodo, i les claus dels nodos pertanyents al seu subárbol dret deuen ser majors que la clau del nodo. Estos subárboles deuen calificar també com a arbres de busca binaris.
La complexitat temporal del algoritme de busca en un arbre de busca binaria és l'altura del propi arbre, la qual és menor que O(log n) per a un arbre que conté n elements.
B-Tree
Els B-Trees són generalisacions dels arbres de busca binaria que poden tindre un número variable de subárboles en cada nodo. Si ben els nodos fills tenen un ranc predefinit, no necessàriament contindran senyes, lo que significa que els B-Trees potencialment poden desperdiciar una miqueta d'espai. La ventaja és que este tipo d'arbre no necessiten ser reequilibrado en tanta freqüència com atres arbres.
Pel ranc variable de la llongitut dels seus nodos, els B-trees estan pensats per a sistemes que lligen grans blocs de senyes. També s'usen comunament en bases de senyes.
La complexitat temporal de buscar en un B-Tree és O(log n).
(a,b)-tree
Un (a,b)-tree és un arbre de busca a on tots les seues fulles tenen la mateixa profunditat. Cada nodo té a lo manco a fills i com a molt b fills, mentres que la raïl de l'arbre posseïx entre 2 i b fills.
a i b poden ser elegits usant la fòrmula següent:[2]
La complexitat temporal de buscar en un (a,b)-tree és O(log n).
Arbre de busca ternaria
Un arbre de busca ternaria és un tipo de trie que pot tindre 3 nodos: un fill menor, un fill igual i un fill major. Cada nodo almagasena un sol caràcter i l'arbre en sí s'ordena de la mateixa forma que un arbre de busca binaria, en l'excepció d'un possible tercer nodo.
La busca en un arbre de busca ternaria implica passar un string per a comprovar si algun camí de l'arbre ho conté.
La complexitat temporal de buscar en un arbre de busca ternaria equilibrat és O (log n).
Algoritmes de Busca
Buscant una Clau Específica
Suponent que l'arbre està ordenat, podem prendre una clau i intentar insertar-ho dins de l'arbre. Els següents algoritmes estan generalisats per a arbres de busca binaria, pero la mateixa idea pot aplicar-se a atres tipos d'arbres.
Recursivo
busqueda-recursiva(clau, nodo)
if nodo és NULL
return ARBOL_VACIO
if clau < nodo.clau
return busqueda-recursiva(clau, nodo.fill_esquerre)
else if clau > nodo.clau
return busqueda-recursiva(clau, nodo.fill_dret)
else
return nodo
Iterativo
busqueda-iterativa(clau, nodo)
nodoActual := nodo
while nodoActual is not NULL
if nodoActual.clau = clau
return nodoActual
else if nodoActual.clau > clau
nodoActual := nodoActual.fill_esquerre
else
nodoActual := nodoActual.fill_dret
Buscant Mínim i Màxim
En un arbre ordenat, el mínim es troba en el nodo més a l'esquerra, mentres que el màxim es troba en el nodo més a la dreta.[3]
Mínim
busca-minimo(nodo)
if nodo is NULL
return ARBOL_VACIO
minimo := nodo
while minimo.fill_esquerre is not NULL
minimo := minimo.fill_esquerre
return minimo.clau
Màxim
busca-maximo(nodo)
if nodo is NULL
return ARBOL_VACIO
maximo := nodo
while maximo.fill_dret is not NULL
maximo := maximo.fill_dret
return maximo.clau
Vore també
Referències
- ↑ Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures
- ↑ Toal, Ray. "(a,b) Trees"
- ↑ Gildea, Donen (2004). "Binary Search Tree"
Referències
- Este artícul conté una traducció derivada de «Árbol de búsqueda» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.