Pruebas

Probar el invariante del BST

El invariante del BST se puede comprobar entero: cada nodo tiene que estar dentro del intervalo que le dejan sus antepasados.

¿Qué pruebas comprueban el invariante de un BST?Comprobar solo que cada hijo izquierdo es menor que su padre y cada derecho, mayorRecorrer en orden y comprobar que las claves salen estrictamente crecientesComprobar para cada nodo que su clave está en el intervalo que le dejan sus antepasadosComparar el recorrido en orden con el de un conjunto ordenado simple tras miles de inserciones al azarInsertar 100 claves al azar y comprobar que la altura nunca pasa de 20