মৌলিক ধারণা
একটি বাইনারি ট্রি হলো এমন একটি ট্রি যেখানে কোনো নোডের দুইটির অধিক চাইল্ড থাকতে পারে না। যেকোনো নোডের সর্বোচ্চ ডিগ্রি হলো দুই। এটি ইঙ্গিত করে যে একটি বাইনারি ট্রির ডিগ্রি শূন্য, এক বা দুই হতে পারে।
উপরোক্ত ফিগার-এ, বাইনারি ট্রি একটি রুট এবং দুটি সাবট্রি TreeLeft & TreeRight নিয়ে গঠিত। বাইনারি ট্রির বামপাশের সকল নোড বাম সাবট্রি হিসেবে নির্দেশ করা হয় এবং ডানপাশের সকল নোড ডান সাবট্রি হিসেবে উল্লেখ করা হয়।
বাস্তবায়ন
একটি বাইনারি ট্রির সর্বোচ্চ দুইটি চাইল্ড থাকে; আমরা সিগুলোর দিকে সরাসরি পয়েন্টার অ্যাসাইন করতে পারি। ট্রি নোডের ডিক্লারেশন ডাবলি লিংকড লিস্টের স্ট্রাকচারের মতোই, অর্থাৎ একটি নোড হলো একটি স্ট্রাকচার যাতে কী ইনফরমেশন প্লাস দুটি পয়েন্টার (left এবং right) অন্যান্য নোডের দিকে থাকে।
বাইনারি ট্রি নোড ডিক্লারেশন
typedef struct tree_node *tree_ptr; struct tree_node { element_type element1; tree_ptr left1; tree_ptr right1; }; typedef tree_ptr TREE;
বাইনারি ট্রির প্রকারভেদ
স্ট্রিক্টলি বাইনারি ট্রি (Strictly binary tree)
স্ট্রিক্টলি বাইনারি ট্রি হলো এমন একটি বাইনারি ট্রি যেখানে সকল নোডের অথবা শূন্য অথবা দুইটি চাইল্ড থাকবে। এতে কোনো নোডে একক চাইল্ড থাকবে না।
স্কিউ ট্রি (Skew tree)
একটি স্কিউ ট্রি হলো এমন একটি বাইনারি ট্রি যেখানে লিফ ছাড়া প্রতিটি নোডের শুধু একক চাইল্ড নোড থাকে। স্কিউ ট্রির দুটি প্রকার আছে, অর্থাৎ লেফট স্কিউড বাইনারি ট্রি এবং রাইট স্কিউড বাইনারি ট্রি।
লেফট স্কিউড বাইনারি ট্রি (Left skewed binary tree)
একটি লেফট স্কিউ ট্রিতে নোড শুধু বাম চাইল্ডের সাথে জড়িত থাকে। এটি একটি বাইনারি ট্রি যাতে শুধু বাম সাবট্রি থাকে।
রাইট স্কিউড বাইনারি ট্রি (Right skewed binary tree)
একটি রাইট স্কিউ ট্রিতে নোড শুধু ডান চাইল্ডের সাথে জড়িত থাকে। এটি একটি বাইনারি ট্রি যাতে শুধু ডান সাবট্রি থাকে।
ফুল বাইনারি ট্রি বা প্রপার বাইনারি ট্রি (Full binary tree or proper binary tree)
একটি বাইনারি ট্রি ফুল বাইনারি ট্রি বলা হয় যদি সকল লিফ একই লেভেলে থাকে এবং প্রতিটি নন-লিফ নোডের ঠিক দুটি চাইল্ড থাকে এবং এতে সকল লেভেলে সম্ভাব্য সর্বোচ্চ নোড থাকে। উচ্চতা h-র একটি ফুল বাইনারি ট্রিতে সর্বোচ্চ 2h+1 – 1টি নোড থাকে।
কম্পлиট বাইনারি ট্রি (Complete binary tree)
প্রতিটি নন-লিফ নোডের ঠিক দুটি চাইল্ড থাকে কিন্তু সকল লিফ একই লেভেলে থাকতে বাধ্য নয়। একটি কম্পলিট বাইনারি ট্রি হলো এমন একটি ট্রি যেখানে সব লেভেলে সর্বোচ্চ নোড থাকে শুধু শেষ লেভেল বাদে। শেষ লেভেলের এলিমেন্টগুলো বাম থেকে ডান দিকে পূরণ করা থাকবে।
প্রায় কম্পলিট বাইনারি ট্রি (Almost complete binary tree)
একটি প্রায় কম্পলিট বাইনারি ট্রি হলো এমন একটি ট্রি যেখানে প্রতিটি নোড যেন ডান চাইল্ড থাকে তবে তার বাম চাইল্ডও থাকবে। বাম চাইল্ড থাকলে ডান চাইল্ড থাকতে বাধ্য নয়।
জেনারেল ট্রি এবং বাইনারি ট্রির পার্থক্য
জেনারেল ট্রি (General Tree)
- জেনারেল ট্রির চাইল্ড সংখ্যার কোনো লিমিট নেই।
- জেনারেল ট্রিতে এক্সপ্রেশন ইভ্যালুয়েট করা কঠিন।
বাইনারি ট্রি (Binary Tree)
- একটি বাইনারি ট্রির সর্বোচ্চ দুটি চাইল্ড থাকে।
- বাইনারি ট্রিতে এক্সপ্রেশন ইভ্যালুয়েশন সহজ।
ট্রির অ্যাপ্লিকেশন
- অ্যারিথমেটিক এক্সপ্রেশন ম্যানিপুলেশন
- সিম্বল টেবিল কনস্ট্রাকশন
- সিনট্যাক্স অ্যানালিসিস
- গ্রামার রাইটিং
- এক্সপ্রেশন ট্রি ক্রিয়েশন
