[C++] Coda di priorità attraverso RedBlack tree

[Peppyno]

Salve a tutti, mi trovo alle prese cn questo progetto per un esame universitario.
Ho implementato gia la struttura dati redblack tree. Adesso dovrei aggiungere le funzioni inerenti alla coda di priorità

Extractmax
Insert
Maximum
Increase-key

Il mio problema é ke nn trovo i rispettivi algoritmi da nessuna parte, manco sul libro o slide.
Se qualcuno puo darmi un consiglio ve ne sarei veramente grato.
Grazie mille!

[misterx]

prova a vedere queste implementazioni http://www.algoteam.di.unimi.it/impl...ici/rbtree.txt

[Peppyno]

Grazie, le terrò presenti per una correzione alle funzioni rbtree, pero qll per la coda di priorità non ci sono.

[MItaly]

Una coda di priorità è una struttura dati astratta, che si costruisce su altre strutture dati concrete.
Se vuoi puoi tranquillamente basare la coda di priorità sull'RB tree (usando il valore di ciascun elemento come chiave), le operazioni si mappano in maniera ovvia:

• maximum => ultimo elemento dell'RB tree (prendi sempre il ramo destro finché non arrivi ad una foglia);
• extractmax => togli l'ultimo elemento dell'RB tree e ribilanci;
• insert => normale inserimento in RB tree;
• increase-key => trovi l'elemento dall'albero e lo reinserisci con la chiave aggiornata.

Tutte queste operazioni sono O(log n).

Spesso comunque una priority queue viene implementata come un heap di qualche genere, che in genere fornisce prestazioni asintotiche migliori per una o più delle operazioni che hai citato (vedi qui).

[Peppyno]

Grazie mille, scusa se nn ho risp subito ma in effetti, ragionandoci un po e vedendo le regole di un albero redblack, ci sono arrivato anke io alle conclusioni cosi logiche xD.

[MItaly]