Árbol de búsqueda

En informática , un árbol de búsqueda es una estructura de datos en forma 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 que permiten un tiempo de búsqueda eficiente, siempre que el árbol esté razonablemente equilibrado, es decir, que las hojas de cada extremo tengan una profundidad comparable. Existen varias estructuras de datos de árboles de búsqueda, varias de las cuales también permiten una inserción y eliminación eficiente de elementos, operaciones que luego deben mantener el equilibrio del árbol.

Los árboles de búsqueda se utilizan a menudo para implementar una matriz asociativa . El algoritmo de á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.

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

La complejidad temporal del peor caso 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 binarios de búsqueda, ya que pueden tener una cantidad 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 la longitud de sus nodos, los árboles B están optimizados para sistemas que leen grandes bloques de datos y también se utilizan 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 en el que todas sus hojas tienen la misma profundidad. Cada nodo tiene al menos un hijo 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]

${\displaystyle 2\leq a\leq {\frac {(b+1)}{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 de bajo nivel, un hijo igual y un hijo de alto nivel. Cada nodo almacena un solo 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 localizarla dentro del árbol. Los siguientes algoritmos se generalizan para árboles de búsqueda binaria, 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)
    De lo contrario,
         nodo
 de retorno

searchIterative(clave, nodo)
    nodoActual := nodo
    mientras currentNode no sea NULL 
        si currentNode.key = key
             devuelve currentNode
         de lo contrario si currentNode.key > key
            nodoActual := nodoActual.izquierda
        demás
            nodoActual := nodoActual.derecha

En un árbol ordenado, el mínimo se ubica en el nodo más a la izquierda, mientras que el máximo se ubica 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 sea NULL
        min := min.izquierda
    devolver min.key

findMaximum(nodo)
     si el nodo es NULL 
        devuelve  EMPTY_TREE
    máx := nodo
    mientras max.right no sea NULL
        máx := máx.derecha
    devolver clave máxima

• Intentar
• Árbol binario
• Búsqueda en profundidad