Topic 08 · Binary Search Tree

BST Deletion — তিনটা Case

পুরো সিলেবাসের সবচেয়ে বেশি নম্বর কাটা যাওয়া টপিক। Delete করার সময় গাছটা যেন BST-ই থেকে যায় — সেটাই আসল চ্যালেঞ্জ। মাত্র তিনটা case, কিন্তু তৃতীয়টাই সব।

Exam Chance ≈ 95% ★★★ সময় ≈ ১৫ মিনিট সবচেয়ে বেশি ভুল হয় এখানে
এই পাতায় যা আছে
  1. 01প্রশ্ন
  2. 02Prerequisite Concepts
  3. 03Exam Definition (English)
  4. 04Concept Explanation
  5. 05Algorithm (English)
  6. 06তিনটা Case — ধাপে ধাপে
  7. 07শুরুর গাছ
  8. 08সমাধান — চারটা Delete
  9. 09Final Exam Answer
  10. 10Common Mistakes
  11. 11Viva Questions
  12. 12Practice Questions

১. প্রশ্ন (Question)

EXAM QUESTION
45, 25, 65, 15, 30, 55, 75, 20, 35 দিয়ে তৈরি BST থেকে নিচের node গুলো ক্রমানুসারে delete করো এবং প্রতিটি ধাপে গাছটা আঁকো:

(a) 35   (b) 15   (c) 25   (d) 45 (root)

প্রতিটা ক্ষেত্রে কোন case প্রযোজ্য তা উল্লেখ করো।

২. Prerequisite Concepts (আগে যা জানা দরকার)

২.১ Inorder Successor — সবচেয়ে গুরুত্বপূর্ণ ধারণা

কোনো node এর Inorder Successor হলো inorder traversal এ তার ঠিক পরের value — অর্থাৎ তার চেয়ে বড় value গুলোর মধ্যে সবচেয়ে ছোটটা।

খুঁজবে কীভাবে (দুই children থাকলে):
১। ওই node এর ডান child এ যাও (একবার, ডানে)
২। তারপর যতদূর সম্ভব বামে নামতে থাকো
৩। যেখানে আর বাম child নেই — সেটাই successor

কেন দরকার: দুইটা child ওয়ালা node delete করার পুরো নিয়মটাই এর উপর দাঁড়ানো। এটা না বুঝলে Case 3 পারা যাবে না।

২.২ Inorder Predecessor (বিকল্প পদ্ধতি)

Inorder Predecessor = inorder এ ঠিক আগের value = তার চেয়ে ছোটদের মধ্যে সবচেয়ে বড়টা। খুঁজবে: একবার বামে যাও, তারপর যতদূর সম্ভব ডানে নামো।

কেন দরকার: Case 3 এ successor বা predecessor — যেকোনো একটা ব্যবহার করা যায়, দুইটাই সঠিক। তবে খাতায় লিখে দিতে হবে তুমি কোনটা ব্যবহার করছ, আর পুরো প্রশ্নে একই নিয়মে থাকতে হবে।

২.৩ Delete করার পরও BST property টিকে থাকতে হবে

Node সরিয়ে দিলেই কাজ শেষ নয় — যে জায়গাটা খালি হলো, সেখানে এমন কাউকে বসাতে হবে যে "বামের সবার চেয়ে বড়, ডানের সবার চেয়ে ছোট" — এই শর্ত রক্ষা করে।

কেন successor ঠিক এই কাজটা করে: successor হলো ডান subtree এর সবচেয়ে ছোট value। তাই সে ডান subtree এর সবার চেয়ে ছোট ✓ আর বাম subtree এর সবার চেয়ে বড় (কারণ সে ডান দিকেই ছিল) ✓ — ঠিক যতটুকু দরকার, ততটুকুই।

২.৪ Successor এর সবসময় বাম child থাকে না

Successor খুঁজতে গিয়ে যতদূর বামে যাওয়া যায় ততদূর গেছি — তাই তার আর বাম child থাকতেই পারে না। কিন্তু ডান child থাকতে পারে।

কেন দরকার: Successor কে উপরে তুলে আনার পর তার পুরোনো জায়গা থেকে তাকে মুছতে হয় — তখন সেটা হয় Case 1 (leaf) নয়তো Case 2 (এক child)। কখনোই Case 3 হবে না। এই কারণেই delete এর recursion আটকে যায় না।

৩. Exam Definition (English)

BST Deletion: Deleting a node from a binary search tree must preserve the search-tree property. Three cases arise:

Case 1 — Leaf node (no child): the node is simply removed and its parent's link is set to NULL.

