- Si implementamos un árbol de búsqueda binario equilibrado, siempre podemos mantener el costo de insert (), delete (), lookup () a O (logN) donde N es el número de nodos en el árbol, por lo que el beneficio es que las búsquedas se puede hacer en tiempo logarítmico, lo que importa mucho cuando N es grande.
- Tenemos un pedido de claves almacenadas en el árbol. Cada vez que necesitemos atravesar el orden creciente (o decreciente) de las teclas, solo tenemos que hacer el recorrido en orden (e invertir en orden) en el árbol.
- Esto es diferente a la tabla hash donde el costo de búsqueda se puede amortizar O (1) pero no hay pedidos de artículos almacenados en la tabla hash. No hay una forma directa / ingenua de iterar sobre todas las claves en un orden ordenado.
- Otra cosa clave en la que centrarse es el “costo amortizado de O (1)”. Con las tablas hash, necesitamos dimensionarlas adecuadamente, de lo contrario, la eficiencia de todas las operaciones (especialmente la búsqueda) se degradará. Por otro lado, con árboles de búsqueda binarios balanceados, todas las operaciones (insertar, buscar, eliminar) están garantizadas para trabajar en O (logN) complejidad de tiempo.
- Podemos implementar estadísticas de pedidos con el árbol de búsqueda binario: el enésimo elemento más pequeño y el más grande. Esto se debe a que es posible ver la estructura de datos como una matriz ordenada.
- También podemos hacer consultas de rango: encontrar claves entre N y M (N <= M).
- BST también se puede utilizar en el diseño de asignadores de memoria para acelerar la búsqueda de bloques libres (fragmentos de memoria) e implementar algoritmos de mejor ajuste donde nos interese encontrar el fragmento libre más pequeño con un tamaño mayor o igual al tamaño especificado en solicitud de asignación.
- Lo principal a recordar es que siempre debemos implementar un árbol de búsqueda binaria equilibrado: árbol AVL, árbol Rojo-Negro, árbol Splay. De lo contrario, el costo de las operaciones puede no ser logarítmico y degenerar en una búsqueda lineal en una matriz.
¿Cuáles son los beneficios del árbol de búsqueda binario?
Related Content
¿Qué se entiende por recursión?
¿Cuáles son los algoritmos hash más comunes además de MD5 y SHA?
¿Qué es el diseño paramétrico y cuáles son algunos ejemplos de él?
Está en el nombre. Los árboles de búsqueda binarios permiten una búsqueda rápida de artículos.
Considere una matriz A de n elementos. Si busca k en A, el peor de los casos es que todos los elementos en A serán examinados. Eso significa la complejidad temporal de la búsqueda es O (n).
Ahora considere un árbol binario T. Una búsqueda de k en T solo tendrá que buscar en la mayoría de los elementos h, donde h es la altura del árbol. Como el tiempo crece con la altura, la complejidad es O (log n), una gran mejora con respecto a O (n).
More Interesting
¿Existe un algoritmo para identificar el género basado en el nombre?
Dado un problema, ¿cómo puedo decidir si usar un enfoque codicioso o dividir y conquistar?
¿Cómo se imprime el reverso de una pila de objetos iterables?
¿Cómo se puede incorporar un algoritmo adaptativo en un sistema operativo?
Cómo argumentar la corrección del tipo radix
¿Es posible escribir un método que muestre todos los elementos en una lista enlazada circular?
