Árbol de búsqueda
En ciencias de la computación, un árbol de búsqueda es una estructura de datos de tipo árbol utilizado para localizar llaves concretas dentro de un conjunto. Para que un árbol pueda funcionar como árbol de búsqueda en cada nodo tiene que cumplirse que su llave tiene que ser más grande que cualquier llave contenida en su subárbol izquierdo y menor que cualquier llave contenida en su subárbol derecho.[1]
La ventaja de los árboles de búsqueda es su eficiencia en el tiempo de búsqueda, dado que el árbol está razonablemente balanceado, lo que quiere decir que todas las hojas se encuentran a profundidades similares. Existen varias estructuras de datos de tipo árbol de búsqueda, varias de las cuales también permiten la inserción y eliminación eficiente de elementos, operaciones que tienen que mantener el equilibrio del árbol.
Los árboles de búsqueda a menudo son utilizados para implementar vectores asociativos. El algoritmo del árbol de búsqueda utiliza la llave del par llave-valor para encontrar una ubicación, y entonces la aplicación almacena el par entero en esa ubicación.
Tipos de Árboles[editar]
Árbol de Búsqueda Binaria[editar]
Un árbol de búsqueda binaria es una estructura de datos basada en nodos donde cada nodo contiene una llave y dos subárboles, el izquierdo y el derecho. Para todos los nodos, las llaves de los nodos pertenecientes a su subárbol izquierdo deben ser menores que la llave del nodo, y las llaves de los nodos pertenecientes a su subárbol derecho deben ser mayores que la llave del nodo. Estos subárboles deben calificar también como árboles de búsqueda binarios.
La complejidad temporal del algoritmo de búsqueda en un árbol de búsqueda binaria es la altura del propio árbol, la cual es menor que O(log n) para un árbol que contiene n elementos.
B-Tree[editar]
Los B-Trees son generalizaciones de los árboles de búsqueda binaria que pueden tener un número variable de subárboles en cada nodo. Si bien los nodos hijos tienen un rango predefinido, no necesariamente contendrán datos, lo que significa que los B-Trees potencialmente pueden desperdiciar algo de espacio. La ventaja es que este tipo de árbol no necesitan ser reequilibrado con tanta frecuencia como otros árboles.
Debido al rango variable de la longitud de sus nodos, los B-trees están pensados para sistemas que leen grandes bloques de datos. También se usan comúnmente en bases de datos.
La complejidad temporal de buscar en un B-Tree es O(log n).
(a,b)-tree[editar]
Un (a,b)-tree es un árbol de búsqueda donde todas sus hojas tienen la misma profundidad. Cada nodo tiene al menos a hijos y a lo sumo b hijos, mientras que la raíz del árbol posee entre 2 y b hijos.
a y b pueden ser elegidos usando la fórmula siguiente:[2]
La complejidad temporal de buscar en un (a,b)-tree es O(log n).
Árbol de búsqueda ternaria[editar]
Un árbol de búsqueda ternaria es un tipo de trie que puede tener 3 nodos: un hijo menor, un hijo igual y un hijo mayor. Cada nodo almacena un solo carácter y el árbol en sí se ordena de la misma forma que un árbol de búsqueda binaria, con la excepción de un posible tercer nodo.
La búsqueda en un árbol de búsqueda ternaria implica pasar un string para comprobar si algún camino del árbol lo contiene.
La complejidad temporal de buscar en un árbol de búsqueda ternaria equilibrado es O (log n).
Algoritmos de Búsqueda[editar]
Buscando una Llave Específica[editar]
Suponiendo que el árbol está ordenado, podemos tomar una llave e intentar insertarlo dentro del árbol. Los siguientes algoritmos están generalizados para árboles de búsqueda binaria, pero la misma idea puede aplicarse a otros tipos de árboles.
Recursivo[editar]
busqueda-recursiva(llave, nodo)
if nodo es NULL
return ARBOL_VACIO
if llave < nodo.llave
return busqueda-recursiva(llave, nodo.hijo_izquierdo)
else if llave > nodo.llave
return busqueda-recursiva(llave, nodo.hijo_derecho)
else
return nodo
Iterativo[editar]
busqueda-iterativa(llave, nodo)
nodoActual := nodo
while nodoActual is not NULL
if nodoActual.llave = llave
return nodoActual
else if nodoActual.llave > llave
nodoActual := nodoActual.hijo_izquierdo
else
nodoActual := nodoActual.hijo_derecho
Buscando Mínimo y Máximo[editar]
En un árbol ordenado, el mínimo se encuentra en el nodo más a la izquierda, mientras que el máximo se encuentra en el nodo más a la derecha.[3]
Mínimo[editar]
busca-minimo(nodo)
if nodo is NULL
return ARBOL_VACIO
minimo := nodo
while minimo.hijo_izquierdo is not NULL
minimo := minimo.hijo_izquierdo
return minimo.llave
Máximo[editar]
busca-maximo(nodo)
if nodo is NULL
return ARBOL_VACIO
maximo := nodo
while maximo.hijo_derecho is not NULL
maximo := maximo.hijo_derecho
return maximo.llave
Véase también[editar]
Referencias[editar]
- ↑ Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures
- ↑ Toal, Ray. "(a,b) Trees"
- ↑ Gildea, Dan (2004). "Binary Search Tree"
| Control de autoridades |
|
|---|
Datos: Q621673
Multimedia: Search trees / Q621673