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 de cada nodo debe ser mayor que cualquier clave de los subárboles de la izquierda y menor que cualquier clave de los subárboles de la derecha. [1]
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 ambos extremos 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 el par clave-valor completo en esa ubicación en particular.
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 temporal del peor de los casos para buscar en un árbol de búsqueda binario es la altura del árbol , que puede ser tan pequeña como O(log n) para un árbol con n elementos.
Los árboles B son generalizaciones de los á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 reequilibrarse con tanta frecuencia como otros árboles autoequilibrados .
Debido al rango variable de 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 temporal para buscar un árbol B es O (log n).
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.
a y b se pueden decidir con la siguiente fórmula: [2]
La complejidad temporal para buscar un árbol (a,b) es O(log n).
Un árbol de búsqueda ternario es un tipo de árbol que puede tener 3 nodos: un hijo bajo, un hijo igual y un hijo alto. Cada nodo almacena un único carácter y el árbol en sí está ordenado de la misma manera que un árbol de búsqueda binario, 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 temporal para buscar en un árbol de búsqueda ternario equilibrado es O (log n).
Suponiendo que el árbol esté ordenado, podemos tomar una clave 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.
búsqueda recursiva (clave, nodo) si el nodo es NULL devuelve EMPTY_TREE si clave <nodo.clave devolver búsqueda recursiva (clave, nodo.izquierda) de lo contrario si clave > nodo.clave devolver búsqueda recursiva (clave, nodo.derecha) otro nodo de retorno
búsquedaIterativa(clave,nodo) nodoactual := nodo mientras que currentNode no es NULL si currentNode.key = clave devuelve currentNode en caso contrario si currentNode.key > clave NodoActual := NodoActual.izquierda demás NodoActual := NodoActual.derecho
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]
findMinimum(nodo) si el nodo es NULL devuelve EMPTY_TREE min := nodo mientras min.left no es NULL min := min.izquierda devolver clave min.
findMaximum(nodo) si el nodo es NULL devuelve EMPTY_TREE máximo: = nodo mientras que max.right no es NULL max := max.derecha devolver clave máxima
