Ho problemi e apprezzerei molto il tuo aiuto, specialmente con pair-diff (S, d)
Sto cercando di implementare una struttura dati S in determinati momenti:
- Inserisci (S, k) - inserendo k in S O (logn)
- Elimina (S, x) - cancellando x da S - O (logn)
- pair-diff (S, d) - trovare due elementi in S in modo che la differenza delle loro chiavi sia esattamente d (se esiste) - O (n)
- Sum (s, k) - restituisce tutte le chiavi in S il cui valore non è maggiore di k - O (logn)
- OLD (S, m) - restituisce la chiave dell'elemento più vecchio m in S - O (logn).
per mantenere la struttura dei dati nei tempi previsti, ho pensato di utilizzare un albero rosso-nero. l'inserimento, la rimozione e il bilanciamento sono O (logn). tuttavia, la ricerca è anche O (logn). non sono davvero sicuro di come implementare pair-diff e sum usando le informazioni fornite. apprezzerebbe davvero il tuo aiuto.
pensava anche di usare un albero avl, ma non riusciva a pensare a un modo per farlo anche in determinati momenti.
spero davvero di imparare come farlo in questo modo