# Rekapitulace ADT

**Přístup k datům pomocí indexů**

|                   | vybrání     | odebrání                     | přidání                      |
| ----------------- | ----------- | ---------------------------- | ---------------------------- |
| spojová struktura | $\Theta(n)$ | $\Theta(1)$ pokud byl vybrán | $\Theta(1)$ pokud byl vybrán |
| dynamické pole    | $\Theta(1)$ | $\Theta(n)$                  | $\Theta(n)$                  |

**Přístup k datům pomocí klíče**

|         | přidání           | odebrání          | vybrání           | vybrání maxima    | odebrání maxima   |
| ------- | ----------------- | ----------------- | ----------------- | ----------------- | ----------------- |
| Tabulka | $\Theta(1)$       | $\Theta(1)$       | $\Theta(1)$       | $\Theta(n)$       | $\Theta(n)$       |
| BST     | $\Theta(\log(n))$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ |
| Halda   | $\Theta(\log(n))$ | N/A               | N/A               | $\Theta(1)$       | $\Theta(\log(n))$ |