Реализовать телефонный справочник с помощью двух попыток

Question

I have encountered an interview question 
    “Implement a phone directory using Data Structures”     

Я хочу, чтобы решить его с помощью tries.By решения его попыток, я попытался с помощью двух попыток, один для имени, а другой для номера телефона, , но я столкнулся с трудностями.
Предположим, я должен добавить три записи (AB "112" BC "124" CD "225") Затем, если я запрашиваю имя для номера «225», как мне вернуть CD. То есть, как эти две попытки будут связаны.

One approach I was thinking was taking two pointers in both the tries. 
    These pointers will point to the first and last word in the other trie. 
    For example,if the structures are as follows: 

    Struct nametrie        
    {              
    Struct nametrie *child[26]; 
    struct phonetrie*head,*tail; 
    struct phonetrie*root;  

    -----------  
    }              

     Struct phonetrie 
    { 
      struct phonetrie*child[9]; 
      struct nametrie*head,*tail; 
      struct nametrie*root; 
     ----------- 
     } 


    Then for AB “112”, 
    Name trie willstore head(1) and tail (2). 

Но я думаю, что этот подход не будет работать для повторяющихся записей (одно имя и несколько номеров.)

Can someone please explain a good approach.I am not looking for code but good understanding of approach,may be via diagram or algorithm. 

Answer 1

я не знаю, C, так что я не могу комментировать в своем коде.

Идея использования попыток действительна.

вы, кажется, отсутствуют какие данные узлы могут проводить в попытках

узел на деревьях имеет 2 основных компонента

1. данные, которые он имеет, который может быть anytype
2. список Childen (или слева, справа childeren) или в любой комбинации детей

что мы будем делать здесь, мы добавим другое поле к каждому узлу и назовем его значением «theValu е»

Так узел Trie будет выглядеть следующим образом

Class TrieNode{ 
public char theChar; 
public String theValue; 
public List<TrieNode> children; 
} 

Таким образом, для прямого просмотра (имя телефона) вы строите один TRIE и на узле, который соответствует записи в каталоге вы установите theValue в том, что entrie.

вам нужно будет создать 2-го синтаксического дерева, чтобы сделать то же самое для обратного поиска (телефон с именем)

Так, чтобы дать вам пример того, как это будет выглядеть для этих данных будет

(AB « 112” AC „124“ ДС «225”)

//create nodes 
TrieNode root = new TrieNode(); 
TrieNode A = new TrieNode(); 
A.theChar = 'A'; 
TrieNode B = new TrieNode(); 
A.theChar = 'B'; 
TrieNode C = new TrieNode(); 
A.theChar = 'C'; 
TrieNode C2 = new TrieNode(); 
A.theChar = 'C'; 
TrieNode D = new TrieNode(); 
A.theChar = 'D'; 
//link nodes together 
root.children = new ArrayList<>(); 
root.children.add(A); 
A.children = new ArrayList<>(); 
A.children.add(B); 
A.children.add(C); 
B.children = new ArrayList<>(); 
B.children.add(C2); 
//fill the data 
B.theValue = "112"; 
C.theValue = "124"; 
C2.theValue = "225"; 

теперь вы можете легко пройти эту TRIE и когда вы достигнете узел и whant проверить значение просто читать theValue

Надеюсь, что это ясно.