Los árboles de búsqueda binarios son colecciones que pueden mantener eficientemente un conjunto de datos que cambia dinámicamente en orden ordenado, para algún tipo “ordenable”. *
Tener una matriz ordenada es útil para muchas tareas porque permite utilizar la búsqueda binaria para localizar elementos de manera eficiente. El problema con una matriz ordenada es que los elementos no se pueden insertar y eliminar de manera eficiente.
El árbol de búsqueda binario es una forma diferente de estructurar los datos para que todavía se pueda buscar en binario (o se puede usar un procedimiento muy similar), pero es más fácil agregar y eliminar elementos. En lugar de simplemente almacenar los elementos contiguamente de menor a mayor, los datos se mantienen en muchos fragmentos separados, lo que hace que agregar un elemento sea cuestión de agregar un nuevo fragmento de memoria y vincularlo a los fragmentos existentes.
- ¿Cómo se almacena una matriz bidimensional en la memoria?
- ¿Cuál es el número de elementos comunes en dos conjuntos de permutación?
- ¿Alguien puede proporcionarme un algoritmo de muestra en CS para ISC 2017?
- ¿Por qué necesitamos un árbol AVL en informática?
- ¿Es mejor aprender estructuras de datos y algoritmos en C ++ o Java?
Los árboles de búsqueda binarios admiten todo lo que puede obtener de una matriz ordenada: búsqueda eficiente, recorrido hacia adelante / atrás en orden desde cualquier elemento dado, búsqueda de elementos predecesor / sucesor y consultas máximo / mínimo, con el beneficio adicional de inserciones y eliminaciones eficientes. Con un árbol de búsqueda binaria de equilibrio automático (BST), todo lo anterior se ejecuta en tiempo logarítmico.
Por ejemplo
Imagine que tiene una matriz con un millón de elementos.
Desea insertar un elemento en la ubicación 5.
Entonces inserta al final de la matriz y luego ordena.
Digamos que la matriz está llena; eso es O (nlog n), que es 1,000,000 * 6 = 6,000,000 operaciones.
Imagina que tienes un árbol equilibrado.
Eso es O (log n), más un bit para equilibrar = 6 + un bit, llámelo 10 operaciones.
Entonces, acaba de gastar 6,000,000 de operaciones clasificando su matriz. Entonces quieres encontrar ese elemento. ¿Qué haces? búsqueda binaria – O (log n) – ¡que es exactamente lo mismo que harás cuando busques en el árbol!
Ahora imagine que quiere asignar otro elemento.
¡Tu conjunto está lleno! ¿qué haces? reasignar la matriz con n elementos adicionales y memcpy el lote? realmente quieres memcpy 4mbytes?
En un árbol de búsqueda binario, solo agrega otro elemento
