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

নির্দেশনা

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

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

ধরা যাক আমাদের কাছে [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-র তৈরি।

নোট

আপনি একই ক্লাসের এমন অবজেক্ট ব্যবহার করতে চাইতে পারেন, যেগুলো ট্রি ও সাবট্রি (নোড) প্রকাশ করে। নোড যোগ করা ও সাজানোর জন্য রিকার্সন মেথড ব্যবহার করার চেষ্টা করুন।