El tipo abstracto de datos de los árboles binarios de búsqueda en Haskell
Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los árboles binarios de búsqueda.
Un árbol binario de búsqueda (ABB) (binary search tree en inglés) es un árbol binario tal que el valor de cada nodo es mayor que los valores de su subárbol izquierdo y es menor que los valores de su subárbol derecho y, además, ambos subárboles son árboles binarios de búsqueda. Por ejemplo, al almacenar los valores de [2,3,4,5,6,8,9] en un ABB se puede obtener los siguientes ABB:
|
1 2 3 4 5 6 7 |
5 5 / \ / \ 2 6 3 8 \ \ / \ / \ 4 8 2 4 6 9 / \ 3 9 |
El objetivo principal de los ABB es reducir el tiempo de acceso a los valores.
El contenido del resto del artículo es el siguiente:
- la signatura del TAD de los árboles binarios de búsqueda;
- las propiedades del TAD de los árboles binarios de búsqueda;
- la implementación, en Haskell, de los árboles binarios de búsqueda mediante tipos de datos algebraicos.
- la comprobación con QuickCheck de sus propiedades.
Read More “El tipo abstracto de datos de los árboles binarios de búsqueda en Haskell”