एक पूर्ण द्विआधारी पेड़ की परिभाषा "ए हैपूर्ण बाइनरी पेड़ एक बाइनरी पेड़ है जिसमें प्रत्येक स्तर, संभवतः आखिरी को छोड़कर, पूरी तरह से भर जाता है, और सभी नोड्स जितना संभव हो उतना दूर छोड़ दिया जाता है। "मैं जानना चाहता था कि अंतिम स्तर को आंशिक रूप से भरने की अनुमति क्यों है। क्या यह मदद करता है कुछ स्थितियों / मामलों में?
मैंने कई स्थानों पर इस प्रश्न का उत्तर खोजने की कोशिश की, हालांकि मैं एक संतोषजनक उत्तर नहीं ढूंढ पाया। क्या कोई इसका जवाब देकर मेरी मदद कर सकता है। बहुत धन्यवाद ...
उत्तर:
जवाब के लिए 2 № 1दूसरे प्रश्न की तुलना में इस प्रश्न पर एक अलग कदम: यदि सभी स्तरों को पूरी तरह से भरने की आवश्यकता होगी तो आपको केवल पेड़ ही मिल सकते हैं (2^n)-1 कुछ के लिए तत्व n। अर्थात। 1, 3, 7, 15, ... तत्व। अंतिम स्तर को आंशिक रूप से भरने की अनुमति देकर आप किसी भी तत्व के साथ बाइनरी पेड़ प्राप्त कर सकते हैं।
उत्तर № 2 के लिए 1
यह सिर्फ एक पूर्ण बाइनरी पेड़ की परिभाषा है। यह जरूरी नहीं है कि न ही कुछ भी बाधा डालें, यह वही तरीका है।
यदि आप विषय में रूचि रखते हैं, तो देखोसंतुलित बाइनरी पेड़। वहां, यह सुनिश्चित करने के लिए कि पेड़ संतुलित है और आपके पास 10 नोड गहरे बाएं तरफ और 1 नोड गहरे दाएं तरफ नहीं है, केवल यह सुनिश्चित करने के लिए कि निम्नतम स्तर पूरी तरह से भरे नहीं हैं।
एक पेड़ के सभी स्तर पूरी तरह से होने के बादभरी सहायता आपको तेजी से खोज के समय की गारंटी देती है। यदि सभी स्तर पूरी तरह से भरे हुए हैं, तो आप जानते हैं कि पेड़ की गहराई सभी संभावित पथों के बराबर है, इसलिए आपको खोज गति पर एक अच्छा ऊपरी बाउंड सुनिश्चित करना है। ऐसे मामलों में आप सभी संभावित पत्ती नोड पथों की गहराई की गणना कर सकते हैं D = floor(lg(N)), जहां एन नोड्स की संख्या है।
अब, कल्पना करें कि क्या आपने जरूरी स्तरों को पूरा नहीं किया है। आपके पास इस राक्षस की तरह कुछ हो सकता है, जहां कुछ तत्व दूसरों की तुलना में कहीं अधिक तेजी से लाए जाएंगे।
