Are there search algorithms that perform better on a Rope than a String?
Rooted trees, balanced or not, can be traversed in linear time via depth-first search. Actual implementations of balanced trees usually provide a way to iterate through it, taking amortized $O(1)$ for each step. So any algorithm will work without $O(\log n)$ overhead if it makes only a single pass through the string (or if it only requires a small bounded sliding window).