बाइनरी खोज वृक्ष निर्माण को समझना

Question

मुझे मुश्किल समय समझ रहा है कि बाइनरी खोज पेड़ कैसे बनाए जाते हैं। शीर्षतम रूट खोजने के लिए क्या उन्हें प्रारंभिक डेटा को सॉर्ट करने की आवश्यकता है?

Answer 1

आकार कि एक द्विआधारी खोज वृक्ष लेता है दो बातों पर निर्भर करता है:

1. जिस क्रम में तत्वों डाला जाता है, और
2. क्या संतुलन संचालन, यदि कोई हो, पेड़ प्रविष्टि के दौरान करता है।

यदि आपके पास शुद्ध पुनर्मूल्यांकन तर्क के साथ शुद्ध बाइनरी खोज पेड़ है, तो ऑर्डर जिसमें तत्व डाले जाते हैं, पेड़ के आकार पर एक मजबूत प्रभाव डालेगा। उदाहरण के लिए, मान 1, 2, 3, 4, 5, 6, 7 लें। यदि आप उन्हें क्रमशः 4, 2, 6, 1, 3, 5, 7 में डालते हैं, तो आपको यह पेड़ मिलेगा:

,

 4 

    4 
/
    2 

    4 
/ \ 
    2  6 

    4 
/ \ 
    2  6 
/
1 

    4 
/ \ 
    2  6 
/\ 
1 3 

    4 
/ \ 
    2  6 
/\ /
1 3 5 

    4 
/ \ 
    2  6 
/\ /\ 
1 3 5 7 

दूसरी ओर अगर आप 1, 2, 3, 4, 5, 6 में मान सम्मिलित करें:

 4 
    / \ 
    2  6 
    /\ /\ 
    1 3 5 7 

इस का कारण यह है कि हम पेड़ों की आगामी श्रृंखला के माध्यम से जाना है , 7, आपको यह पेड़ मिलता है:

1 
\ 
    2 
    \ 
    3 
    \ 
     4 
     \ 
     5 
     \ 
      6 
      \ 
      7 

दिलचस्प बात यह है कि क्रमबद्ध क्रम में बीएसटी में तत्व डालना ओ है के सबसे खराब चीजें जो आप पेड़ के लिए कर सकते हैं, क्योंकि यह पेड़ को एक रैखिक संरचना बनाता है। आप सम्मिलित करने के लिए तत्वों का एक यादृच्छिक क्रमपरिवर्तन उठा से बेहतर कर रहे हैं, या उन्हें छंटाई और अनुसार क्रमबद्ध क्रम पर निम्नलिखित पुनरावर्ती एल्गोरिदम के उपयोग (वे सब पहले से भी जाना जाता है कर रहे हैं):

• अगर कोई तत्व हैं, आप कर चुके हैं।
• अन्यथा:
  • मध्यस्थ को बीएसटी में डालें।
  • बीएसटी में तत्वों के पहले भाग को दोबारा सम्मिलित करें।
  • बीएसटी में तत्वों के दूसरे भाग को रिकर्सिव रूप से सम्मिलित करें।

आशा इस मदद करता है!