मैं बाइनरी खोज पेड़ पर इस ऑपरेशन को कैसे साबित कर सकता हूं?

Question

मैं चाहता हूं कि आप मुझे इस अभ्यास को कॉर्मन की किताब से साबित करने के लिए एक संकेत दें: "साबित करें कि कोई भी नोड जो हम ऊंचाई-एच बाइनरी खोज पेड़ में शुरू करते हैं, के ट्री-सफलताकर्ता को लगातार कॉल ओ (के + एच) समय ले लो। "

Answer 1

• Let शुरू करने नोड हो x और z वृक्ष-उत्तराधिकारी को k लगातार कॉल के बाद समाप्त होने नोड हो।
• px और z समेत सरल पथ बनें।
• yx और z के सामान्य पूर्वजों को p विज़िट करने दें।
• p की लंबाई 2h पर है, जो O(h) है।
• output उन तत्वों को बनें जो उनके मान x.key और z.key समेत शामिल हैं।
• output का आकार O(k) है।
• वृक्ष-उत्तराधिकारी को k लगातार कॉल, नोड्स p में हैं के निष्पादन में दौरा कर रहे हैं, और नोड्स x, y और z, अलावा अगर p में एक नोड के एक उप पेड़ तो सभी का दौरा किया है इसके तत्व output में हैं।
• तो चलने का समय O(h+k) है।

Answer 2

संकेत: एक छोटा सा उदाहरण तैयार करें, परिणाम देखें, कारण को निकालने का प्रयास करें।

आरंभ करने के लिए, यहां कुछ चीजों पर विचार करना है।

एक निश्चित नोड से शुरू करें, ट्री-सक्सेसर को सफलतापूर्वक कॉल आंशिक वृक्ष चलने का प्रयास करता है। कितने (कम से कम और अधिकतर) नोड्स इस यात्रा पर जाते हैं? (संकेत: कुंजी (एक्स) के बारे में सोचें)। ध्यान रखें कि किनारे पर दो बार दौरा किया जाता है (क्यों?)।

अंतिम संकेत: परिणाम O(2h+k) है।