[Powered by Google Translate] कैसे आप एक कंप्यूटर में अपने परिवार के सभी सदस्यों का प्रतिनिधित्व करेंगे?
हम बस एक सूची का उपयोग कर सकते हैं,
लेकिन वहाँ एक स्पष्ट पदानुक्रम यहाँ है.
>> हम कहते हैं कि हम अपने महान दादी, ऐलिस के साथ शुरुआत कर रहे हैं.
वह 2 बेटों, बॉब
और अपने दादा, चार्ली.
चार्ली 3 बच्चों की है,
अपने चाचा, डेव, अपने चाची, ईव, और अपने पिता, फ्रेड.
तुम फ्रेड केवल बच्चे हैं.
>> इस तरह से अपने परिवार के सदस्यों क्यों आयोजन होगा
सरल सूची प्रतिनिधित्व की तुलना में बेहतर हो सकता है?
एक कारण यह है कि इस सौपानिक संरचना,
'पेड़' एक साधारण सूची की तुलना में अधिक जानकारी है एक बुलाया.
हम सब के बीच पारिवारिक संबंधों पता
बस पेड़ का परीक्षण करके.
इसके अलावा, यह गति कर सकते हैं
काफी समय देखो, अगर पेड़ डेटा सॉर्ट किया जाता है.
>> हम यहाँ कि लाभ नहीं ले सकते हैं, लेकिन हम जल्द ही इस का एक उदाहरण देखेंगे.
प्रत्येक व्यक्ति को पेड़ पर एक नोड द्वारा प्रतिनिधित्व किया है.
नोड्स बच्चे नोड्स हो सकता है
के रूप में अच्छी तरह से एक माता पिता के नोड के रूप में.
इन तकनीकी शब्दों हैं,
यहां तक ​​कि जब परिवारों के अलावा बातों के लिए पेड़ों का इस्तेमाल करते हैं.
ऐलिस नोड 2 बच्चों और माता पिता नहीं है,
जबकि चार्ली नोड 3 बच्चों और 1 माता पिता है.
>> एक पत्ती नोड एक है कि किसी भी बच्चे नहीं है
पेड़ के बाहर किनारे पर.
पेड़ के सर्वोच्च नोड, रूट नोड,
कोई माता पिता है.
>> एक द्विआधारी पेड़ पेड़ की एक विशिष्ट प्रकार है,
जिसमें प्रत्येक नोड में सबसे अधिक है,, 2 बच्चों.
यहाँ सी. में एक द्विआधारी पेड़ के एक नोड struct है
हर नोड कुछ इसके साथ जुड़े डेटा
और अन्य नोड्स के लिए 2 संकेत.
>> हमारे परिवार के पेड़ में,
डेटा जुड़े प्रत्येक व्यक्ति का नाम था.
यहाँ यह एक int है, हालांकि यह कुछ भी हो सकता है.
के रूप में यह पता चला है,
एक द्विआधारी पेड़ एक परिवार के लिए एक अच्छा प्रतिनिधित्व नहीं होगा,
के बाद से लोगों को अक्सर 2 से अधिक बच्चे हैं.
>> एक द्विआधारी खोज वृक्ष
द्विआधारी पेड़ के एक विशेष प्रकार का आदेश दिया है
कि हमें मूल्यों पर देखने के लिए जल्दी की अनुमति देता है.
आपने गौर किया हो सकता है
कि एक पेड़ की जड़ के नीचे हर नोड
एक पेड़ की जड़ है, एक 'subtree' कहा जाता है.
यहाँ, पेड़ की जड़ 6 है,
और उसके बच्चे, 2, एक सबट्री की जड़ है.
>> एक द्विआधारी खोज वृक्ष में
एक नोड के सभी मूल्यों को सही subtree है
नोड के मूल्य से अधिक हैं. यहाँ: 6.
खैर, एक नोड छोड़ दिया subtree में मानों
नोड मूल्य की तुलना में कम कर रहे हैं.
अगर हम डुप्लिकेट मानों को संभालने की जरूरत है,
हम या तो उन लोगों में से एक ढीला असमानता को बदल सकते हैं,
जिसका अर्थ है समान मूल्यों को या तो छोड़ दिया है या सही पर गिर सकता है,
के रूप में लंबे समय के रूप में हम भर में इसके बारे में संगत कर रहे हैं.
यह पेड़ एक द्विआधारी खोज वृक्ष
क्योंकि यह इन नियमों का पालन.
>> यह है कि यह देखना होगा अगर हम सी structs में सभी नोड्स दिया.
सूचना है कि अगर एक बच्चा गायब है,
सूचक अशक्त है.
हम देखने के लिए अगर पेड़ में 7 जांच कैसे करूं?
हम जड़ में शुरू करते हैं.
सात 6 से अधिक है, इसलिए अगर यह पेड़ में है, यह सही करने के लिए होना चाहिए.
तो फिर, यह 8 की तुलना में कम है, तो इसे छोड़ दिया जाना चाहिए.
यहाँ, हम 7 पाया है.
अब, हम 5 के लिए जांच करेंगे.
पांच 6 से कम है, तो यह बाईं ओर होना चाहिए.
पांच 2 से अधिक है,
तो यह सही होना चाहिए,
और यह भी 4 से अधिक है, तो यह सही फिर से होना चाहिए.
हालांकि, वहाँ कोई बच्चा यहाँ है.
सूचक अशक्त है.
इसका मतलब यह है कि 5 हमारे पेड़ में नहीं है.
>> हम निम्नलिखित कोड के साथ बाइनरी पेड़ खोज कर सकते हैं:
प्रत्येक नोड में, हम देखने के लिए अगर हम मिल गया है की जाँच करें
मूल्य के लिए हम देख रहे हैं.
अगर हम यह नहीं मिल रहा है, हम तय अगर यह होना चाहिए
पर छोड़ दिया है या सही है कि subtree की जाँच करें.
इस लूप के नीचे पेड़ जारी रहेगा
जब तक वहाँ या तो छोड़ दिया है या सही पर कोई बच्चा नोड है.
>> याद है कि 5 पेड़ में नहीं था.
हम यह कैसे डालूँ?
प्रक्रिया को खोज करने के लिए समान दिखता है.
हम नीचे 6 से शुरू पेड़ पुनरावृति
2 के लिए छोड़ दिया,
4 करने के लिए सही है,
और फिर से ठीक है, लेकिन इस तरफ 4 कोई बच्चे नहीं है.
यह 5 के लिए नई स्थिति में हो जाएगा,
और यह कोई बच्चों के साथ शुरू कर देंगे.
>> कितनी तेजी से एक द्विआधारी खोज वृक्ष पर कार्य कर रहे हैं?
याद रखें कि Bigohnotation एक ऊपरी सीमा प्रदान करना चाहता है.
सबसे खराब स्थिति में,
हमारे पेड़ बस एक लिंक सूची हो सकता है
जिसका अर्थ है कि प्रविष्टि, विलोपन, और खोज
पेड़ में नोड्स की संख्या के लिए आनुपातिक समय लग सकता है.
यह O (n) है.
>> उदाहरण के लिए, निम्नलिखित एक वैध द्विआधारी खोज वृक्ष है.
हालांकि, अगर हम 9 खोजने की कोशिश की,
हम हर नोड पार है.
यह कोई एक लिंक सूची की तुलना में बेहतर है.
आदर्श रूप में, हम हर नोड चाहते हो जाएगा
हमारे द्विआधारी खोज वृक्ष के 2 बच्चों के लिए.
इस तरह, प्रविष्टि विलोपन, और खोज
में सबसे खराब, हे (लॉग एन) समय लग जाएगा.
पहले से पेड़ और अधिक संतुलित हो सकता है,
इस तरह.
अब, किसी भी मूल्य देख में सबसे अधिक लेता है, 3 चरणों.
इस पेड़ संतुलित है,
जिसका अर्थ है कि एक न्यूनतम गहराई है
नोड्स की संख्या के सापेक्ष.
>> एक संतुलित द्विआधारी खोज वृक्ष में एक मूल्य के लिए देख रहे हैं
एक हल सरणी पर द्विआधारी खोज के लिए इसी तरह की है.
वास्तव में, यदि हम डालने या आइटम को हटाने की जरूरत नहीं है,
वे बिल्कुल उसी तरह व्यवहार करते हैं.
हालांकि, एक वृक्ष संरचना बेहतर है
से निपटने के सम्मिलन और विलोपन के लिए
>> मेरा नाम Bannus वान डेर Kloot है.
यह CS50 है.