Algoritmos de aprendizaje

Capítulo 6. Árboles binarios: El infinito en lapalma de tu mano

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

En este capítulo aprenderás

• Cómo crear y manipular árboles binarios insertando, eliminando y buscando valores.

• Cómo gestionar un árbol de búsqueda binario que cumpla la propiedad global de que:

  • Los valores del subárbol izquierdo de un nodo son todos menores o iguales que el valor de ese nodo.

  • Los valores del subárbol derecho de un nodo son todos mayores o iguales que el valor de ese nodo.

• Que las operaciones de búsqueda, inserción y eliminación pueden ser O(log N) en árboles binarios equilibrados, pero pueden degradarse hasta convertirse en un inaceptable O(N) si no tienes cuidado.

• Cómo reequilibrar un árbol de búsqueda binario tras las operaciones de inserción y eliminación para garantizar un rendimiento de O(log N) para la búsqueda, la inserción y la eliminación.

• Cómo recorrer un árbol de búsqueda binario para procesar cada valor en orden ascendente con un rendimiento O(N).

• Cómo utilizar una estructura de árbol binario para implementar un tipo de datos de tabla de símbolos con la ventaja añadida de que sus claves pueden recuperarse ordenadas.

• Cómo utilizar una estructura de árbol binario para implementar una cola de prioridad con la ventaja añadida de que puedes generar las entradas (clave, valor) en orden de prioridad sin interrumpir la cola de prioridad.

Cómo empezar