runtime - recursiva - para que sirve un arbol binario
Los tiempos de búsqueda para el árbol de búsqueda binaria (3)
¿Alguien sabe cómo calcular el tiempo de búsqueda para un árbol de búsqueda binario (es decir, el peor de los casos, el mejor caso y el promedio de casos)?
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).
Podría querer etiquetar esto como "tarea". Este es un buen punto de partida: http://en.wikipedia.org/wiki/Binary_search_tree
En general, un árbol de búsqueda binaria equilibrada tiene una búsqueda en el peor de los casos de O (log n), el mejor caso de O (1) (cuando el valor deseado es la raíz) y un caso promedio de O (log n) (las hojas contener 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 vinculada y puede tener una forma como la siguiente:
1
/ /
2
/ /
3
/ /
4
/ /
En esta situación, el tiempo de acceso al peor de los casos es O (n) .
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 (log 2 n) para un árbol perfectamente equilibrado, ya que reduce el espacio de búsqueda a la mitad para cada nivel de árbol.
El caso promedio está en algún lugar entre esos dos y depende completamente de los datos :-)
Como rara vez se puede controlar la secuencia en la que se insertan los datos en un árbol, los árboles con autoequilibrio son usualmente preferibles ya que, aunque 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, puedes ver que obtienes 2 n -1 nodos por cada n niveles. Eso significa que para 15 nodos, nunca debe buscar más de cuatro nodos para encontrarlo (por ejemplo, para encontrar 13 , busca 8 , 12 , 14 y 13 ). De ahí viene la log 2n figura.
Un árbol desequilibrado degenerado, como ya se dijo, es una lista vinculada. Si sus datos llegaron en secuencia y lo insertó en un árbol binario desequilibrado, obtendría:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
|
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15
Para encontrar 13 en ese caso, necesitaría buscar 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 y 13 , por lo tanto O (n).