Case 2 — Node with exactly one child: the node is removed and its single child is attached directly to the node's parent, replacing it.

Case 3 — Node with two children: the node's key is replaced by the key of its inorder successor — the minimum key of its right subtree (alternatively, the inorder predecessor, the maximum key of its left subtree). The successor node is then deleted from the right subtree, which necessarily falls under Case 1 or Case 2.

Complexity: O(h), where h is the height of the tree.

৪. Concept Explanation (বাংলায়)

ভাবো একটা অফিসে সবাই নির্দিষ্ট নিয়মে বসে আছে। কেউ চাকরি ছেড়ে দিলে তিন রকম পরিস্থিতি হয় —

১। সে সবার নিচের কর্মী (leaf): চলে গেল, চেয়ারটা খালি। কেউ প্রভাবিত হলো না। সবচেয়ে সহজ।

২। তার নিচে একজন মাত্র লোক (এক child): ওই একজনই তার চেয়ারে উঠে বসবে, সাথে নিজের পুরো টিম নিয়ে। কোনো নিয়ম ভাঙে না, কারণ ওই দিকের সবাই একই সম্পর্কে ছিল।

৩। তার নিচে দুইটা টিম (দুই child): এখানেই আসল সমস্যা — কোন টিমকে উপরে তুলবে? একটাকে তুললে অন্যটার সাথে সম্পর্ক ভেঙে যাবে। তাই কাউকে টিম সমেত তোলা হয় না — বরং এমন একজনকে খুঁজে আনা হয় যে ঠিক এই দুই টিমের মাঝখানের মানুষ, অর্থাৎ inorder successor। তাকে শুধু value হিসেবে উপরে বসিয়ে দেওয়া হয়, আর তার পুরোনো জায়গা থেকে তাকে মুছে ফেলা হয়।

মূল কথা: Case 3 এ আমরা node টা সরাই না — শুধু value বদলাই, তারপর নিচে গিয়ে successor কে delete করি। আর সেই delete টা সবসময় সহজ Case 1 বা 2 হয়।

৫. Algorithm (English)

BST_DELETE(root, key)
    if root == NULL then
        return NULL                       // key not found

    if key < root.key then
        root.left  = BST_DELETE(root.left,  key)
    else if key > root.key then
        root.right = BST_DELETE(root.right, key)
    else                                  // found the node
        // ---- Case 1 & 2 : zero or one child ----
        if root.left == NULL then
            return root.right             // NULL if leaf, else the child
        if root.right == NULL then
            return root.left

        // ---- Case 3 : two children ----
        succ = FIND_MIN(root.right)       // inorder successor
        root.key = succ.key               // copy the value up
        root.right = BST_DELETE(root.right, succ.key)   // delete it below

    return root


FIND_MIN(node)
    while node.left != NULL do
        node = node.left
    return node

৬. তিনটা Case — ধাপে ধাপে

Case 1 — Leaf node (কোনো child নেই)
সরাসরি মুছে দাও, parent এর ওই দিকের link কে NULL করো।
30 30 / \ ⇒ / 20 40 20 (40 delete)
কেন এত সহজ: leaf এর নিচে কেউ নেই, তাই কারো সাথে সম্পর্ক ভাঙার প্রশ্নই আসে না।
Case 2 — ঠিক একটা child
Node টা মুছে দাও, তার একমাত্র child কে parent এর সাথে সরাসরি জুড়ে দাও।
30 30 / \ ⇒ / \ 20 40 20 50 (40 delete, তার child 50 উঠে এলো) \ 50
কেন ঠিক থাকে: child টা তার পুরো subtree নিয়ে উঠে আসে। 40 যে দিকে ছিল (30 এর ডানে, অর্থাৎ 30 এর চেয়ে বড়), 50 ও সেই একই দিকেই ছিল — তাই সম্পর্ক অটুট।
Case 3 — দুইটা child (আসল খেলা)
  1. Node এর inorder successor খোঁজো: একবার ডানে যাও, তারপর যতদূর সম্ভব বামে নামো।
  2. Successor এর value টা কপি করে delete করার node এ বসাও (node টা সরাচ্ছি না, শুধু value বদলাচ্ছি)।
  3. এখন ডান subtree থেকে successor কে delete করো — এটা সবসময় Case 1 বা Case 2 হবে।
