ট্রি (Tree) একটি গাণিতিক ডেটা স্ট্রাকচার যা হায়ারার্কিকাল (সামরিক) সম্পর্ককে উপস্থাপন করে। এটি মূলত একটি গাছের মতো গঠন, যেখানে একটি মূল নোড (root node) থাকে এবং এটি বিভিন্ন শাখা (branches) এবং পাতা (leaves) নিয়ে গঠিত। ট্রি ডেটা স্ট্রাকচারগুলির মধ্যে বিভিন্ন ধরনের ট্রি রয়েছে, যার মধ্যে বাইনারি ট্রি, বাইনারি সার্চ ট্রি (BST), এবং AVL ট্রি অন্যতম। নিচে এগুলোর সম্পর্কে বিস্তারিত আলোচনা করা হলো।
১. বাইনারি ট্রি (Binary Tree)
বিবরণ: বাইনারি ট্রি একটি ট্রি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোড সর্বাধিক দুটি সন্তান (child) নোড ধারণ করতে পারে, যা সাধারণত "বাম সন্তান" (left child) এবং "ডান সন্তান" (right child) হিসেবে পরিচিত।
বৈশিষ্ট্য:
- গঠন: প্রতিটি নোডে ০, ১ বা ২টি সন্তান থাকতে পারে।
- গভীরতা: একটি বাইনারি ট্রির গভীরতা হল সেই সর্বাধিক স্তরের সংখ্যা যা মূল নোড থেকে পাতালোক পর্যন্ত চলে যায়।
- বিন্যাস: সাধারণত বাইনারি ট্রির তিনটি প্রধান ট্রাভার্সাল পদ্ধতি থাকে: ইন-অর্ডার (in-order), প্রি-অর্ডার (pre-order), এবং পোস্ট-অর্ডার (post-order)।
উদাহরণ:
A
/ \
B C
/ \
D E
২. বাইনারি সার্চ ট্রি (Binary Search Tree - BST)
বিবরণ: বাইনারি সার্চ ট্রি একটি বিশেষ ধরনের বাইনারি ট্রি, যেখানে প্রতিটি নোডের বাম সন্তানটির মান উক্ত নোডের মানের চেয়ে ছোট এবং ডান সন্তানটির মান উক্ত নোডের মানের চেয়ে বড়। এটি ডেটা অনুসন্ধান এবং সংরক্ষণ করার জন্য কার্যকরী।
বৈশিষ্ট্য:
- ডেটা সংগঠন: BST এর সাহায্যে দ্রুত ডেটা অনুসন্ধান, ইনসার্ট, এবং ডিলিট করা যায় (গড় সময় O(log n))।
- অর্ডার: ইন-অর্ডার ট্রাভার্সাল করলে BST এর এলিমেন্টগুলি ক্রমবর্ধমানভাবে পাওয়া যায়।
উদাহরণ:
10
/ \
5 15
/ \ / \
3 7 12 20
৩. AVL ট্রি (AVL Tree)
বিবরণ: AVL ট্রি একটি ব্যালেন্সড বাইনারি সার্চ ট্রি, যেখানে প্রতিটি নোডের বাম ও ডান subtree এর উচ্চতার মধ্যে সর্বাধিক ১-এর পার্থক্য থাকে। AVL ট্রি ডেটার কার্যকরী সঞ্চয় নিশ্চিত করে এবং দ্রুত অনুসন্ধান এবং ইনসার্টের জন্য পরিচিত।
বৈশিষ্ট্য:
- ব্যালেন্সিং: AVL ট্রি ইনসার্ট বা ডিলিট করার পর, যদি কোন নোডের ব্যালেন্স ফ্যাক্টর ১, ০, বা -১ এর বাইরে চলে যায়, তবে তা পুনর্বিন্যাস করা হয়।
- গতি: AVL ট্রি গড় সময় O(log n) এ অনুসন্ধান, ইনসার্ট এবং ডিলিটের কাজ করে।
উদাহরণ:
30
/ \
20 40
/ \ \
10 25 50
সারসংক্ষেপ
- বাইনারি ট্রি: একটি সাধারণ ট্রি স্ট্রাকচার, যেখানে প্রতিটি নোডের সর্বাধিক দুটি সন্তান থাকে।
- BST: বাইনারি সার্চ ট্রি, যা অনুসন্ধান ও সঞ্চয়ের জন্য একটি বিশেষ রূপের ট্রি।
- AVL ট্রি: একটি ব্যালেন্সড BST, যা ডেটার উচ্চ কার্যকারিতা নিশ্চিত করে এবং দ্রুত অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশন করে।
এই ট্রি ডেটা স্ট্রাকচারগুলো ডেটা সংগঠনের জন্য অত্যন্ত গুরুত্বপূর্ণ এবং সঠিকভাবে ব্যবহার করা হলে ডেটা পরিচালনার গতি ও কার্যকারিতা বৃদ্ধি পায়।
Read more
