द्विआधारी खोज पेड़

Question

यह BST के बारे में विकिपीडिया पर पाया कुछ कोड है

 10 
    5  12 
    3 8 9 14 
    4 11 

मैं 11 के लिए खोज कर रहा हूँ, और मैं वहाँ एल्गोरिथ्म का पालन करें , मैं 10 के साथ शुरू करता हूं, मैं 12 तक जाता हूं, और फिर 9 तक जाता है। और मैं बिना पेड़ के अंत तक पहुंच जाता हूं 11. लेकिन 11 मेरे पेड़ में मौजूद है, यह दूसरी तरफ है।

क्या आप कृपया बता सकते हैं कि इस पेड़ पर काम करने के लिए इस एल्गोरिदम के लिए बाइनरी ट्री में प्रतिबंध क्या हैं?

धन्यवाद।

Answer 1

ऐसा इसलिए है क्योंकि आपका पेड़ एक बाइनरी खोज पेड़ नहीं है: इसे सही तरीके से आदेश नहीं दिया गया है। वास्तव में एल्गोरिदम में वर्णित बीएसटी का निर्माण होता है। उदाहरण के लिए अपने पेड़ में: नोड '9' सही स्थिति पर नहीं है क्योंकि 9 < 10 के रूप में यह आपके रूट नोड '10' की बाएं शाखा के नीचे होना चाहिए। '14' और '11' के लिए वही है जो सही शाखा पर होना चाहिए।

उदाहरण के लिए एक BST इस तरह sth सकता है:

10 
    5 11 
3 8 12 
      14 

Answer 2

बाइनरी ट्री और बाइनरी सर्च ट्री के बीच भ्रमित न हों। बाइनरी सर्च ट्री (जिसे बीएसटी कहा जाता है) एक विशेष प्रकार का बाइनरी पेड़ है जहां बाईं ओर के सभी नोड्स पैरेंट नोड से कम या बराबर होते हैं और सभी नोड्स पैरेंट नोड से अधिक होते हैं।

जबकि आपने जो उदाहरण दिया है वह सिर्फ एक बाइनरी ट्री है और बाइनरी सर्च ट्री नहीं है। आप देख सकते हैं कि मूल्य 11 और 14 माता-पिता नोड 10 पर छोड़े गए हैं जो बीएसटी संपत्ति का उल्लंघन करते हैं। बाइनरी खोज पेड़ के लिए here देखें।

Answer 3

आपने गलत स्थान पर नोड्स 14 और 11 रखे हैं। the Wikipedia article on BSTs से:

• एक नोड के बाईं सबट्री नोड के प्रमुख की तुलना में कम कुंजी के साथ केवल नोड्स में शामिल है।
• नोड के दाएं उपट्री में केवल नोड की कुंजी से अधिक कुंजी वाले नोड्स होते हैं।
• बाएं और दाएं उपट्री दोनों बाइनरी खोज पेड़ भी होना चाहिए।

आप देख सकते हैं, दोनों 14 और 11 से अधिक 8.

Answer 4

पेड़ तुम नहीं एक BST में प्रस्तुत कर रहे हैं। 11 और 14 को 10 के बाईं ओर कभी नहीं डाला गया था, और यही कारण है कि एल्गोरिदम वहां नहीं खोजता है। 9 जगह से बाहर भी है।

विकिपीडिया के अनुसार प्रविष्टि:

निवेशन एक खोज शुरू हो जाएगा के रूप में शुरू होता है; यदि रूट मूल्य के बराबर नहीं है, तो हम बाएं या दाएं उपट्री को पहले की तरह खोजते हैं। आखिरकार, हम नोड के मूल्य के आधार पर बाहरी नोड तक पहुंच जाएंगे और मूल्य को दाएं या बाएं बच्चे के रूप में जोड़ देंगे। दूसरे शब्दों में, हम रूट की जांच करते हैं और बाएं उपट्री में नए नोड को दोबारा सम्मिलित करते हैं यदि नया मान रूट से कम है, या सही सबट्री यदि नया मान रूट से बड़ा या बराबर है।

आप बता सकते हैं कि एक बाइनरी ट्री एक BST है अगर यह इन गुणों (भी विकिपीडिया से) है: कम नोड की तुलना में

1. एक नोड के बाईं सबट्री केवल कुंजी के साथ नोड शामिल कुंजी।
2. नोड के दाएं उपट्री में नोड्स की कुंजी से अधिक कुंजी वाले नोड्स होते हैं।
3. बाएं और दाएं उपट्री दोनों बाइनरी खोज पेड़ भी होना चाहिए।

Answer 5

अपने पेड़ एक द्विआधारी खोज वृक्ष