Árbol de búsqueda - Search tree
En informática , un árbol de búsqueda es una estructura de datos de árbol que se utiliza para localizar claves específicas dentro de un conjunto. Para que un árbol funcione como árbol de búsqueda, la clave para cada nodo debe ser mayor que cualquier clave en los subárboles de la izquierda y menor que cualquier clave en los subárboles de la derecha.
La ventaja de los árboles de búsqueda es su tiempo de búsqueda eficiente dado que el árbol está razonablemente equilibrado, es decir, las hojas en cada extremo tienen profundidades comparables. Existen varias estructuras de datos de árbol de búsqueda, varias de las cuales también permiten la inserción y eliminación eficiente de elementos, cuyas operaciones luego deben mantener el equilibrio del árbol.
Los árboles de búsqueda se utilizan a menudo para implementar una matriz asociativa . El algoritmo del árbol de búsqueda utiliza la clave del par clave-valor para encontrar una ubicación, y luego la aplicación almacena todo el par clave-valor en esa ubicación en particular.
Tipos de árboles
Árbol de búsqueda binaria
Un árbol de búsqueda binaria es una estructura de datos basada en nodos donde cada nodo contiene una clave y dos subárboles, el izquierdo y el derecho. Para todos los nodos, la clave del subárbol izquierdo debe ser menor que la clave del nodo y la clave del subárbol derecho debe ser mayor que la clave del nodo. Todos estos subárboles deben calificar como árboles de búsqueda binarios.
La complejidad de tiempo en el peor de los casos para buscar un árbol de búsqueda binaria es la altura del árbol , que puede ser tan pequeña como O (log n) para un árbol con n elementos.
Árbol B
Los árboles B son generalizaciones de árboles de búsqueda binarios en el sentido de que pueden tener un número variable de subárboles en cada nodo. Si bien los nodos secundarios tienen un rango predefinido, no necesariamente estarán llenos de datos, lo que significa que los árboles B pueden potencialmente desperdiciar algo de espacio. La ventaja es que los árboles B no necesitan ser reequilibrados con tanta frecuencia como otros árboles autoequilibrados .
Debido al rango variable de la longitud de sus nodos, los árboles B están optimizados para sistemas que leen grandes bloques de datos, también se usan comúnmente en bases de datos.
La complejidad de tiempo para buscar un árbol B es O (log n).
(a, b) -árbol
Un árbol (a, b) es un árbol de búsqueda donde todas sus hojas tienen la misma profundidad. Cada nodo tiene al menos a hijos y como máximo b hijos, mientras que la raíz tiene al menos 2 hijos y como máximo b hijos.
una y b se pueden decidir con la siguiente fórmula:
La complejidad de tiempo para buscar un árbol (a, b) es O (log n).
Árbol de búsqueda ternario
Un árbol de búsqueda ternario es un tipo de árbol que puede tener 3 nodos: un niño bajo, un niño igual y un niño alto. Cada nodo almacena un solo carácter y el árbol en sí está ordenado de la misma manera 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 ternario implica pasar una cadena para probar si alguna ruta la contiene.
La complejidad de tiempo para buscar un árbol de búsqueda ternario equilibrado es O (log n).
Algoritmos de búsqueda
Buscando una clave específica
Suponiendo que el árbol está ordenado, podemos tomar una llave e intentar ubicarla dentro del árbol. Los siguientes algoritmos están generalizados para árboles de búsqueda binarios, pero la misma idea se puede aplicar a árboles de otros formatos.
Recursivo
search-recursive(key, node)
if node is NULL
return EMPTY_TREE
if key < node.key
return search-recursive(key, node.left)
else if key > node.key
return search-recursive(key, node.right)
else
return node
Iterativo
searchIterative(key, node)
currentNode := node
while currentNode is not NULL
if currentNode.key = key
return currentNode
else if currentNode.key > key
currentNode := currentNode.left
else
currentNode := currentNode.right
Buscando mínimo y máximo
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.
Mínimo
findMinimum(node)
if node is NULL
return EMPTY_TREE
min := node
while min.left is not NULL
min := min.left
return min.key
Máximo
findMaximum(node)
if node is NULL
return EMPTY_TREE
max := node
while max.right is not NULL
max := max.right
return max.key