बाइनरी ट्री ऊंचाई

Question

मुझे बाइनरी पेड़ की न्यूनतम ऊंचाई और बाइनरी पेड़ की अधिकतम ऊंचाई की गणना करने के लिए एक सामान्य सूत्र की आवश्यकता है। (द्विआधारी खोज पेड़ नहीं)

Answer 1

इस बारे में सोचें कि पेड़ की संरचना कैसे बदल सकती है।

उदाहरण के लिए, यदि पेड़ पूरी तरह असंतुलित है तो यह सबसे बुरा मामला है - प्रत्येक नोड में बिल्कुल एक बच्चा होगा। सबसे अच्छे मामले में, पेड़ संतुलित हो जाता है, और प्रत्येक नोड में दो बच्चे होते हैं।

चूंकि यह होमवर्क की तरह लगता है, मैं इसे वहां छोड़ दूंगा।

Answer 2

अधिकतम ऊंचाई n और मिनट ऊंचाई (आईई एक आदर्श द्विआधारी पेड़) है (लॉग आधार 2 (n + 1)) - 1

Answer 3

आप एन तत्वों, एक द्विआधारी की न्यूनतम ऊंचाई है, तो पेड़ लॉग 2 (एन) +1 होगा।

एक पूर्ण बाइनरी पेड़ के लिए, अधिकतम ऊंचाई एन/2 होगी।

एक गैर पूर्ण द्विआधारी पेड़ के लिए, अधिकतम ऊंचाई एन हो जाएगा

Answer 4

पहले वहाँ कैसे कंप्यूटर विज्ञान, एक पेड़ की ऊंचाई की गणना करता है बनाम रास्ता ऊंचाई असतत में निर्धारित किया जाता है के रूप में कुछ अंतर हो सकता है गणित (ग्राफ सिद्धांत), यह किसी भी एक नोड (या ऊर्ध्वाधर) पर डेटा के अस्तित्व के कारण हो सकता है, जबकि गणित में, यह एक शुद्ध सिद्धांत दृष्टिकोण है।

तो शायद यह सबसे अच्छा है कि आप जिसकी आपको आवश्यकता है उसे स्पष्ट करें।

असतत गणित में, पेड़ों को एम-आरी पेड़ों के रूप में वर्गीकृत किया जाता है, इसलिए बिन-आरी पेड़ 2-आरी पेड़ है। किसी भी दी गई ऊंचाई पर, अधिकतर 2^एच = एल (पत्ते) पर हो सकता है। यह ध्यान देने योग्य है, क्योंकि यह पुष्टि करता है कि रूट ऊंचाई शून्य पर है, इसलिए 2^0 = 1 पत्ता ... 1 वर्टिस ... रूट।

तो दिया n कोने, एक पेड़ की ऊंचाई सूत्र द्वारा दिया जाता है एन = 2^(ज + 1) - 1

आप ज के लिए देख रहे हैं के बाद से, आप दोनों की log2 ले जाना है सूत्र n = 2 की तरफ^(ज + 1) - 1

एक पूर्ण द्विआधारी पेड़ के लिए, अधिकतम ऊंचाई log2 (n + 1) = log2 (2^(ज + 1)) यह है बराबर बराबर (लॉग 2 (एन + 1) - 1) = एच

गैर-पूर्ण बाइनरी पेड़ के लिए, अधिकतम ऊंचाई = (एन -1) इसलिए यदि आपके पास एन शिखर हैं, तो रूट को ऊपर दिए गए पिछले सूत्र (2^एच = एल)

उपरोक्त नियमों से निकालने के लिए न्यूनतम ऊंचाई के लिए अधिकतम ऊंचाई प्राप्त करने के लिए घटाया जाना चाहिए।

Answer 5

न्यूनतम ऊंचाई एच = छत (लॉग (एन + 1)/लॉग (2) -1) किसी भी बाइनरी पेड़ के लिए है।

Answer 6

एक रूट तो 2 (0,1,2) तक पत्ते के किसी भी संख्या हो सकती है, तो:

• अधिकतम ऊंचाई n-1 है। यह वह मामला है जब आपके पेड़ में केवल एक पत्ता होता है। कोई नोड में एक से अधिक शाखाएं हैं।
• न्यूनतम ऊंचाई [log2 (n)] जहां [x] x का पूर्णांक हिस्सा है।

न्यूनतम ऊंचाई प्राप्त करने के लिए प्रत्येक रूट में जितनी संभव हो उतनी शाखाएं होनी चाहिए। इस मामले में आप देखेंगे कि n = 1, ऊंचाई = 0; एन = 2 से एन = 3, ऊंचाई = 1 के लिए; एन = 4 से एन = 7, ऊंचाई = 2 के लिए; के लिए एन = 8 n करने के लिए = 15, ऊंचाई = 3 आदि

आप इस प्रकार है कि नोटिस कर सकते हैं, हर n के लिए, वहां मौजूद एपी ऐसी है कि:

2^पी < = n < 2^(पी + 1) और पी = ऊंचाई, तो ऊंचाई = [लॉग 2 (एन)]

Answer 7

एन - नोड्स की संख्या।
एच - बाइनरी पेड़ की ऊंचाई।

पूरा बाइनरी ट्री:

2^H <= N <= (2^(H+1) - 1) 

इस प्रकार, इस असमानता को सुलझाने;:
फिर, एच ऊंचाई के साथ एन के बीच झूठ होगा हम पाते हैं:

H <= lg(N) and H >= (lg(N+1) - 1) 

इसलिए हम अंत में मिलता है:

H = floor(lg(N)) = ceil((lg(N+1) - 1)) //as H is integer 

(एलजी: log base 2)

बाइनरी ट्री (जरूरी नहीं पूरा):

Max height = N; 

Min Height = floor(lg(N)) = ceil((lg(N+1) - 1)) 

बाइनरी पेड़ पूरा होने पर हमें न्यूनतम ऊंचाई मिलती है।

Answer 8

n-nodes के साथ संभव अधिकतम ऊंचाई floor(log(n)) = ceil (log(n+1))-1 है।

n-nodes के साथ संभव न्यूनतम ऊंचाई n-1 है।