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

নির্দেশনা

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

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

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

ইমপ্লিমেন্টেশন

Cairo-তে (বা ইমিউটেবল মেমরিসম্পন্ন যেকোনো পিউরলি ফাংশনাল ভাষায়) একটি দক্ষ ও পরিবর্তনযোগ্য ট্রি স্ট্রাকচার ইমপ্লিমেন্ট করা চ্যালেঞ্জিং, কারণ এই ভাষাগুলো এমনভাবে ডিজাইন করা হয়েছে যাতে ডেটা তৈরি হওয়ার পরে তা পরিবর্তন করা এড়ানো যায়। এই ইমিউটেবিলিটির মানে হলো, সরাসরি একটি ট্রি নোড আপডেট করার বদলে আপনি যখনই এটিকে পরিবর্তন করেন, তখনই ট্রিটির একটি নতুন ভার্সন তৈরি করতে হয়।

কেন এমন হয় তা দেখানোর জন্য, একটি সরল বাইনারি ট্রি স্ট্রাকচার কল্পনা করুন, যেখানে প্রতিটি নোডের একটি বাম চাইল্ড ও একটি ডান চাইল্ড থাকে। ধরা যাক, আমরা এইরকম একটি ছোট ট্রি দিয়ে শুরু করি:

       1
      / \
     2   3

এখন ধরা যাক, আমরা নোড 2-এর বাম চাইল্ড হিসেবে একটি নতুন নোড 4 যোগ করতে চাই। পিউরলি ফাংশনাল ভাষায় (যেমন Cairo বা Haskell-এ), মেমরি ইমিউটেবল, তাই আমরা সরাসরি 2-এ নোড 4 যোগ করতে পারি না। এর বদলে, রুট থেকে পরিবর্তিত নোড পর্যন্ত পাথের প্রতিটি নোডের একটি নতুন ভার্সন তৈরি করতে হয়, কারণ এই পাথের প্রতিটি নোড এখন একটি নতুন বা পরিবর্তিত সাবট্রি-কে পয়েন্ট করে।

এই প্রক্রিয়াটি দেখতে এমন হবে:

1. নোড 4 নোড 2-এ যোগ করুন:

   • নোড 2-এর একটি নতুন ভার্সন তৈরি করুন, যার এখন বাম চাইল্ড হিসেবে 4 আছে।

       2'
      / 
     4   
   

2. রুট নোড আপডেট করুন:

   • যেহেতু নোড 1 মূলত পুরোনো 2-কে পয়েন্ট করত, তাই আমরা রুট নোড 1'-এর একটি নতুন ভার্সন তৈরি করি, যা এখন বাম দিকে আপডেট করা নোড 2'-কে পয়েন্ট করে এবং ডান দিকে নোড 3 রাখে।

       1'
      / \
     2'  3
   

সুতরাং, ফলাফল ট্রিটি হয়:

       1'
      / \
     2'  3
    /
   4

এই নতুন ট্রিটি (1') এখনও আসল ট্রির মতো, তবে এর পাথটি আপডেট করা। মূল বিষয় হলো, ইমিউটেবিলিটি ধরে রাখতে আমাদের পাথের প্রতিটি নোড (1 থেকে 2) পুনরায় তৈরি করতে হয়েছিল, কারণ বিদ্যমান নোডগুলোকে জায়গায় বসে পরিবর্তন করা যায় না। আসল ট্রিটি এখনও আছে (উদাহরণস্বরূপ, এর আসল রুট 1-এর সমস্ত রেফারেন্সের জন্য), আর এই নতুন ট্রিটি পরিবর্তিত অবস্থা প্রকাশ করে।

বড় ট্রিতে এই পদ্ধতিটি ব্যয়বহুল হয়ে উঠতে পারে, কারণ প্রতিটি নতুন পরিবর্তনের জন্য রুট থেকে আপডেট করা নোড পর্যন্ত নোডের একটি পাথ পুনরায় তৈরি করতে হয়, এমনকি যদি ট্রির সামান্য অংশই বাস্তবে পরিবর্তিত হয়।