নির্দেশনা
বাইনারি ট্রি-তে সংখ্যা ইনসার্ট করুন ও খুঁজুন।
সর্ট করা ডেটা উপস্থাপন করতে হলে অ্যারে ভালো কোনো ডেটা স্ট্রাকচার নয়।
ধরা যাক আমাদের কাছে [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-র তৈরি।
CoffeeScript সংক্রান্ত নির্দিষ্ট নির্দেশনা
একটি BinarySearchTree ইনস্ট্যান্সে ৩টি প্রপার্টি থাকতে হবে: data, left এবং right.
একটি ইনস্ট্যান্সে নিচের মেথডগুলো থাকতে হবে:
-
insert, যা ট্রিতে নতুন একটি ডেটা যোগ করে। এটি ট্রির কোথাও একটি নতুন "লিফ" নোড যোগ করবে।
-
each, যা একটি "কলব্যাক" আর্গুমেন্ট নেয়। এটি এমন একটি ফাংশন, যা ট্রির প্রতিটি ডেটার উপর ক্রম অনুসারে কল করা হবে।
এই অনুশীলনীটি রিকার্সন অনুশীলন করার জন্য চমৎকার একটি জায়গা।
সূত্র
Josh Cheek
