Trees — লাইব্রেরির ক্যাটালগ নতুন করে সাজান¶
একটি লাইব্রেরিতে নতুন বইয়ের ID আসার ক্রমে BST-তে ঢোকানো হয়েছে। ID-গুলো ক্রমবর্ধমান হলে tree একটি লম্বা শিকলের মতো হয়ে যায়। আপনার কাজ হলো সেই tree থেকে তথ্য উদ্ধার করে একটি balanced BST বানানো, তারপর পাঠকের কয়েকটি প্রশ্নের উত্তর দেওয়া।
Microsoft কোর্সের সংযোগ: Module 3-এর tree, traversal ও balanced tree ধারণা। এখানে একবার tree পুনর্গঠন করবেন; AVL/Red–Black tree-এর rotation বাস্তবায়ন এই lab-এর অংশ নয়।
১. আগে যা পড়বেন ও করবেন¶
| ক্রম | পড়া / অনুশীলন | নিজে কী ব্যাখ্যা করতে পারবেন |
|---|---|---|
| ১ | Tree-এর ধারণা, চিত্র | Root, child, height ও BST ordering |
| ২ | Traversal patterns, Inorder | Inorder কেন ছোট থেকে বড় ID দেয় |
| ৩ | Level order, Maximum depth | Queue-এর এক round কেন একটি level |
| ৪ | Validate BST, Balanced tree | Local parent-child তুলনা একা যথেষ্ট নয় কেন |
| ৫ | K-th smallest, LCA of BST | Ordering দিয়ে কোন subtree বাদ দেবেন |
প্রথমে ২ ও ৩ নম্বর সারির problem নিজে করুন। ৪ ও ৫ নম্বরের ধারণা নিয়ে নিচের lab শুরু করুন; আটকে গেলে সংশ্লিষ্ট explanation-এ ফিরে যান।
২. সুনির্দিষ্ট সমস্যা¶
catalogue_report(book_ids, low, high, k, pair) লিখুন।
book_ids-এর ID একই ক্রমে একটি বাস্তব node-ভিত্তিক BST-তে insert করুন। সব ID আলাদা।- পুরোনো tree-এর height মাপুন; height হলো root থেকে deepest leaf পর্যন্ত node-এর সংখ্যা।
- Inorder traversal থেকে sorted ID নিন। প্রতি অর্ধখোলা range
[left, right)-এর(left + right) // 2index-কে root করে নতুন balanced BST বানান। জোড় সংখ্যক ID হলে এটি ডানদিকের মাঝের ID বেছে নেয়। - নতুন tree থেকে inclusive range
[low, high]-এর বই, ১-ভিত্তিকk-তম ছোট ID এবংpair-এর দুই ID-এর LCA দিন। - Sorted ID, আগে/পরের height ও নতুন tree-এর level-গুলোও রিপোর্টে দিন। সব query নতুন tree-তে হবে।
সীমা: 1 ≤ n ≤ 2,000, ID ও query bound পূর্ণসংখ্যা, 1 ≤ k ≤ n, low ≤ high; pair-এর দুই ID অবশ্যই বইয়ের তালিকায় আছে। একই ID দুইবার query করা যায়। Duplicate বই, ফাঁকা তালিকা বা ভুল query-তে ValueError দিন।
এটি Python function-এর input/output সমস্যা; stdin parser বা database লাগবে না। মূল book_ids বদলাবেন না।
{
"ordered": [10, 20, 30, 40, 50],
"height_before": 5,
"height_after": 3,
"levels": [[30], [20, 50], [10, 40]],
"in_range": [20, 30, 40],
"kth": 30,
"lca": 20,
}
পুরোনো tree-তে 10 → 20 → 30 → 40 → 50 ডানদিকে নেমেছে। নতুন tree:
flowchart TD
root["30"] --> left["20"]
root --> right["50"]
left --> a["10"]
right --> b["40"]10 ও 20-এর সাধারণ ancestor 20 নিজেই। নতুন tree-এর তিনটি level আছে, তাই height 3।
৩. ধাপে ধাপে নির্মাণ¶
ধাপ A — Node ও insertion¶
Node(key, left, right) এবং insert(root, key) লিখুন। প্রথম ID root হবে। পরের ID ছোট হলে বামে, বড় হলে ডানে হাঁটুন; প্রথম খালি child-এ নতুন node বসান।
Invariant: প্রতিটি node-এর সম্পূর্ণ বাম subtree ছোট, সম্পূর্ণ ডান subtree বড়। Duplicate পেলে থামুন। Hint: পুরোনো tree খুব গভীর হতে পারে; insertion-এ loop ব্যবহার করলে Python recursion limit এড়ানো যায়।
Checkpoint: [10, 20, 30] insert করার পরে root.right.right.key == 30; height 3।
ধাপ B — পুরোনো tree থেকে তথ্য উদ্ধার¶
একটি explicit stack দিয়ে inorder এবং queue দিয়ে level order লিখুন। Inorder ফলই পরের ধাপের input; এই lab-এ sorted(book_ids) দিয়ে tree traversal এড়াবেন না।
Invariant: stack-এ থাকা node-এর বামদিকের কাজ শেষ হলে তবেই node visit হবে। Queue-এর বর্তমান দৈর্ঘ্য ধরে এক round চালালে নতুন child-গুলো পরের level-এ থাকবে।
Checkpoint: example-এর inorder [10, 20, 30, 40, 50], পুরোনো level count 5।
ধাপ C — মাঝের ID দিয়ে tree পুনর্গঠন¶
build(left, right)-এ খালি range হলে None; অন্যথায় middle-এ একটি node বানিয়ে দুই অর্ধে recursion করুন। Slice করে নতুন array বানানোর দরকার নেই।
Invariant: recursion-এর প্রতিটি range sorted এবং তার বাইরের ID ওই subtree-তে ঢুকবে না। অর্ধেক অর্ধেক ভাগ হওয়ায় height ছোট হয়।
Checkpoint: [10, 20, 30, 40, 50] থেকে root 30; তার right child 50, 50-এর left child 40।
ধাপ D — পাঠকের query ও চূড়ান্ত রিপোর্ট¶
Range query-তে key < low হলে বাম subtree বাদ দিন। kth-এর জন্য inorder visit গুনুন। LCA-তে দুই ID ছোট হলে বামে, দুইটি বড় হলে ডানে; দুই দিকে ভাগ হলে বর্তমান node-ই উত্তর।
Invariant: LCA খোঁজার সময় দুই target এখনও বর্তমান subtree-র মধ্যে আছে। Pair-এর সদস্য tree-তে আছে কি না আগে যাচাই করুন।
Checkpoint: example-এর range উত্তর তিনটি ID; kth=30, lca=20। সব ধাপের ফল একই report-এ মিলতে হবে।
৪. সমাধান বুঝে মিলিয়ে নিন¶
Reference solution-এর যুক্তি
পুরোনো tree সত্যিকারের insertion order ধরে, তাই তার height সমস্যাটির অবস্থা দেখায়। Iterative inorder একবার প্রতিটি node visit করে sorted sequence উদ্ধার করে। সেই sequence-এর midpoint দিয়ে node তৈরি করলে প্রতিটি subtree-র আকার কাছাকাছি থাকে।
Query-গুলোর উত্তর নতুন node-গুলোতে হাঁটেই পাওয়া হয়। শুধু sorted list থেকে সব উত্তর দিলে height, child relation ও LCA শেখা হতো না। LCA-র ক্ষেত্রে ordering দুই target-এর সম্ভাব্য subtree একসঙ্গে ছোট করতে দেয়।
সম্পূর্ণ Python solution এবং unit test। আগে নিজে ধাপ A–D লিখে তারপর তুলনা করুন।
৫. Unit test ও edge case¶
Repository root থেকে চালান। Download করলে দুই ফাইল practice/ folder-এ রাখুন।
৮টি test method-এ worked example, এক বই, range-এর বাইরে query, duplicate/invalid input, node-ভিত্তিক BST ও balance invariant, ১,২০০ node-এর skewed tree এবং ৮০টি seeded random query যাচাই হয়। Random query-র oracle হিসেবে আলাদা sorted-list filter ব্যবহার করা হয়েছে।
নিজে আরও ভাবুন: low == high, k == n, দুই target একই node এবং ancestor নিজেই target হলে কী হবে।
৬. কী শিখলেন, কী বাকি¶
| এই lab-এ ব্যবহার | কোথায় | আলাদা করে অনুশীলন দরকার |
|---|---|---|
| BST insertion, ordering | A | Deletion-এর তিনটি case |
| DFS inorder, BFS level order | B | Preorder/postorder construction |
| Balanced shape ও recursion | C | AVL/Red–Black rotation, online balancing |
| Range pruning, k-th, LCA | D | Arbitrary binary-tree LCA, subtree matching |
| Tree-এর গঠন ও height | পুরো report | Diameter, maximum path sum, serialization |
Complexity: সাধারণ BST insertion-এর worst case O(n²); এটি ইচ্ছাকৃত, পুরোনো skewed tree তৈরি করতে হবে। Inorder, rebuild ও level report O(n)। Rebuilt tree-তে range query O(log n + r), k-th traversal O(log n + k), LCA O(log n); r হলো মিলে যাওয়া বইয়ের সংখ্যা। মোট node/report storage O(n)।
শেষে সব tree problem-এ ফিরে বাকি pattern আলাদা করে করুন। একটি capstone সেই অনুশীলনের বিকল্প নয়।