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

निर्देश

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

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

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

संकेत

इस अभ्यास को पूरा करने के लिए आपको BST डेटा टाइप बनाना होगा, जिसमें Eq और Show के इंस्टेंस हों, और इन फंक्शनों को लागू करना होगा:

• bstLeft
• bstRight
• bstValue
• empty
• fromList
• insert
• singleton
• toList

फाइल में एक डमी डेटा डिक्लेरेशन और टाइप सिग्नेचर पहले से मौजूद हैं, लेकिन इन फंक्शनों को बनाना और एक सार्थक डेटा टाइप, न्यूटाइप या टाइप सिनोनिम तैयार करना आपका काम है।