implementazione della struttura dati che consiste in pair-diff (s, d)

0

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

    
posta BeginningMath 26.06.2018 - 17:50
fonte

0 risposte

Leggi altre domande sui tag