ট্রি (Binary, BST, AVL)

Binary Tree-এর অপরিহার্য গাণিতিক সূত্র

Assistant Programmer ও সমমানের পরীক্ষায় সরাসরি সূত্র থেকে MCQ আসে:

• লেভেল L-এ (root-এর লেভেল 0 ধরলে) সর্বোচ্চ node সংখ্যা = 2^L
• উচ্চতা h (root-এর উচ্চতা 0 ধরলে) বিশিষ্ট Binary Tree-তে সর্বোচ্চ মোট node = 2^(h+1) − 1
• যেকোনো non-empty Binary Tree-তে leaf node সংখ্যা (n₀) এবং ২-ডিগ্রি বিশিষ্ট internal node সংখ্যা (n₂)-এর সম্পর্ক: n₀ = n₂ + 1
• Strict/Full Binary Tree-তে মোট internal node I হলে মোট leaf node L = I + 1 এবং মোট node N = 2I + 1
• Complete Binary Tree-কে 0-indexed অ্যারেতে রাখলে index i-এর left child = 2i + 1, right child = 2i + 2, এবং parent = ⌊(i − 1) / 2⌋

Tree Traversal (ভিজিট করার ক্রম)

• Inorder (Left → Root → Right): Binary Search Tree (BST)-এর ক্ষেত্রে সর্বদা মানগুলো ঊর্ধ্বক্রমে (sorted order) দেয়।
• Preorder (Root → Left → Right): Prefix এক্সপ্রেশন তৈরি ও ট্রি ক্লোন করতে ব্যবহৃত হয়। প্রথম উপাদানটি সবসময় Root।
• Postorder (Left → Right → Root): Postfix এক্সপ্রেশন ও ট্রি মেমোরি থেকে মুছে ফেলতে (deletion) ব্যবহৃত হয়। শেষ উপাদানটি সবসময় Root।

        40
       /  \
     20    60
    /  \
  10   30

Inorder   : 10, 20, 30, 40, 60
Preorder  : 40, 20, 10, 30, 60
Postorder : 10, 30, 20, 60, 40

BST ও AVL Tree

• BST শর্ত: বাম সাবট্রির সকল মান < Root < ডান সাবট্রির সকল মান।
• সাধারণ BST-তে search/insert/delete-এর গড় সময় O(log n), কিন্তু একদিকে হেলে পড়া (skewed) ট্রিতে worst-case সময় O(n)।
• AVL Tree: একটি self-balancing BST যেখানে প্রতিটি node-এর Balance Factor = height(left) − height(right) সর্বদা {-1, 0, +1}-এর মধ্যে থাকে।
• ব্যালেন্স নষ্ট হলে ৪ ধরনের রোটেশন ব্যবহৃত হয়: LL (একটি Right rotation), RR (একটি Left rotation), LR (Left তারপর Right rotation) এবং RL (Right তারপর Left rotation)। AVL Tree-তে worst-case search/insert/delete সর্বদা O(log n)।