[pavpanchekha]

AVL trees give shorter path lengths. So the resulting structure ends up being better, depending on your exact balance of insertion and selection.