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

Binary search tree

Arbre de busca binaria

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 binarios.

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 els seus fulls 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]

2 \leq a \leq \frac{(b + 1)}{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.

[1] Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures

[2] Toal, Ray. "(a,b) Trees"

[3] Gildea, Donen (2004). "Binary Search Tree"

[1]

[2]

[3]