हम क्यों विशेष रूप से बाइनरी पेड़ का अध्ययन करते हैं? एक सामान्य एम-रास्ता खोज पेड़ में डेटा संरचना संरचना पाठ्यपुस्तकों में बाइनरी पेड़ के रूप में महत्व के रूप में नहीं दिया जाता है।बाइनरी पेड़ क्यों महत्वपूर्ण हैं?
क्या बाइनरी पेड़ का उपयोग एम-वे पेड़ से अधिक है?
बाइनरी पेड़ मल्टी-वे पेड़ का सबसे सरल रूप है इसलिए उन्हें उस अर्थ में अध्ययन करना आसान होता है।
बहु रास्ता पेड़ नोड्स N कुंजी और N+1 संकेत से मिलकर बनता है, की तर्ज पर है:
|
+-----+-----+-----+-----+
| k00 | k01 | k02 | k03 |
+-----+-----+-----+-----+
/ | | | \
p00 p01 p02 p03 p04
पता लगाने के लिए सूचक एक खोज में पालन करने के लिए, आप कुंजी आप देख रहे हैं की तुलना नोड में चाबियों के खिलाफ। ऊपर दिया गया उदाहरण एक ऑर्डर -2 मल्टी-वे पेड़ है (मैं n को 2n कुंजी और 2n+1 पॉइंटर्स के रूप में परिभाषित कर रहा हूं)।
जब आप "पतित" इस संरचना में सबसे छोटी नोड संभव है करने के लिए, आप एक कुंजी और दो संकेत दिए गए, अपने शास्त्रीय द्विआधारी पेड़ के साथ अंत:
|
+-----+
| k00 |
+-----+
/ \
p00 p01
जब मैं विश्वविद्यालय के लिए गया था (और मैं हूँ स्वतंत्र रूप से स्वीकार करें कि यह थोड़ी देर पहले था), हमने बाइनरी पेड़ पहले का अध्ययन किया, बस इसलिए कि एल्गोरिदम सुरुचिपूर्ण थे। खोज एक साधारण तुलना नोड था और दो उप-पेड़ों में से एक का चयन करें। सम्मिलन और हटाना भी अपेक्षाकृत आसान था।
फिर हम संतुलित द्विआधारी पेड़, जहां खोज बिल्कुल वैसा ही था, लेकिन प्रविष्टि और विलोपन जहां आवश्यक इसे रखने के लिए एक छोटे से अधिक जटिल थे, उप पेड़ जड़ के माध्यम से उप पेड़ों की 'घूर्णन' को शामिल करने के लिए पर चला गया संतुलित।
इसके बाद गैर-संतुलित बहु-मार्ग पेड़ों के बाद नोड के भीतर खोज करने की अवधारणा प्राप्त करने के बाद एक सही नोड पाया गया, अंत में, संतुलित बहु-मार्ग पेड़ जो मूल रूप से बाइनरी पेड़ के समान थे लेकिन एक अनुक्रमिक खोज की उसी जटिल जटिलता के साथ-साथ नोड के भीतर सम्मिलन या विलोपन और नोड्स के संयोजन और थूकना।
उन सभी चरणों में आपने एल्गोरिदम में थोड़ी अधिक जटिलता को जोड़ा है। मुझे उस प्रगति के साथ बहुत से लोगों को परेशानी नहीं है, इसलिए शायद आपके द्वारा उल्लेख की जाने वाली सभी पाठ्यपुस्तकें स्टार्टर स्तर पर हैं।
मैंने कभी भी एक बहुत ही विशिष्ट स्थिति को छोड़कर बाइनरी पेड़ों की तुलना में बहु-पक्ष पेड़ अधिक उपयोगी नहीं पाया है। यही वह समय है जब आप पेड़ के नोड्स को धीमे माध्यम से डिस्क जैसे पढ़ रहे हैं और आपने सेक्टर/क्लस्टर/ब्लॉक आकार के लिए अनुकूलित किया है।
हमने ओएस/2 के तहत एक बहु-मार्ग वृक्ष कार्यान्वयन विकसित किया (यहां मेरी उम्र दिखा रहा है) जो चिल्लाती है कि नोड्स अंतर्निहित डिस्क ब्लॉक के आकार में समान थे। भले ही इससे कुछ बर्बाद जगह हो सकती है, गति सुधार इसके लायक थे।
इन-मेमोरी सामान के लिए, बाइनरी पेड़ों में बहु-तरीकों के सभी फायदे हैं जिनमें कोई भी अतिरिक्त जटिलता नहीं है (उप-पेड़ चयन के साथ नोड की अनुक्रमिक खोज को जोड़ना)।
बाइनरी पेड़ उबालते हैं "क्या हमें बाएं या दाएं स्थानांतरित करना चाहिए?", बहु-तरीके हैं "इस नोड में कुंजी कहां है ताकि हम उप-पेड़ चुन सकें?"।
बाइनरी पेड़ एक साधारण अवधारणा है, उन्हें समझना आसान है, कार्यान्वित करने में आसान है, और अच्छी तरह से और तेज़ काम करते हैं - मुझे लगता है कि यह शिक्षण और/या उनका उपयोग करने के लिए पर्याप्त है।
उदाहरण के लिए, बाइनरी पेड़ का उपयोग हीप सॉर्टिंग (बाइनरी हीप) के लिए किया जाता है। यह बहुत तेज़ सॉर्टिंग डेटा के लिए रास्ता है ताकि सबसे बड़ी (या सबसे कम) वस्तु हमेशा सामने हो। इसका उपयोग एआई (ए * एल्गोरिदम) में उदाहरण के लिए किया जाता है।
'एन-आरी' पेड़ पर बाइनरी पेड़ का एक लाभ यह है कि उन्हें ट्रैवल करने से अक्सर binary space partitioning में एक साधारण हां/कोई निर्णय समस्या नहीं होती है।
मैं यहां बहुत ज्यादा तकनीकी नहीं होने वाला हूं .. क्योंकि सवाल यह है कि बाइनरी ट्री डेटा संरचना में इतना महत्व क्यों देती है। बाइनरी ट्री, का मतलब है कि पेड़ टी/एफ, हां/नहीं आदि पर आधारित है। ड्यूओ का संयोजन कहना है। व्यावहारिक रूप से हम उस स्थिति का सामना करते हैं जहां हमें हां या नहीं तय करना होगा .. सही या गलत। बाइनरी पेड़ ऐसी स्थिति का प्रतिनिधित्व करता है। जिन सॉफ़्टवेयर पर हम काम करते हैं, वे ऐसे समाधान हैं जो आंतरिक जीवन परिदृश्यों को हल करने के लिए आंतरिक रूप से उपयोग किए जाने वाले डेटा-संरचनाओं का उपयोग करेंगे .. यही कारण है कि बाइनरी पेड़ चित्र में आ रहा है और आमतौर पर भी इसका उपयोग किया जाता है और यहां तक कि महत्वपूर्ण भी है। बाकी पेड़ सामान्य परिस्थितियों के साथ मिलान करने के लिए और परिशोधन या अतिरिक्त जटिलताओं हैं। बाइनरी पेड़ शुरू करने के लिए हमेशा महत्वपूर्ण है।
बहुत अजीब जवाब ... – Paul
वास्तव में, लेकिन मुझे लगता है कि यह इस मामले में एक भाषा बाधा है। – danieltalsky
क्योंकि पेड़ डेटा संरचनाओं का उपयोग अक्सर ऑर्डर किए गए तत्वों को व्यवस्थित करने के लिए किया जाता है, उदाहरण: ए> बी> सी। यदि पेड़ों में डाले गए आपके आइटम का आदेश दिया जाता है, तो आपको प्रत्येक नोड पर दो शाखाएं बाएं उप-पेड़ में बड़े तत्वों को विभाजित करने के लिए आवश्यक होती हैं, और तत्व जो उप-पेड़ में छोटे होते हैं।
यही कारण है कि बाइनरी पेड़ इतने अधिक प्रचलित हैं कि एम-आरी पेड़। एम-आरी निर्णय बनाम हां/कोई निर्णय लेने में आसानी से इसका कोई लेना-देना नहीं है!
एक बेहतर प्रतिक्रिया ... पाउल .. यू ने एक उदाहरण दिया है। ए> बी> सी .. लेकिन यदि आप इसके बाहर एक पेड़ निकालने का प्रयास करेंगे .. आप इस चरण को चरणबद्ध तरीके से कैसे करेंगे। निम्नलिखित आल्गो है: ए पेश किया गया। जैसा कि है बी पेश किया गया। बी <ए .. ए के बाईं ओर जाएं (सही/गलत निर्णय) सी पेश किया गया। सी <बी .. बी के बाईं ओर जाएं (सही/गलत निर्णय) उस आधार पर मैंने हां/नहीं .. और सच झूठ का संयोजन कहा .. केवल बाइनरी पेड़ ही आपके लिए यह कर सकता है। बीएसटी हालांकि अधिक अर्थपूर्ण है। वैसे भी, आपकी टिप्पणियों के लिए धन्यवाद – Sumeet
यू आदेश को संरक्षित करने के लिए बी + पेड़ का उपयोग कर सकते हैं, इसलिए हम कह सकते हैं .. ऑर्डर के लिए बाइनरी का भी उपयोग नहीं किया जाता है :) http://en.wikipedia.org/wiki/B%2B_tree – Sumeet
उपर्युक्त सभी उत्तरों को जोड़कर, किसी भी धर्मार्थ का पेड़ एक बाइनरी पेड़ द्वारा प्रदर्शित किया जा सकता है (जहां बाएं लिंक नोड के पहले बच्चे को जाता है, और सही लिंक अगले "भाई" पर जाता है)।
ए बी-ट्री एक प्रकार का एम-रास्ता पेड़ है। मुझे लगता है कि आप बाइनरी पेड़ का मतलब है, है ना? – Thomas
@ थॉमस: आउच, मैं हमेशा "बी-पेड़" "बाइनरी-पेड़" के लिए शॉर्टकट था; एक बार फिर, मैंने कुछ पर सवाल का जवाब सीखा ;; धन्यवाद ! –