Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Бинарные деревья поиска - АВЛ vs RB

Автор: A1ukard 21.12.2008, 16:31

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

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

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

Автор: Earnest 23.12.2008, 13:36

Цитата(A1ukard @ 21.12.2008, 17:31

)

RB-деревья используются в классе map, но он мне не очень подходит

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

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