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

निर्देश

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

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

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

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

बाइनरी सर्च ट्री कई जुड़े हुए नोड से बना होता है। हर नोड में एक डेटा रखा होता है (जैसे संख्या 3), साथ ही left नाम का एक वेरिएबल और right नाम का एक वेरिएबल। left और right वेरिएबल या तो nil की ओर इशारा करते हैं, या किसी दूसरे नोड की ओर। चूँकि उन दूसरे नोड के नीचे भी और नोड होते हैं, इसलिए हम कहते हैं कि left और right वेरिएबल किसी सबट्री की ओर इशारा कर रहे होते हैं। 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

श्रेय

ये चित्र habere-et-dispertire ने Till Tantau के PGF/TikZ की मदद से बनाए हैं।