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

निर्देश

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

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

मान लीजिए हमारे पास ऐरे [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

श्रेय

ये चित्र habere-et-dispertire ने बनाए हैं। इनमें Till Tantau द्वारा बनाए गए PGF/TikZ का उपयोग किया गया है।