Actually, implementing AVL tree in purely functional way is easy, I'd say it's easier than doing it in the mutable in-place way. It will allocate more, but will

Actually, implementing AVL tree in purely functional way is easy, I'd say it's easier than doing it in the mutable in-place way. It will allocate more, but will have the optimal O(something) complexity. Many other algorithms are much harder, though, especially those requiring fast array indexing (graph search, hash tables, ...)