m-way-bst-ai.md

📌 Insertion & Deletion in an M-Way Search Tree (Intuitive Explanation)

Think of an M-way tree like a filing cabinet! 🗄️

• Each folder (node) holds multiple documents (keys).
• When a folder gets too full, we split it into new folders.
• When a folder has too few documents, we borrow or merge with others.

---

🌱 Insertion in an M-Way Search Tree

How do we insert values?

1. Find the correct place

   • Like a BST, move left for smaller and right for larger.
   • But now we have multiple middle sections.

2. Insert the value into the node

   • If there’s space, just place it in sorted order.
   • If the node is full, split it and push the middle value up.

---

🔹 Example: Inserting into a 3-Way Search Tree (M = 3, max 2 keys per node)

Step 1: Insert 10, 20, 30, 40, 50

• Insert 10 → 20 → 30, all fit in one node:

  [10, 20, 30]
  

• Insert 40
  • There’s space, so just place it:

  [10, 20, 30, 40]
  

• Insert 50
  • Now the node is full (4 values, but max allowed = 2).
  • We split the node:
    • Middle value 20 goes up.
    • The node splits into two.

     [20]
    /    \
  

[10] [30, 40, 50]

Step 2: Insert 25

• Go to the correct node (between 20 and 30).
• Insert 25 into [30, 40, 50] in sorted order.

     [20]
    /    \
 [10]  [25, 30, 40, 50]

• Again, the node is full! We split it:
  • 30 moves up.
  • Two child nodes remain: [25] and [40, 50].

     [20, 30]
    /    |    \
 [10]  [25]  [40, 50]

💡 Key Takeaways for Insertion:

• Insert the value in sorted order.
• If a node becomes too full, split it and push the middle value up.
• This keeps the tree balanced.

---

🔥 Deletion in an M-Way Search Tree

How do we delete values?

1. Find the value (like searching in a BST).
2. Delete it
   • If it's in a leaf node, just remove it.
   • If it's in an internal node, replace it with its predecessor (largest in left) or successor (smallest in right).
3. Fix underflow (if needed)
   • If a node has too few values, borrow from a sibling.
   • If borrowing isn’t possible, merge with a sibling.

---

🔹 Example: Deleting from a 3-Way Search Tree

Step 1: Start with this tree

     [20, 30]
    /    |    \
 [10]  [25]  [40, 50]

Case 1: Deleting 50 (Leaf Node, No Fixing Needed)

• Just remove it:

     [20, 30]
    /    |    \
 [10]  [25]  [40]

Case 2: Deleting 30 (Internal Node)

• 30 is not in a leaf.
• Find successor (40 in this case).
• Replace 30 with 40, then delete 40 from the child node.

     [20, 40]
    /    |    \
 [10]  [25]  []

• The right child now has too few keys.
• Merge it with 25, since it's the sibling.

     [20]
    /    \
 [10]   [25, 40]

---

💡 Key Takeaways for Deletion:

• If deleting from a leaf, just remove the value.
• If deleting from an internal node, replace it with a predecessor or successor.
• If a node has too few values, borrow or merge with a sibling.

---

🎯 Final Thoughts

• M-way trees keep things balanced by splitting and merging.
• Faster searches compared to BSTs due to fewer levels.
• Used in databases and file systems (like B-Trees in indexing).