Cad is crann cuardaigh dhénártha (BST) agus cad iad na castáchta oibríochta ?

Question

Accepted Answer

Is **crann cuardaigh dhénártha** ann crann dénártha le ionradh ordaithe : do gach nód, **tá na heochracha ar fad ina fhostrom clé níos lú**, agus **tá na heochracha ar fad ina fhostrom deis níos mó**. Tugann sé seo deis duit cuardach a dhéanamh trí an fhadhb a leathú ag gach céim.

## An ionradh

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

## Cuardach agus ionsá

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

## Castacht

| Oibríocht | Cothromaithe | Dochar (truaillithe) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

Tarlaíonn an **dochar is measa** nuair a insítear eochracha in ord sórtáilte — déantar an crann truaillithí i liosta fófhaighte ar airde `n`.

## Socrúchán

- **Neart :** taisteal ordaithe in O(n) ; tacaíonn le ceistanna raon agus rannpháirtí/réamhtheachtaí.
- **Lag :** gan ráthaíochtaí cothromaíochta ann féin — bíonn gá do athrú AVL nó red-black fanacht O(log n).

## Cén fáth a bhíonn sé tábhachtach

Tugann BST sonraí sórtáilte, dinimiciúla duit le hoibríochtaí logartamúla — an réamhtheachtaí coincheapúil d'innéacsanna bunachair sonraí agus mapanna ordaithe.

Mothaíonn an fhadhb truaillithe **crann féin-chothromaitheach**, ábhar leanúnach ríthábhachtach in agallamh.