Completare la seguente tabella indicando la complessità delle operazioni che si riferiscono a un dizionario di n elementi. Per l’operazione Successore si assuma di essere sull’elemento x a cui si applica l’operazione.
| Ricerca | Massimo | Successore | Minimo | Costruzione | |
|---|---|---|---|---|---|
| Albero binario di ricerca | O(h) | O(h) | O(h) | O(h) | O(n) |
| Min-Heap | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
Nota: in un albero binario bilanciato, h è l'altezza dell'albero, che è uguale a log(n) per n compreso tra n^(h-1)+1 e n^h