6.15. Análisis de árboles de búsqueda¶
Con la implementación de un árbol binario de búsqueda ahora completo, haremos un análisis rápido de los métodos que hemos implementado. Veamos primero el método agregar. El factor limitante en su rendimiento es la altura del árbol binario. Recuerde de la sección de vocabulario que la altura de un árbol es el número de aristas entre la raíz y el nodo hoja más profundo. La altura es el factor limitante porque cuando estamos buscando el lugar apropiado para insertar un nodo en el árbol, tendremos que hacer como máximo una comparación en cada nivel del árbol.
¿Cuál será la probable altura de un árbol binario? La respuesta a esta pregunta depende de cómo se agregan las claves al árbol. Si las claves se agregan en un orden aleatorio, la altura del árbol estará alrededor de \(\log_2{n}\) donde \(n\) es el número de nodos en el árbol. Esto se debe a que si las claves están distribuidas aleatoriamente, aproximadamente la mitad de ellas serán menores que la raíz y la otra mitad será mayor que la raíz. Recuerde que en un árbol binario hay un nodo en la raíz, dos nodos en el siguiente nivel y cuatro en el siguiente. El número de nodos en cualquier nivel es \(2^d\) donde \(d\) es la profundidad del nivel. El número total de nodos en un árbol binario perfectamente equilibrado es \(2^{h+1}-1\), donde \(h\) representa la altura del árbol.
Un árbol perfectamente equilibrado tiene el mismo número de nodos en el subárbol izquierdo que en el subárbol derecho. En un árbol binario equilibrado, el peor desempeño de agregar es \(O(\log_2{n})\), donde \(n\) es el número de nodos en el árbol. Note que ésta es la relación inversa respecto al cálculo del párrafo anterior. Así que \(\log_2{n}\) nos da la altura del árbol, y representa el número máximo de comparaciones que agregar necesitará hacer mientras busca el lugar apropiado para insertar un nodo nuevo.
Infortunadamente, ¡es posible construir un árbol de búsqueda que tenga una altura \(n\) insertando simplemente las claves ordenadas! Un ejemplo de tal árbol se muestra en la Figura 6. En este caso, el rendimiento del método agregar es \(O(n)\).
Figura 6: Un árbol binario de búsqueda sesgado daría un desempeño pobre¶
Figura 6: Un árbol binario de búsqueda sesgado daría un desempeño pobre
Ahora que usted entiende que el desempeño del método agregar está limitado por la altura del árbol, probablemente supondrá que otros métodos, obtener, in y del, también están limitados. Dado que obtener busca en el árbol para encontrar la clave, en el peor de los casos se busca hasta el fondo del árbol y no se encuentra ninguna clave. A primera vista del parecería más complicado, ya que podría necesitar buscar el sucesor antes de que la operación de eliminación pueda completarse. Pero recuerde que el peor de los casos para encontrar el sucesor es también la altura del árbol, lo que significa que el trabajo simplemente se duplica. Dado que la duplicación es un factor constante, no cambia el análisis del peor caso de \(O(n)\) para un árbol no equilibrado.