algorithm - insercion - ¿Diferencia entre la búsqueda binaria y el árbol de búsqueda binario?
arbol binario de busqueda python (3)
¿Cuál es la diferencia entre la búsqueda binaria y el árbol de búsqueda binario?
¿Son lo mismo? Al leer internet se ve que el segundo es solo para árboles (hasta 2 nodos hijos) y la búsqueda binaria no sigue esta regla. No lo entendí del todo
Árboles de búsqueda binaria
Un nodo en un árbol binario es una estructura de datos que tiene un elemento y una referencia a otros dos árboles binarios, típicamente llamados subárboles izquierdo y derecho. Es decir, un nodo presenta una interfaz como esta:
Node:
element (an element of some type)
left (a binary tree, or NULL)
right (a binary tree, or NULL)
Un árbol binario de búsqueda es un árbol binario (es decir, un nodo, típicamente llamado raíz) con la propiedad de que los subárboles izquierdo y derecho también son árboles de búsqueda binarios, y que todos los elementos de todos los nodos en el subárbol izquierdo son menores que el elemento raíz, y todos los elementos de todos los nodos en el subárbol derecho son mayores que el elemento raíz. P.ej,
5
/ /
/ /
2 8
/ / / /
1 3 6 9
Búsqueda binaria
La búsqueda binaria es un algoritmo para encontrar un elemento en el árbol de búsqueda binario. (A menudo se expresa como una forma de buscar una colección ordenada, y esta es una descripción equivalente. Describiré la equivalencia después). Es esto:
search( element, tree ) {
if ( tree == NULL ) {
return NOT_FOUND
}
else if ( element == tree.element ) {
return FOUND_IT
}
else if ( element < tree.element ) {
return search( element, tree.left )
}
else {
return search( element, tree.right )
}
}
Normalmente, este es un método eficiente de búsqueda porque en cada paso puede eliminar la mitad del espacio de búsqueda. Por supuesto, si tiene un árbol de búsqueda binaria mal equilibrado, puede ser ineficiente (puede degradarse a búsqueda lineal). Por ejemplo, tiene un rendimiento pobre en un árbol como:
3
/
4
/
5
/
6
Búsqueda binaria en matrices
La búsqueda binaria a menudo se presenta como un método de búsqueda para matrices ordenadas. Esto no contradice la descripción anterior. De hecho, lo que destaca es el hecho de que realmente no nos importa cómo se implementa un árbol de búsqueda binario; nos importa que podamos tomar un objeto y hacer tres cosas con él: obtener un elemento, obtener un subobjeto izquierdo y obtener un subobjeto correcto (sujeto, por supuesto, a las restricciones sobre los elementos de la izquierda) menos que el elemento, y los elementos en el derecho son mayores, etc.).
Podemos hacer las tres cosas con una matriz ordenada. Con una matriz ordenada, el "elemento" es el elemento medio de la matriz, el subobjeto izquierdo es la subcadena a la izquierda y el subobjeto derecho es la subestructura a la derecha de la misma. Por ejemplo, la matriz
[1 3 4 5 7 8 11]
corresponde al árbol:
5
/ /
/ /
3 8
/ / / /
1 4 7 11
Por lo tanto, podemos escribir un método de búsqueda binario para matrices como esta:
search( element, array, begin, end ) {
if ( end <= begin ) {
return NOT_FOUND
}
else {
midpoint = begin+(end-begin)/2
a_element = array[midpoint]
if ( element == midpoint ) {
return FOUND_IT
}
else if ( element < midpoint ) {
return search( element, array, begin, midpoint )
}
else {
return search( element, array, midpoint, end )
}
}
}
Conclusión
Como se presenta a menudo, la búsqueda binaria se refiere al algoritmo basado en matrices presentado aquí, y el árbol de búsqueda binaria se refiere a una estructura de datos basada en árbol con ciertas propiedades. Sin embargo, las propiedades que requiere la búsqueda binaria y las propiedades que tienen los árboles de búsqueda binaria hacen que estas dos caras de la misma moneda. Ser un árbol de búsqueda binario a menudo implica una implementación particular, pero en realidad se trata de proporcionar ciertas operaciones y satisfacer ciertas restricciones. La búsqueda binaria es un algoritmo que funciona en estructuras de datos que tienen estas operaciones y cumplen estas restricciones.
El árbol de búsqueda binaria es solo una estructura de datos, no un algoritmo, mientras que la búsqueda binaria es un algoritmo en el que compara el valor de la clave de búsqueda con el valor de la clave del elemento medio de la matriz. Si las claves coinciden, se ha encontrado un elemento coincidente y se devuelve su índice o posición. De lo contrario, si la clave de búsqueda es menor que la clave del elemento medio, entonces el algoritmo repite su acción en la subarranque a la izquierda del elemento medio o, si la clave de búsqueda es mayor, en la sub-matriz a la derecha. Si la matriz restante que se va a buscar está vacía, entonces la clave no se puede encontrar en la matriz y se devuelve una indicación especial "no encontrado"
No, no son lo mismo.
- Una estructura de datos de árbol
- Cada nodo tiene hasta 2 niños
- El subárbol izquierdo de un nodo contiene solo nodos con claves menores que la clave del nodo
- El subárbol derecho de un nodo contiene solo nodos con claves mayores que la clave del nodo
- Algoritmo que funciona en una estructura de datos ordenada (generalmente, pero no necesariamente, una matriz) y, en cada paso, busca el valor en el medio y recurre a la izquierda o a la derecha, dependiendo de si el valor objetivo es más pequeño o mayor que el valor en el medio (o detenerse si es igual).
Y, por supuesto, una estructura de datos es:
Una forma particular de almacenar y organizar datos en una computadora para que se pueda usar de manera eficiente.
Mientras que un algoritmo es:
Un procedimiento paso a paso para los cálculos.
El proceso de búsqueda en un árbol de búsqueda binaria (donde buscamos un valor específico en el árbol) puede considerarse similar (o una instancia de, dependiendo de sus definiciones y de si está utilizando una búsqueda binaria equilibrada BST), ya que esto también mira al elemento ''medio'' y vuelve a aparecer ya sea a la izquierda o derecha, dependiendo del resultado de la comparación entre ese valor y el valor objetivo.