ट्रे और पेड़ के बीच अंतर?

Question

मुझे दूरस्थ रूप से याद है कि प्रति नोड पूरे डेटा को स्टोर नहीं करता है, लेकिन केवल पैरेंट नोड के लिए प्रत्यय।

जहां पेड़ पूरे डेटा को स्टोर करते हैं, लेकिन केवल स्वयं आधारित उपसर्ग आधारित होते हैं।

तो छोटे होने की कोशिश करता है, उदाहरण के लिए कंप्रेसर शब्दकोश बहुत अच्छा हो सकता है।

तो क्या वास्तव में केवल अंतर है?

वास्तविक अनुप्रयोगों से मुझे याद है कि सीमा प्रश्नों में प्रयास तेजी से हैं? सीमा प्रश्नों को गति देने के लिए यहां तक ​​कि विशेष solr/lucene trie फ़ील्ड भी हैं। लेकिन ऐसा कैसे है?

वास्तविक अंतर क्या है और प्रयासों और पेड़ों के फायदे/नुकसान क्या हैं?

Answer 1

एक पेड़ रिकर्सिव नोड्स की एक सामान्य संरचना है। पेड़ के कई प्रकार हैं। लोकप्रिय लोग binary tree और balanced tree हैं। एक Trie एक प्रकार का पेड़ है, जिसे कई नामों से जाना जाता है जिसमें उपसर्ग पेड़, डिजिटल सर्च पेड़, और पुनर्प्राप्ति पेड़ (इसलिए नाम 'ट्राई') शामिल है।

प्रत्येक प्रकार के पेड़ का एक अलग उद्देश्य, संरचना और व्यवहार होता है। उदाहरण के लिए, एक बाइनरी पेड़ तुलनीय वस्तुओं (जैसे संख्याओं) का संग्रह संग्रहीत करता है। इसलिए इसका उपयोग संख्याओं के एक सेट को स्टोर करने के लिए किया जा सकता है, या अन्य डेटा को इंडेक्स करने के लिए किया जा सकता है जिसे संख्याओं द्वारा प्रदर्शित किया जा सकता है (उदाहरण के लिए ऑब्जेक्ट जिन्हें धोया जा सकता है)। इसकी संरचना को हल किया गया है ताकि इसे एक आइटम खोजने के लिए जल्दी से खोजा जा सके। एक संतुलित पेड़ जैसे अन्य वृक्ष संरचनाएं सिद्धांत में समान हैं।

ए trie इसकी संरचना में अनुक्रम का प्रतिनिधित्व करता है। यह बहुत अलग है कि यह व्यक्तिगत एकल मानों के बजाय मूल्यों के अनुक्रमों को संग्रहीत करता है। रिकर्सन के प्रत्येक स्तर का कहना है कि 'इनपुट सूची के आइटम I का मूल्य क्या है'। यह एक बाइनरी पेड़ से अलग है जो प्रत्येक नोड को एकल खोज मूल्य की तुलना करता है।

Answer 2

ए बाइनरी पेड़ या बीएसटी आमतौर पर संख्यात्मक मानों को संग्रहीत करने के लिए उपयोग किया जाता है। बीएसटी में समय जटिलता ओ (लॉग (एन)) सम्मिलन, हटाने और खोज के लिए है। एक बाइनरी पेड़ में प्रत्येक नोड में अधिकतम 2 बच्चे नोड होते हैं।

ट्री: त्रिभुज के प्रत्येक नोड में कई शाखाएं होती हैं। प्रत्येक शाखा कुंजी के संभावित चरित्र का प्रतिनिधित्व करती है। हमें पत्ती नोड के रूप में प्रत्येक कुंजी के अंतिम नोड को चिह्नित करने की आवश्यकता है। नोड को पत्ती नोड के रूप में अलग करने के लिए एक त्रिभुज नोड फ़ील्ड मान का उपयोग किया जाएगा (मूल्य क्षेत्र के अन्य उपयोग हैं)

प्रयासों के बारे में जानने के लिए इस टॉपकोडर ट्यूटोरियल को देखें। https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/