मान लीजिए कि हमें तीन बुनियादी संचालन जैसे डालने (), खोज (), स्टार्टविथ () विधियों के साथ त्रिकोणीय संरचना बनाना है। हम मान सकते हैं कि सभी इनपुट लोअरकेस अक्षरों में हैं। उदाहरण के लिए, यदि हम फ़ंक्शन को इस प्रकार कहते हैं, तो हम आउटपुट देखेंगे
- ट्री ट्री =न्यू ट्री ()
- trie.insert(“apple”)
- trie.search(“apple”)//यह सच हो जाएगा
- trie.search("app") // यह झूठी वापसी करेगा
- trie.startsWith(“app”) // यह सच हो जाएगा
- trie.insert(“app”)
- trie.search(“app”)//यह सच हो जाएगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- शुरुआत में चाइल्ड नाम की एक डिक्शनरी बनाएं।
- सम्मिलित करने की विधि इस प्रकार होगी -
- वर्तमान:=बच्चा
- शब्द के प्रत्येक अक्षर l के लिए −
- यदि l वर्तमान में मौजूद नहीं है, तो वर्तमान[l] :=नया शब्दकोश
- वर्तमान:=वर्तमान[l]
- वर्तमान[#] =1
- खोज विधि इस प्रकार होगी -
- वर्तमान:=बच्चा
- शब्द के प्रत्येक अक्षर l के लिए −
- यदि l वर्तमान में मौजूद नहीं है, तो झूठी वापसी करें
- वर्तमान:=वर्तमान[l]
- सही लौटें अगर करंट[#] =1, अन्यथा गलत हो
- StarsWith विधि इस प्रकार होगी -
- वर्तमान:=बच्चा
- शब्द के प्रत्येक अक्षर l के लिए −
- यदि l वर्तमान में मौजूद नहीं है, तो झूठी वापसी करें
- वर्तमान:=वर्तमान[l]
- सही लौटें
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class Trie(object):
def __init__(self):
self.child = {}
def insert(self, word):
current = self.child
for l in word:
if l not in current:
current[l] = {}
current = current[l]
current['#']=1
def search(self, word):
current = self.child
for l in word:
if l not in current:
return False
current = current[l]
return '#' in current
def startsWith(self, prefix):
current = self.child
for l in prefix:
if l not in current:
return False
current = current[l]
return True
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app")) इनपुट
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app")) आउटपुट
True False True True