Árbol binario de búsqueda
1. Concepto y su introducción
El árbol binario de búsqueda (en inglés: Binary Search Tree), también conocido como árbol de búsqueda binaria, árbol binario de búsqueda, árbol binario ordenado o árbol binario de clasificación. Cumple las siguientes condiciones:
- Si su subárbol izquierdo no está vacío, todos los valores de los nodos del subárbol izquierdo son menores que su nodo raíz.
- Si su subárbol derecho no está vacío, todos los valores de los nodos del subárbol derecho son mayores que su nodo raíz.
Sus subárboles izquierdo y derecho también son árboles binarios de búsqueda.
Como se muestra en la siguiente figura:
2. Instrucciones de aplicación
El árbol binario de búsqueda tiene operaciones eficientes de inserción, eliminación y consulta.
La complejidad temporal promedio esO(log n), y en el peor caso esO(n). El árbol binario de búsqueda, a diferencia del montón, no es necesariamente un árbol binario completo; en la capa inferior no es fácil representarlo directamente con un arreglo, por lo que se utiliza una lista enlazada para implementar el árbol binario de búsqueda.
| Buscar elemento | Insertar elemento | Eliminar elemento | |
|---|---|---|---|
| Arreglo normal | O(n) | O(n) | O(n) |
| Arreglo ordenado | O(logn) | O(n) | O(n) |
| Árbol binario de búsqueda | O(logn) | O(logn) | O(logn) |
A continuación, primero presentamos el método de búsqueda binaria en forma de arreglo como referencia conceptual, y luego continuamos presentando el método de búsqueda en el árbol binario de búsqueda.
3. Diagrama del proceso del método de búsqueda binaria
La idea del método de búsqueda binaria fue propuesta en 1946. El problema de búsqueda es un problema fundamental muy importante en computación; solo para secuencias ordenadas se puede usar el método de búsqueda binaria. Si queremos buscar un elemento, primero observamos la relación de tamaño entre el valor V en el medio del arreglo y el dato a buscar, y se distinguen tres casos:
- 1. Si es igual al dato buscado, se encuentra directamente.
- 2. Si es menor que V, se continúa la búsqueda en el grupo de la parte menor que V.
- 3. Si es mayor que V, se continúa la búsqueda en el grupo de la parte mayor que V.
4. Código de ejemplo en Java
Descarga del paquete de código fuente:Download
Código del archivo src/ejemplo/binary/BinarySearch.java:
/**
* Método de búsqueda binaria
*/
public class BinarySearch {
// Método de búsqueda binaria: busca target en el arreglo ordenado arr
// Si se encuentra target, devuelve el índice correspondiente index
// Si no se encuentra target, devuelve -1
public static int find(Comparable[] arr, Comparable target) {
// Busca target en arr[l...r]
int l = 0, r = arr.length-1;
while( l <= r ){
//int mid = (l + r)/2;
// Para evitar el desbordamiento de enteros en casos extremos, usa la siguiente lógica para calcular mid
int mid = l + (r-l)/2;
if( arr[mid].compareTo(target) == 0 )
return mid;
if( arr[mid].compareTo(target) > 0 )
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
}