एक बाइनरी खोज पेड़ की औसत ऊंचाई

Question

1000 यादृच्छिक इनट जोड़ने के दौरान आप बाइनरी खोज पेड़ की औसत ऊंचाई की गणना कैसे करते हैं? औसत ऊंचाई क्या है?

Answer 1

आप एक द्विआधारी पेड़ की ऊंचाई की गणना इस पुनरावर्ती परिभाषा का उपयोग कर सकते हैं:

height(empty) = 0 
height(tree) = 1 + max(height(tree.left), height(tree.right)) 

एक तरीका यह अनुभव बार-बार एक खाली पेड़ बनाने के लिए किया गया है इस तरह के एक पेड़ की औसत ऊंचाई मापने और 1000 यादृच्छिक आइटम जोड़ने के लिए यह। उपरोक्त फ़ंक्शन का उपयोग करके प्रत्येक परीक्षण की ऊंचाई को मापें, और उन्हें औसत करें।

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

Answer 2

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

Answer 3

यह (जैसे एक लाल-काले वृक्ष के रूप में) आप संतुलित वृक्ष संरचना किसी भी प्रकार का उपयोग कर रहे हैं, इस पर निर्भर करता है। चूंकि आप बाइनरी पेड़ में यादृच्छिक संख्याएं डाल रहे हैं, इसलिए यह अपेक्षा करना उचित होगा कि औसत गहराई लगभग लॉग 2 (1000) है - इसलिए मान 10 और 11 'सामान्य' होंगे। मुझे यकीन नहीं है कि इससे कितना दूर विचलन हो सकता है; 10 स्तरों से अधिक नहीं, संभवतः कुछ हद तक गहराई से। बिना संतुलन वाला एक चरम मामला 1000 गहरा होगा; यादृच्छिक संख्या के साथ होने की संभावना नहीं है।

Answer 4

क्या पेड़ आप औसत ऊंचाई के रूप में प्रयोग कर रहे हैं किसी को पहले उल्लेख किया है, log2 (1000) हो जाएगा के बावजूद

। यह सच है कि संख्याओं के क्रम के आधार पर वास्तविक ऊंचाई भिन्न हो सकती है, लेकिन यादृच्छिक रूप से वितरित संख्याओं को मानते हुए, जो आप उल्लेख करते हैं, तो वास्तविक मूल्य, अपेक्षाकृत अधिक अनुमानित मूल्य अनुमानित करेगा (जो, एक बार फिर, लॉग 2 है (1000))

Answer 5

यह प्रश्न वास्तव में मुश्किल है। जवाब 1000 नहीं होगा, क्योंकि यह असंभव है, लेकिन लॉग 2 (1000) भी असंभव है, लेकिन पेड़ उगने के तरीके के आधार पर भी और भी अधिक है।

आप कदम हालांकि पेड़ तो भोलेपन से यह जोड़कर पेड़ लगभग हमेशा log2 (1000) से अधिक लंबी हो जाएगा द्वारा किसी पूर्णांक जोड़ें।

एक सांख्यिकीविद से बात करें, क्योंकि यह सामान्य संभावना वितरण से संबंधित प्रतीत होता है। वे बहुत सी यादृच्छिक यादृच्छिक घटनाओं (सिर एक इकाई दाएं, बाएं पूंछ के बाएं) द्वारा उत्पन्न होते हैं, और एक यादृच्छिक पूर्णांक का मूल्य पेड़ के माध्यम से फिर से शुरू होता है क्योंकि यह एक पत्ते में निकलता है।

Answer 6

यह सवाल है कि क्या आप मुझे निश्चित यह वास्तव में पेड़ पैदा करने के बिना काम कर सकते हैं पूछ मिला है।

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

मुझे जो जवाब मिले हैं वे इस आलेख में हैं। (X- अक्ष पेड़ में आइटमों की संख्या, नीली रेखा औसत ऊंचाई है, और लाल रेखा इष्टतम संभव ऊंचाई है)

 
N  Average Height 
2  2 
16 7.039 
32 9.280 
64 11.679 
256 16.783 
343 17.896 

Granitebolshevik सही है: यह संभव है लेकिन सांख्यिकीय रूप से असंभव है कि एक संतुलित लागू वृक्ष अतिरिक्त संतुलन कार्यक्षमता के बिना इष्टतम ऊंचाई होगी।

एल्गोरिथ्म हे की एक जटिलता (एन^2) है, और यह काफी तेजी से वास्तव में बड़ी संख्या की गणना करने के लिए नहीं है।

Answer 7

हालांकि सांख्यिक अनुमानों के एक नंबर, उदा .:

Devroye, ल्यूक देखते हैं इस सवाल का एक सरल जवाब होने के लिए वहाँ प्रकट नहीं होता है,। "द्विआधारी खोज पेड़ों की ऊंचाई पर एक नोट।" एसीएम जर्नल (जेएसीएम) 33.3 (1 9 86): 48 9-498।

रीड, ब्रूस। "एक यादृच्छिक बाइनरी खोज पेड़ की ऊंचाई।" एसीएम जर्नल (जेएसीएम) 50.3 (2003): 306-332।

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap13.htm

इन अनुमानों आम तौर पर रूप ले: A ln n - B ln ln n + C

कहाँ A~4.311 और B~1.953

तो शायद कहने के लिए सबसे अधिक उपयोगी बात यह है कि यादृच्छिक सम्मिलन के लिए औसत ऊंचाई O(log n) है, लेकिन अगर आपको वास्तव में संख्यात्मक अनुमान की आवश्यकता है तो मुझे लगता है कि (4.311 ln n - 1.953 ln ln n) बड़े एन के लिए पर्याप्त होगा। जो काफी अच्छी तरह से कहीं और सूचना प्रयोगात्मक परिणामों से फिट बैठता है -

n=1000 के लिए, कि 26 के बारे में देता है।