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

নির্দেশনা

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

আমাদের যখন সাজানো ডেটা উপস্থাপন করতে হয়, তখন একটি অ্যারে ভালো ডেটা স্ট্রাকচার হিসেবে কাজ করে না।

ধরুন আমাদের কাছে [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