50 60 60 / \ / \ / \ 30 70 ⇒ 30 70 ⇒ 30 70 / \ / \ \ 60 80 60 80 80 ধাপ ১: 50 এর ধাপ ২: 60 কে ধাপ ৩: নিচের successor = 60 উপরে কপি করলাম পুরোনো 60 মুছলাম
কেন successor: সে ডান subtree এর সবচেয়ে ছোট — তাই ডানের সবার চেয়ে ছোট ✓ এবং বাম subtree এর সবার চেয়ে বড় ✓। ঠিক এই দুইটা শর্তই তো root এর জায়গায় বসতে লাগে।

৭. শুরুর গাছ

45 / \ 25 65 / \ / \ 15 30 55 75 \ \ 20 35
Inorder = 15, 20, 25, 30, 35, 45, 55, 65, 75 (sorted ✓)

৮. সমাধান — চারটা Delete

(a) Delete 35 — Case 1 (leaf)

খোঁজা: 35 < 45 → বাম (25) · 35 > 25 → ডান (30) · 35 > 30 → ডান, পেয়ে গেলাম।
যাচাই: 35 এর কোনো child নেই → Case 1। শুধু মুছে দাও।

45 / \ 25 65 / \ / \ 15 30 55 75 \ 20

Inorder = 15, 20, 25, 30, 45, 55, 65, 75 ✓

(b) Delete 15 — Case 2 (এক child)

খোঁজা: 15 < 45 → 25 · 15 < 25 → 15 পেলাম।
যাচাই: 15 এর বাম child নেই, ডান child আছে (20) → Case 2। তাই 20 উঠে এসে 15 এর জায়গায় বসবে, অর্থাৎ 25 এর left child হবে।

45 / \ 25 65 / \ / \ 20 30 55 75

Inorder = 20, 25, 30, 45, 55, 65, 75 ✓

(c) Delete 25 — Case 3 (দুই children)

যাচাই: 25 এর দুইটা child আছে (20 আর 30) → Case 3।

ধাপ ১ — Successor খোঁজা: 25 এর ডান child → 30 30 এর বাম child আছে? → নেই ⇒ Inorder Successor = 30 ধাপ ২ — 30 এর value 25 এর জায়গায় কপি করো ধাপ ৩ — ডান subtree থেকে পুরোনো 30 কে delete করো 30 এখন leaf ⇒ Case 1 ⇒ সরাসরি মুছে দাও
45 / \ 30 65 / / \ 20 55 75

Inorder = 20, 30, 45, 55, 65, 75 ✓

(d) Delete 45 — Case 3, তাও root

যাচাই: root 45 এর দুইটা child আছে (30 আর 65) → Case 3। Root বলে আলাদা কোনো নিয়ম নেই — একই তিন ধাপ।

ধাপ ১ — Successor খোঁজা: 45 এর ডান child → 65 65 এর বাম child আছে? → 55 আছে, নামো 55 এর বাম child আছে? → নেই, থামো ⇒ Inorder Successor = 55 ধাপ ২ — 55 কে root এ কপি করো ধাপ ৩ — ডান subtree থেকে পুরোনো 55 কে delete করো 55 এখন leaf ⇒ Case 1
55 / \ 30 65 / \ 20 75

Inorder = 20, 30, 55, 65, 75 ✓

বিকল্প উত্তরও সঠিক: ধাপ (d) তে successor এর বদলে predecessor নিলে — 45 এর বাম subtree এর সবচেয়ে বড় = 30 — গাছটা হতো:
30 / \ 20 65 / \ 55 75
Inorder = 20, 30, 55, 65, 75 ✓ — এটাও সম্পূর্ণ বৈধ। খাতায় লিখে দাও কোন পদ্ধতি ব্যবহার করেছ।

বোনাস — Successor এর যখন ডান child থাকে

মূল গাছ থেকে (কিছু delete করার আগে) সরাসরি 25 delete করলে কী হতো? 25 এর successor = 30, কিন্তু তখন 30 এর একটা ডান child (35) ছিল। তাই ধাপ ৩ এ 30 কে মুছতে গিয়ে Case 2 লাগত — 35 উঠে এসে 30 এর জায়গা নিত:
45 45 / \ / \ 25 65 ⇒ 30 65 / \ / \ / \ / \ 15 30 55 75 15 35 55 75 \ \ \ 20 35 20
Inorder = 15, 20, 30, 35, 45, 55, 65, 75 ✓ — এই ধরনের কেসই পরীক্ষায় বেশি দেওয়া হয়, কারণ এখানেই বোঝা যায় কে সত্যিই নিয়মটা বুঝেছে।

৯. Final Exam Answer (English)

