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

নির্দেশনা

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

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

ধরা যাক আমাদের কাছে [1, 3, 4, 5] অ্যারেটি আছে, আর আমরা এতে 2 যোগ করলাম, ফলে সেটি হয়ে গেল [1, 3, 4, 5, 2]। এখন আমাদের পুরো অ্যারেটি আবার সাজাতে হবে! নতুন এলিমেন্টটির জন্য শুধু একটু জায়গা বানালেই হয় [1, nil, 3, 4, 5], তারপর যে জায়গাটি বানালাম সেখানে এলিমেন্টটি বসিয়ে দিলেই হয়, এটা বুঝলে আমরা বিষয়টি আরও ভালোভাবে করতে পারি। কিন্তু এতেও আমাদের অনেক এলিমেন্ট এক ঘর নিচে সরাতে হয়।

তবে বাইনারি সার্চ ট্রি সাজানো ডেটার উপর অনেক বেশি দক্ষতার সাথে কাজ করতে পারে।

একটি বাইনারি সার্চ ট্রি পরস্পর সংযুক্ত কিছু নোড নিয়ে গঠিত। প্রতিটি নোডে থাকে এক টুকরো ডেটা (যেমন সংখ্যা 3), left নামের একটি ভ্যারিয়েবল এবং right নামের একটি ভ্যারিয়েবল। left ও right ভ্যারিয়েবলগুলো nil অথবা অন্য নোডের দিকে নির্দেশ করে। যেহেতু এই অন্য নোডগুলোর আবার নিচে অন্য নোড থাকে, তাই আমরা বলি বাম ও ডান ভ্যারিয়েবলগুলো সাবট্রির দিকে নির্দেশ করছে। বাম সাবট্রির সব ডেটা বর্তমান নোডের ডেটার চেয়ে ছোট বা সমান, আর ডান সাবট্রির সব ডেটা বর্তমান নোডের ডেটার চেয়ে বড়।

উদাহরণস্বরূপ, যদি আমাদের কাছে 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 ব্যবহার করে।