¿Alguien sabe cómo calcular el tiempo de búsqueda para un árbol de búsqueda binaria (es decir, el peor de los casos, el mejor de los casos y el promedio de casos)?Tiempos de búsqueda para el árbol de búsqueda binaria
Para un árbol no autoequilibrado (posible pero inusual para un árbol de búsqueda), el peor caso es O (n), que es para el árbol binario degenerado (una lista vinculada).
En este caso, debe buscar, en promedio, la mitad de la lista antes de encontrar el elemento deseado.
El mejor caso es O (registro n) para un árbol perfectamente equilibrado, ya que se reduce el espacio de búsqueda a la mitad para cada nivel de árbol.
caso promedio está en algún lugar entre los dos y depende por completo de los datos :-)
Dado que rara vez se llega a controlar la secuencia en la que se insertan datos en un árbol, árboles autobalanceados suelen ser preferible ya , mientras que agregan una pequeña cantidad de tiempo a cada inserción o eliminación, aceleran enormemente la búsqueda. Su peor caso es mucho mejor que los árboles desequilibrados.
8
_______/ \_______
/ \
4 12
__/ \__ __/ \__
/ \ / \
2 6 10 14
/\ /\ /\ /\
1 3 5 7 9 11 13 15
En este árbol perfectamente equilibrado, se puede ver que se obtiene 2 n -1 nodos para cada n niveles. Eso significa que para 15 nodos, nunca tendrá que buscar más de cuatro nodos para encontrarlo (por ejemplo, para encontrar 13, busque 8, 12, 14 y 13). Ahí es donde viene el registro n figura.
Un árbol desequilibrado degenerado, como ya se indicó, es una lista vinculada. Si los datos llegaron en secuencia y se insertaron en un árbol binario desequilibrado, se obtendría:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
|
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15
Para encontrar 13 en ese caso, que había necesidad de buscar 1, 2, 3, 4, 5 , 6, 7, 8, 9, 10, 11, 12 y 13, de ahí O (n).
Puede que quieras etiquetar esto como "tarea". Aquí es un buen punto de partida: http://en.wikipedia.org/wiki/Binary_search_tree
En general, una equilibrada árbol binario de búsqueda tiene una búsqueda del peor caso de O (log n), la mejor caja de O (1) (cuando el valor deseado es la raíz) y un caso promedio de O (log n) (las hojas contienen exponencialmente más valores que sus padres).
El peor caso es el más interesante y se ve fácilmente al reconocer que el primer nivel de un árbol binario tiene 1 nodo, el segundo tiene 2, el tercero tiene 4 y así sucesivamente. Por lo tanto, el número de nodos en un árbol binario de profundidad n es precisamente 2^n - 1. La inversa matemática de la función exponencial es el logaritmo, por lo tanto: O (log n).
Un árbol desequilibrado puede ser tan malo como una lista enlazada y puede tener una forma similar a la siguiente:
1
/\
2
/\
3
/\
4
/\
En esta situación, el tiempo de acceso del peor caso es O (n).
Un árbol desbalanceado es cualquier árbol que no está perfectamente equilibrado (es decir, la profundidad de un subárbol es diferente a otro subárbol). A lo que te refieres (la lista enlazada) es un árbol degenerado. – paxdiablo
Cambiar mi respuesta para ser un poco más preciso. En general, si no especifica "equilibrado", entonces el peor de los casos es O (n), independientemente de si es * en realidad * degenerado. –
La imagen en la publicación se conoce como "árbol de búsqueda binaria sesgada" – RBT
El mejor caso es O (1). el primer elemento podría ser el artículo que está buscando. el peor caso es O (n), es decir, en un árbol sesgado y el caso promedio es O (lg n).
@paxdiablo No es cierto. http://bigocheatsheet.com/ – safaiyeh
pero, ¿qué pasa si se trata de números completamente aleatorios y no están casi equilibrados, existe algún tipo de método para descubrir los casos? –
No, porque depende tanto de su árbol como de lo que esté buscando. – paxdiablo
Existen algoritmos para equilibrar árboles en insertar/eliminar. Por lo tanto, los datos aleatorios no son un problema para la implementación correcta. –