بائنری سرچ ٹری (BST) کیا ہے اور اس کی operations کی complexity کیا ہے؟

Question

Accepted Answer

**بائنری سرچ ٹری** ایک بائنری ٹری ہے جس میں ایک ordering invariant ہوتی ہے: ہر node کے لیے، **اس کے بائیں subtree میں تمام keys چھوٹی ہوتی ہیں**، اور **اس کے دائیں subtree میں تمام keys بڑی ہوتی ہیں**۔ یہ آپ کو ہر قدم پر مسئلہ کو آدھا کر کے سرچ کرنے دیتا ہے۔

## The invariant

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right at every node
```

## Search and insert

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # go one way
    return None

def insert(node, key):
    if node is None: return Node(key)
    if key < node.val: node.left  = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## Complexity

| Operation | Balanced | Worst (degenerate) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

**worst case** تب ہوتا ہے جب keys کو sorted order میں insert کیا جائے — ٹری height `n` کی linked list میں تبدیل ہو جاتی ہے۔

## Trade-offs

- **Strengths:** ordered traversal O(n) میں؛ range queries اور successor/predecessor کو سپورٹ کرتا ہے۔
- **Weaknesses:** اپنے آپ میں balance کی guarantee نہیں ہے — O(log n) میں رہنے کے لیے AVL یا red-black variant کی ضرورت ہے۔

## اہمیت

BSTs آپ کو sorted، dynamic data دیتے ہیں جس میں logarithmic operations ہوں — یہ database indexes اور ordered maps کا conceptual ancestor ہے۔

Degeneration کا مسئلہ **self-balancing trees** کی نے متاثر کیا، جو interviews میں ایک اہم follow-up topic ہے۔