Ce este un arbore binar de căutare (BST) și care sunt complexitățile operațiilor acestuia?

Question

Accepted Answer

Un **arbore binar de căutare** este un arbore binar cu o invariantă de ordonare: pentru fiecare nod, **toate cheile din subarborele stâng sunt mai mici**, și **toate cheile din subarborele drept sunt mai mari**. Aceasta vă permite să căutați prin înjumătățirea problemei la fiecare pas.

## 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) |

**Cel mai rău caz** apare atunci când cheile sunt inserate în ordine sortată — arborele degenerează într-o listă legată de înălțime `n`.

## Trade-offs

- **Puncte forte:** traversare ordonată în O(n); suportă interogări de interval și successor/predecessor.
- **Puncte slabe:** nicio garanție de echilibrare de la sine — necesită o variantă AVL sau red-black pentru a rămâne O(log n).

## De ce este important

BST-urile vă oferă date ordonate și dinamice cu operații logaritmice — ancestrul conceptual al indexurilor de baze de date și al mapelor ordonate.

Problema degenerării motivează **self-balancing trees**, un subiect de continuare cheie în interviuri.