Поиск данных, хранящихся в дереве

Question

У меня есть эти данные, которые являются иерархическими, и поэтому я храню их в дереве.Я хочу предоставить ему функцию поиска.Должен ли я создать двоичное дерево для этого?Я не хочу иметь тысячи узлов дважды.Разве нет такого рода дерева, которое позволяет мне хранить данные в указанном порядке, а также предоставлять мне двоичное дерево, например, эффективную настройку поиска, с небольшими накладными расходами?

Любые другие предложения по структуре данных также будутпризнателен.

Спасибо.

РЕДАКТИРОВАТЬ:

Некоторые детали: Дерево очень простое "сделанное вручную" дерево, которое можно считать очень простым.Дело в том, что есть тысячи имен и другого текста, которые будут вводиться как данные, которые я хочу искать, но я не хочу проходить узлы традиционным способом и мне нужен быстрый поиск, такой как бинарный поиск.

Также, что важно, пользователь должен видеть структуру, в которую он вошел, а НЕ отсортированную.Так что я не могу сохранить его отсортированным для поддержки поиска.Вот почему я сказал, что не хочу иметь тысячи узлов дважды.

Answer 1

Если вы не хотите изменять иерархию деревьев, используйте карту для хранения указателей на вершины: std::map<SearchKeyType,Vertex*> M.

Каждый раз, когда вы добавляете вершину к своему дереву, вы также должны добавлять ее на свою карту. Это очень просто: M[key]=&vertex. Чтобы найти элемент, используйте M.find(key); или M[key];, если вы уверены, что ключ существует.

Если в вашем дереве есть дубликаты ключей, вам следует использовать multimap .

Редактировать: Если размер вашего ключа слишком велик, вы можете использовать указатель на ключ вместо ключа:

inline bool comparisonFunction(SearchKeyType * arg1,SearchKeyType * arg2);

std::map<SearchKeyType *, Vertex *, comparisonFunction> M;

inline bool comparisonFunction(SearchKeyType * arg1,SearchKeyType * arg2)
{
         return (*arg1)<(*arg2);
}

для поиска элемента со значением V необходимо написать следующее:

Vertex * v = M[&V]; // assuming that element V exists in M