Deletion summary Delete 35 → Case 1 (leaf) : removed directly Delete 15 → Case 2 (one child) : child 20 replaced it Delete 25 → Case 3 (two children) : successor 30 moved up Delete 45 → Case 3 (root, 2 children): successor 55 moved up Final tree Final inorder 55 20, 30, 55, 65, 75 (sorted ✓) / \ 30 65 / \ 20 75 Deletion cost O(h) · The BST property is preserved after every step

১০. Common Mistakes

১১. Viva Questions

Q: BST deletion এর তিনটা case কী কী? প্রতিটার উদাহরণ দাও।
Q: Inorder successor কী এবং কীভাবে খুঁজবে?
Q: Case 3 এ successor ব্যবহার করা হয় কেন? অন্য কোনো node দিয়ে কেন হয় না?
Q: Inorder successor এর কি বাম child থাকতে পারে? কেন নয়?
Q: Successor এর বদলে predecessor ব্যবহার করলে কি উত্তর ভুল হবে?
Q: Deletion এর time complexity কত এবং কেন?
Q: Root delete করলে কি আলাদা কোনো নিয়ম লাগে?
Q: Delete করার পর গাছটা এখনো BST আছে কিনা কীভাবে যাচাই করবে? (উত্তর: inorder বের করে sorted কিনা দেখে)

১২. Practice Questions

  1. 50, 30, 70, 20, 40, 60, 80 এর BST থেকে 20 delete করো। কোন case?
    উত্তর দেখাও
    20 একটা leaf → Case 1। সরাসরি মুছে দাও। বাকি গাছ: 50 (বামে 30 যার শুধু ডান child 40; ডানে 70 with 60, 80)।
    Inorder = 30, 40, 50, 60, 70, 80 ✓
  2. একই গাছ থেকে 30 delete করো (child 20 ও 40)।
    উত্তর দেখাও
    Case 3। Successor = ডান subtree {40} এর সবচেয়ে ছোট = 40। 40 কে উপরে কপি করে নিচের 40 (leaf) মুছে দাও।
    ফলাফল: 50 এর বামে 40, তার বামে 20। Inorder = 20, 40, 50, 60, 70, 80 ✓
  3. একই গাছ থেকে root 50 delete করো — successor ও predecessor দুই পদ্ধতিতেই দেখাও।
    উত্তর দেখাও
    Successor = ডান subtree এর সবচেয়ে ছোট = 60 → নতুন root 60, নিচের 60 (leaf) মুছে যায়।
    Predecessor = বাম subtree এর সবচেয়ে বড় = 40 → নতুন root 40, নিচের 40 মুছে যায়।
    দুইটাই বৈধ BST, দুই ক্ষেত্রেই inorder = 20, 30, 40, 60, 70, 80 ✓
  4. 60, 25, 80, 15, 45, 70, 90, 35, 55 এর BST থেকে ক্রমে 15, 45, 60 delete করো।
    উত্তর দেখাও
    15 leaf → Case 1।
    45 এর child 35 ও 55 → Case 3; successor = 55 → 55 উপরে, নিচের 55 (leaf) মুছে যায়। এখন 25 এর ডান child 55, তার বাম child 35।
    60 (root) এর child 25 ও 80 → Case 3; successor = ডানের সবচেয়ে ছোট = 70 → নতুন root 70, নিচের 70 (leaf) মুছে যায়।
    চূড়ান্ত inorder = 25, 35, 55, 70, 80, 90 ✓
  5. Delete করার পর গাছের height বাড়তে পারে কি? ব্যাখ্যা করো।
    উত্তর দেখাও
    না — delete করলে node কমে, তাই কোনো পথ লম্বা হয় না। Height হয় একই থাকে, নয়তো কমে।
  6. একটা BST তে শুধু ডান দিকে হেলে থাকা (right-skewed) গাছ থেকে root delete করলে কী হয়?
    উত্তর দেখাও
    Root এর বাম child নেই → Case 2। তার ডান child নতুন root হয়ে যায়, গাছ এক ধাপ ছোট হয়।
  7. BST_DELETE এর pseudocode লেখো এবং Case 3 এ recursion কেন অসীমভাবে চলে না ব্যাখ্যা করো।
    উত্তর দেখাও
    কারণ successor এর কখনো বাম child থাকে না, তাই তাকে delete করা সবসময় Case 1 বা Case 2 — recursion আর গভীরে যায় না।
  8. একটা গাছ থেকে সব node delete করার সবচেয়ে ভালো ক্রম কী হবে যদি গাছটা balanced রাখতে চাও?
← আগের০৭. BST — Creation ও Insertion পরের →০৯. Traversal থেকে BST বানানো
CSE 123 · Data Structures — পড়ার খাতা  ·  সব টপিক  ·  Cheat Sheet
←☰→