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

Question

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

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

Спасибо.

EDIT:

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

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

Answer 1

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

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

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

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

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

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

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

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