Add attributes to avl functions

This PR redoes #140
We already had a case where the `__nonnull__` attribute was missing and the function did crash because of it. So I would highly apprechiate keeping both the attribute and the check. It is also not that much code.