বাইনারি সার্চ ট্রি

নির্দেশনা

বাইনারি ট্রি-তে সংখ্যা ইনসার্ট করুন ও খুঁজুন।

সর্ট করা ডেটা উপস্থাপন করতে হলে অ্যারে ভালো কোনো ডেটা স্ট্রাকচার নয়।

ধরা যাক আমাদের কাছে [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 তৈরি করেছেন PGF/TikZ ব্যবহার করে, যা Till Tantau-র তৈরি।

SML-নির্দিষ্ট নির্দেশাবলি

বাইনারি সার্চ ট্রি যেকোনো ক্রমবদ্ধ ডেটা টাইপের জন্য উপযোগী, কেবল সংখ্যার জন্য নয়।

Notes on Programming SML/NJ-এর ২.৬ নম্বর সেকশনে পলিমরফিজম নিয়ে আলোচনা করা হয়েছে, আর ৪.১ নম্বর সেকশনে compare ফাংশনগুলোর ব্যবহার নিয়ে আলোচনা করা হয়েছে।