Kas yra dvejetainis paieškos medis (BST) ir kokios yra jo operacijų sudėtingumų?

Question

Accepted Answer

**Dvejetainis paieškos medis** yra dvejetainis medis, turintis nusakymą apie tvarkymą: kiekvienam mazgui, **visi raktai jo kairiajame pomedyje yra mažesni**, o **visi raktai dešiniajame pomedyje yra didesni**. Tai leidžia paieškoti, perpus sumažinant problemą kiekviename žingsnyje.

## Kodėl tai svarbu

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

## Paieška ir įterpimas

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

## Sudėtingumas

| Operacija | Subalansuota | Blogiausias (suirustas) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

**Blogiausias atvejis** pasitaiko, kai raktai įterpiami surikiuota tvarka — medis susmulkėja į susietos sąrašo aukštį `n`.

## Kompromisai

- **Stiprybės:** surikiuotas peržiūrėjimas O(n); palaiko diapazoninės užklausos ir įpėdinio/pirmtako paieškos.
- **Silpnybės:** nėra balanso garantijos pačiam — reikia AVL arba raudonai-juodo varianto, kad liktų O(log n).

## Kodėl tai svarbu

BST suteikia surikiuotus, dinaminius duomenis su logaritminėmis operacijomis — duomenų bazės indeksų ir surikiuotų žemėlapių konceptualus protėvis.

Suirusimo problema motyvuoja **savęs balansuojančius medžius**, svarbią pokalbio temą.