Çfarë është një pemë kërkimi binare (BST) dhe cilat janë kompleksitetet e operacioneve të tij?

Question

Accepted Answer

Një **pemë kërkimi binare** është një pemë binare me një ndryshim rendi: për çdo nyje, **të gjithë çelësat në nënpemën e majtë janë më të vegjël**, dhe **të gjithë çelësat në nënpemën e djathtë janë më të mëdhenj**. Kjo ju lejon të kërkoni duke përgjysmuar problemin në secilin hap.

## Ndryshimi i rendit

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

## Kërkimi dhe futja

```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
```

## Kompleksiteti

| Operacioni | I balancuar | Rasti më i keq (i degjeneruar) |
|---|---|---|
| kërkimi | O(log n) | O(n) |
| futja | O(log n) | O(n) |
| fshirja | O(log n) | O(n) |

Rasti **më i keq** ndodh kur çelësat futen në rendin e sortimit — pema degjenerojë në një listë të lidhur me lartësinë `n`.

## Kompromiste

- **Pikat e forta:** përshkim i renditur në O(n); mbështet pyetjet e vargut dhe pasardhës/paraardhës.
- **Pikat e dobëta:** nuk ka garanci balancimi në vetvete — duhet një variant AVL ose red-black për të mbetur O(log n).

## Pse ka rëndësi

BST-të ju japin të dhëna të renditura, dinamike me operacione logaritmike — paraardhësi konceptual i indekseve të bazave të të dhënave dhe hartave të renditura.

Problema e degjenerimit motivon **pemët vetë-balancuese**, një temë e rëndësishme ndjekëse në intervista.