Trees — The Concept¶
অধ্যায়ের সূচি · সহজ ব্যাখ্যা ও বাস্তব ব্যবহার · অনুশীলন ও সমাধান
একটা বাস্তব জীবনের analogy দিয়ে শুরু করি¶
তোমার computer-এর file explorer খোলো। উপরে একটাই folder। তার ভেতরে: file আর আরো folder। সেগুলোর ভেতরে: file আর আরো folder। এই nesting-টা — প্রতিটা জিনিসের ঠিক একটা container, আর container-গুলো অনেক জিনিস ধরে — এটাই একটা tree।
অথবা genealogy-র কায়দায় আঁকা একটা family tree কল্পনা করো: উপরে এক পূর্বপুরুষ, নিচে সন্তানেরা, তাদের নিচে নাতি-নাতনিরা। ছবিতে প্রতিটা মানুষের (সবার উপরের পূর্বপুরুষ বাদে) ঠিক একজন parent। Tree-র vocabulary আক্ষরিক অর্থেই এই ছবি থেকে ধার করা: parent, child, sibling, ancestor, descendant।
মূল অনুভূতিটা: tree হলো one-to-many, কোনো cycle নেই। একটা folder কখনো নিজের ভেতরে থাকে না; তুমি নিজের দাদা হতে পারো না।
এক ছবিতে পুরো vocabulary¶
(A) ← ROOT: the one node with no parent
/ \
(B) (C) ← B and C are CHILDREN of A; A is their PARENT
/ \ \ B and C are SIBLINGS
(D) (E) (F) ← D, E, F: LEAVES (no children)
- Node: একটা গোলক। একটা value আর child-দের link ধরে রাখে।
- Edge: parent আর child-এর মাঝের দাগ। n-টা node-এর tree-তে সবসময় ঠিক n - 1টা edge।
- Root: একমাত্র উপরের node (A)।
- Leaf: যে node-এর কোনো child নেই (D, E, F)।
- Depth of a node: ROOT থেকে তার পর্যন্ত edge-এর সংখ্যা। depth(A)=0, depth(B)=1, depth(D)=2।
- Height of a node: তার থেকে নিচে কোনো leaf পর্যন্ত LONGEST path-এর edge-এর সংখ্যা। height(D)=0, height(B)=1, height(A)=2। Tree-র height = root-এর height।
- Subtree: যেকোনো node আর তার নিচের সবকিছু। B-র subtree নিজেই একটা সম্পূর্ণ ছোট tree — এই self-similarity-র কারণেই recursion নিখুঁত খাপ খায়।
Depth মাপে উপর থেকে; height মাপে নিচ পর্যন্ত। এ দুটো গুলিয়ে ফেলাই classic vocabulary bug।
Memory-র ছবি: একটা node আসলে কী¶
Binary tree-র node মানে শুধু একটা value আর দুটো reference:
class TreeNode: one node in memory:
def __init__(self, val):
self.val = val ┌─────────────┐
self.left = None │ val: 8 │
self.right = None │ left: ●───┼──► (node 3 (left child))
│ right: ●───┼──► (node 10 (right child))
└─────────────┘
পুরো tree মানে memory-তে ছড়িয়ে থাকা node, এই reference-গুলো দিয়ে সেলাই করা — হুবহু linked list-এর মতো, শুধু প্রতিটা node সর্বোচ্চ দুটো node-এর দিকে নিচে point করে। কোনো বড় contiguous block নেই; প্রতিটা missing child-কে None চিহ্নিত করে।
┌───────┐
│ 8 │
└─┬───┬─┘
left │ │ right
┌─────▼┐ ┌▼──────┐
│ 3 │ │ 10 │
└┬────┬┘ └─┬────┬┘
┌▼┐ ┌▼┐ (None) ┌▼─┐
│1│ │6│ │14│ leaves: left=None, right=None
└─┘ └─┘ └──┘
Binary tree vs binary search tree¶
Binary tree শুধু প্রতিশ্রুতি দেয় "সর্বোচ্চ দুটো child।" Value যেখানে খুশি বসতে পারে।
Binary search tree (BST) এর সাথে ordering invariant-টা যোগ করে:
প্রতিটা node-এর জন্য: তার left subtree-র সব value কঠোরভাবে ছোট, আর right subtree-র সব value কঠোরভাবে বড়।
A valid BST: NOT a BST (looks fine locally!):
8 8
/ \ / \
3 10 3 10
/ \ \ / \ \
1 6 14 1 9 14
▲
9 > 8 but sits in 8's LEFT subtree.
Each parent-child pair is ordered,
yet the WHOLE-SUBTREE rule is broken.
ডানদিকের ফাঁদটার জন্যই "validate BST" এত বিখ্যাত interview question: নিয়মটা পুরো subtree-কে বাঁধে, শুধু সরাসরি child-দের না। সঠিক validation recursion-এর নিচে (low, high) bounds পাঠিয়ে দেয় — দেখো implementation.py।
Core invariants¶
- ঠিক একটা root; বাকি প্রতিটা node-এর ঠিক একটা parent।
- কোনো cycle নেই — child link ধরে গেলে কোনো node-এ দ্বিতীয়বার ফেরা যায় না।
- n-টা node ⇒ n - 1টা edge।
- প্রতিটা subtree নিজেই একটা valid tree (recursion-এর আইনি ভিত্তি)।
- শুধু BST-তে: left subtree < node < right subtree, প্রতিটা node-এ।
Tree কেন O(log n) দেয় — যখন balanced¶
উপরের BST-তে 15 খোঁজা: 15 > 8 → ডানে যাও (পুরো বাঁ অর্ধেক — 3, 1, 6 — না তাকিয়েই বাদ)। 15 > 10 → ডানে। 15 vs 14 → not found। ছয়টি node-এর মধ্যে তিনটির সঙ্গে তুলনা করেই অনুসন্ধান শেষ।
একটি perfect binary tree-তে প্রতিটি level সম্পূর্ণ ভরা থাকে; তাই প্রতি level-এ node-এর সংখ্যা দ্বিগুণ হয়। শুধু full binary tree বললে এই শর্ত নিশ্চিত হয় না:
level 0: 1 node
level 1: 2 nodes
level 2: 4 nodes
level 3: 8 nodes
4 levels: 1 + 2 + 4 + 8 = 15 nodes
h + 1 filled levels: 2^(h+1) - 1 nodes
20 filled levels: 2^20 - 1 = 1,048,575 nodes
Search প্রতি level-এ একটা node হাঁটে, তাই balanced BST উত্তর দেয় O(log n)-এ — binary search, structure-এর রূপ নিয়ে, কিন্তু সাথে O(log n) insert আর delete-ও (sorted array সেটা দিতে পারে না)।
ফাঁকটা: balance ফ্রি না। একটা naive BST-তে 1, 2, 3, 4, 5 ক্রম অনুযায়ী insert করো:
1
\
2
\
3 ← a chain. Height n-1. Every operation O(n).
\ A "tree" cosplaying as a linked list.
4
Self-balancing tree (AVL, Red-Black — পরের topic) node rotate করে height-কে যেকোনো insertion order-এ O(log n) রাখে। এই folder-এর জন্য শুধু জানো: BST-র complexity বলে "O(h)", আর h-এর range log n (balanced) থেকে n (chain)।
কখন tree ব্যবহার করবে¶
- Data সত্যিকারের hierarchical: file system, org chart, parse করা document, game state।
- Sorted-order operation দরকার সাথে fast update-ও: range query, predecessor/successor, k-th smallest (BST এখানে জ্বলে; hash map order পারেই না)।
- Divide-by-structure recursion problem-এ খাপ খায় (expression evaluation, decision tree)।
কখন tree ব্যবহার করবে না¶
- শুধু exact-key lookup, কোনো ordering লাগে না → ../05-hashing/ সহজ আর average-এ দ্রুত।
- Data সমতল আর index দিয়ে address করা → array।
- শুধু বারবার min বা max দরকার → heap একটা হালকা, array-backed tree।
- Time pressure-এ Python-এ হাতে balanced BST বানাতে যাচ্ছ →
sortedcontainer ব্যবহার করো বা নতুন করে ভাবো; interview-তে হাতে-বানানো balancing-এর দাম প্রায় কখনোই ওঠে না।
Complexity table¶
| Operation | Balanced BST | Degenerate BST (chain) | Any binary tree |
|---|---|---|---|
| Search | O(log n) | O(n) | O(n) (কাজে লাগানোর মতো order নেই) |
| Insert | O(log n) | O(n) | — |
| Delete | O(log n) | O(n) | — |
| Min / Max | O(log n) | O(n) | O(n) |
| Full traversal | O(n) | O(n) | O(n) |
| Space | O(n) | O(n) | O(n) |
| Recursion stack | O(log n) | O(n) | O(height) |
Dry run সহ ছোট্ট snippet¶
1. Height — tree recursion-এর আদিরূপ¶
def height(node):
if node is None: # empty tree: height -1 by convention
return -1
return 1 + max(height(node.left), height(node.right))
উপরের 8/3/10 tree-তে dry run: height(1)=1+max(-1,-1)=0, height(6)=0 → height(3)=1+max(0,0)=1; height(14)=0 → height(10)=1+max(-1,0)=1; height(8)=1+max(1,1)=2। উত্তরগুলো হুবহু factorial-এর unwind-এর মতো বুদবুদ হয়ে উপরে ওঠে।
2. Node গোনা¶
Dry run, 3-এর subtree: count(1)=1, count(6)=1 → count(3)=1+1+1=3। বাক্যের মতো পড়ো: "আমি, plus আমার বাঁয়ের সবাই, plus আমার ডানের সবাই।"
3. BST search — প্রতি step-এ tree-র অর্ধেক হাওয়া¶
def bst_search(node, target):
if node is None or node.val == target:
return node
if target < node.val:
return bst_search(node.left, target)
return bst_search(node.right, target)
Dry run, target 6: 8-এ, 6 < 8 → বাঁয়ে (10-এর পুরো subtree ছোঁয়াই হলো না); 3-এ, 6 > 3 → ডানে; 6-এ → পাওয়া গেছে। ছয়টা node-এর মধ্যে তিনটা visit।
এক বাক্যের সারমর্ম¶
Tree হলো self-similar nesting — প্রতিটা node তার নিজের ছোট tree-র root — তাই প্রতিটা tree algorithm-এর recipe: None সামলাও, এই node-এর ছোট কাজটা করো, আর left আর right-এর জন্য leap of faith নাও।
পরের file: visual-explanation.md — একটা tree, চারটা traversal walk, প্রতিটা চাল ধরে ধরে আঁকা।