बाइनरी सर्च ट्री

निर्देश

बाइनरी ट्री में संख्याएँ डालिए और उन्हें खोजिए।

जब हमें क्रम में लगे डेटा को दिखाना होता है, तो ऐरे अच्छा डेटा स्ट्रक्चर नहीं होता।

मान लीजिए हमारे पास ऐरे [1, 3, 4, 5] है और हम उसमें 2 जोड़ देते हैं, तो वह [1, 3, 4, 5, 2] हो जाता है। अब हमें पूरे ऐरे को फिर से क्रम में लगाना पड़ेगा! हम इसे बेहतर बना सकते हैं। हमें बस नई चीज़ के लिए जगह बनानी है, [1, nil, 3, 4, 5], और फिर उस चीज़ को उसी बनाई गई जगह में डाल देना है। लेकिन इसमें भी हमें कई एलिमेंट को एक-एक जगह नीचे खिसकाना पड़ता है।

लेकिन बाइनरी सर्च ट्री क्रम में लगे डेटा पर कहीं ज़्यादा कुशलता से काम कर सकते हैं।

बाइनरी सर्च ट्री जुड़े हुए नोडों की एक श्रृंखला से बना होता है। हर नोड में डेटा का एक टुकड़ा होता है (जैसे संख्या 3), left नाम का एक वेरिएबल, और right नाम का एक वेरिएबल। left और right वेरिएबल या तो nil की ओर इशारा करते हैं, या दूसरे नोडों की ओर। चूँकि उन दूसरे नोडों के नीचे भी आगे और नोड होते हैं, हम कहते हैं कि left और right वेरिएबल सबट्री की ओर इशारा कर रहे हैं। बाएँ सबट्री का सारा डेटा मौजूदा नोड के डेटा से कम या उसके बराबर होता है, और दाएँ सबट्री का सारा डेटा मौजूदा नोड के डेटा से बड़ा होता है।

उदाहरण के लिए, अगर हमारे पास डेटा 4 वाला एक नोड हो और हम डेटा 2 जोड़ें, तो हमारा ट्री ऐसा दिखेगा:

  4
 /
2

अगर हम फिर 6 जोड़ें, तो यह ऐसा दिखेगा:

  4
 / \
2   6

अगर हम फिर 3 जोड़ें, तो यह ऐसा दिखेगा

   4
 /   \
2     6
 \
  3

और अगर हम फिर 1, 5, और 7 जोड़ें, तो यह ऐसा दिखेगा

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

ध्यान दें

आप चाहें तो एक ही क्लास के ऑब्जेक्ट इस्तेमाल कर सकते हैं, जो ट्री और सबट्री (नोड) को दर्शाते हैं। नोड जोड़ने और उन्हें क्रम में लगाने के लिए रिकर्शन का तरीका इस्तेमाल करने की कोशिश कीजिए।