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

निर्देश

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

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

मान लीजिए हमारे पास ऐरे [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 का उपयोग किया गया है।

कार्यान्वयन

Cairo में (या फिर अपरिवर्तनीय मेमोरी वाली किसी भी पूर्णतः फंक्शनल भाषा में) एक कुशल और बदलने योग्य ट्री संरचना बनाना मुश्किल है, क्योंकि ऐसी भाषाएँ इस तरह बनाई जाती हैं कि एक बार डेटा बन जाने के बाद उसे बदलने से बचा जाए। अपरिवर्तनीयता का मतलब है कि किसी ट्री नोड को सीधे बदलने के बजाय, जब भी आप ट्री में कोई बदलाव करते हैं, ट्री का एक नया रूप बनाना पड़ता है।

यह समझने के लिए कि ऐसा क्यों होता है, एक साधारण बाइनरी ट्री की संरचना की कल्पना कीजिए, जिसके हर नोड का एक बायाँ और एक दायाँ चाइल्ड होता है। मान लीजिए कि शुरू में हमारे पास इस तरह का एक छोटा ट्री है:

       1
      / \
     2   3

अब मान लीजिए कि हम नोड 2 के बाएँ चाइल्ड के रूप में एक नया नोड 4 जोड़ना चाहते हैं। किसी पूर्णतः फंक्शनल भाषा (जैसे Cairo या Haskell) में मेमोरी अपरिवर्तनीय होती है, इसलिए हम नोड 4 को सीधे 2 में नहीं जोड़ सकते। इसके बजाय, रूट से लेकर बदले गए नोड तक के रास्ते में आने वाले हर नोड का एक नया रूप बनाना पड़ता है, क्योंकि इस रास्ते का हर नोड अब किसी नए या बदले हुए सबट्री की ओर इशारा करता है।

यह प्रक्रिया कुछ इस तरह दिखेगी:

1. नोड 4 को नोड 2 में जोड़िए:

   • नोड 2 का एक नया रूप बनाइए, जिसका बायाँ चाइल्ड अब 4 होता है।

       2'
      / 
     4   
   

2. रूट नोड को बदलिए:

   • चूँकि नोड 1 पहले पुराने 2 की ओर इशारा करता था, हम रूट नोड का एक नया रूप 1' बनाते हैं, जो अब बाईं ओर बदले हुए नोड 2' की ओर इशारा करता है और दाईं ओर नोड 3 को बनाए रखता है।

       1'
      / \
     2'  3
   

तो नतीजा यह ट्री बनता है:

       1'
      / \
     2'  3
    /
   4

यह नया ट्री (1') दिखने में मूल ट्री जैसा ही है, बस इसका रास्ता बदल गया है। मुख्य बात यह है कि अपरिवर्तनीयता बनाए रखने के लिए हमें रास्ते के हर नोड (1 से 2 तक) को फिर से बनाना पड़ा, क्योंकि जो नोड पहले से मौजूद हैं, उन्हें उसी जगह पर बदला नहीं जा सकता। मूल ट्री अब भी मौजूद है (उदाहरण के लिए, उसके मूल रूट 1 के सारे रेफरेंस के लिए), जबकि यह नया ट्री बदली हुई स्थिति को दर्शाता है।

बड़े ट्री में यह तरीका महंगा पड़ सकता है, क्योंकि हर नए बदलाव के लिए रूट से लेकर बदले गए नोड तक के सारे नोड फिर से बनाने पड़ते हैं, चाहे ट्री का वास्तव में सिर्फ एक छोटा हिस्सा ही बदला हो।