Most programs don't use much rootfs space - the bulk is installed to /opt instead. Generally rootfs space gets used up by libraries, so it's only when you've uninstalled all programs using a library that the space can get freed up.