বাইনারি ট্রি একটি বিশেষ ডেটা স্ট্রাকচার যা ডেটা স্টোরেজের উদ্দেশ্যে ব্যবহৃত হয়। একটি বাইনারি ট্রির একটি বিশেষ শর্ত আছে যে প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড থাকতে পারে। একটি বাইনারি ট্রির সুবিধা হলো এটি একটি সর্টেড অ্যারে এবং একটি লিংকড লিস্ট উভয়ের সুবিধা দেয় কারণ সার্চ সর্টেড অ্যারেতে যত দ্রুত এবং ইনসারশন বা ডিলিশন অপারেশন লিংকড লিস্টে যত দ্রুত।
নিচে একটি বাইনারি ট্রির চিত্র দেওয়া হলো কিছু টার্মসহ যা আমরা নিচে আলোচনা করেছি:
গুরুত্বপূর্ণ টার্মস
ট্রির সাথে সম্পর্কিত গুরুত্বপূর্ণ টার্মস নিচে দেওয়া হলো।
পাথ (Path) − পাথ বলতে একটি ট্রির এজগুলোর طولে নোডগুলির ক্রমকে বোঝায়।
রুট (Root) − ট্রির শীর্ষে অবস্থিত নোডকে রুট বলা হয়। প্রতিটি ট্রিতে শুধু একটি রুট থাকে এবং রুট নোড থেকে যেকোনো নোডে শুধু একটি পাথ থাকে।
প্যারেন্ট (Parent) − রুট নোড বাদে যেকোনো নোডের একটি এজ উপরের দিকে একটি নোডের সাথে থাকে যাকে প্যারেন্ট বলা হয়।
চাইল্ড (Child) − একটি প্রদত্ত নোডের নিচে এর এজ দ্বারা সংযুক্ত নোডকে এর চাইল্ড নোড বলা হয়।
লীফ (Leaf) − যেই নোডের কোনো চাইল্ড নোড নেই সেটাকে লীফ নোড বলা হয়।
সাবট্রি (Subtree) − সাবট্রি একটি নোডের সন্ততিগুলোকে প্রতীকবদ্ধ করে।
ভিজিটিং (Visiting) − ভিজিটিং বলতে নোডের ওপর কন্ট্রোল থাকার সময় নোডের ভ্যালু চেক করা বোঝায়।
ট্রাভারসিং (Traversing) − ট্রাভারসিং বলতে নোডগুলোর মধ্য থেকে নির্দিষ্ট ক্রমে পাস করা বোঝায়।
লেভেল (Levels) − একটি নোডের লেভেল সেই নোডের জেনারেশনকে প্রতীকবদ্ধ করে। যদি রুট নোড লেভেল ০-তে থাকে, তবে এর পরবর্তী চাইল্ড নোড লেভেল ১-তে, এর নাতি লেভেল ২-তে থাকবে, ইত্যাদি।
কি (Keys) − কি একটি নোডের ভ্যালুকে প্রতীকবদ্ধ করে যার ভিত্তিতে একটি নোডের জন্য সার্চ অপারেশন চালানো হয়।
