Имеется ли существенное различие в плане скорости основных операций и объеме используемой памяти между АВЛ-деревьями и Красно-Черными деревьями? К сожалению, нигде не могу найти сравнение этих структур. 
Имеются ли в C++ стандартные классы, реализующие один из типов деревьев?

Я знаю, что RB-деревья используются в классе map, но он мне не очень подходит. Задача: найти в множестве строк одну, наиболее похожую на данную. То есть если множество { abcdef, fedcba, abggg }, а мы ищем строку abckl, то нужная строка является первой.

Заранее спасибо.

Класс map (ste, multimap и multiset) реализованы на базе красно-черного дерева. Т.е. отдельный класс дерева в stl есть, хотя и не документирован. Кто мешает использовать его? Не нравится интерфейс - напиши адаптер.

Что касается твоей задачи, то тебе сначала нужно разработать метрику: что значит "похоже" и каково "расстояние" между словами. После этого по барабану, какую реализацию дерева ты будешь использовать. Хоть вообще линейный поиск в списке. И std::min_element.