Add avl tests

This pull request adds and fixes the avl tests
Why was the `const` keyword removed?