Albero di rango in C++

Question

Abbiamo bisogno di ADT con funzioni di ricerca e classificazione. Cioè, oltre all'interfaccia della mappa STL, è richiesta una funzione 'int get_rank (chiave)'.

L'implementazione standard di tale funzione richiede il supporto e l'aggiornamento di un campo intero in più in ogni nodo dell'albero di ricerca auto bilanciato (ad esempio, nell'albero nero-rosso, utilizzato nella mappa/insieme STL). Ma a quanto pare, la mappa/set STL non lo fa.

Stiamo cercando una soluzione basata su contenitori standard (STL, Boost) con la migliore complessità temporale possibile: trovare/aggiungere/cancellare un elemento prendere O (log n) (come in STL map/set), calcolando il rango con una chiave prende anche O (log n).

Per il grado di un elemento, si intende la posizione dell'elemento nella sequenza ordinata di tutti gli elementi della mappa/set.

Esempio. set = {0, 4, 6, 7, 8} rank (0) = 1, rank (4) = 2, rank (6) = 3, rank (7) = 4, rank (8) = 5.

A nostro parere, in base ai vincoli di complessità temporale sopra, il problema non può essere risolto da una combinazione di due mappe un ordinamento per chiave e altro ordinamento per grado.

Grazie.

Answer 1

Suppongo che per rank si intenda effettivamente la distanza dalla radice, poiché se potesse essere memorizzata in modo contiguo con il valore non si dovrebbe andare a tale lunghezza.

Penso che si potrebbe farlo "dall'esterno", poiché in questo caso il rango può essere estrapolata dal numero di volte che il predicato di confronto viene utilizzato ...

namespace detail 
{ 
    template <class Comparator> 
    class CounterComparator: Comparator 
    { 
    public: 
    CounterComparator(size_t& counter): 
     Comparator(), mCounter(&counter) {} 
    CounterComparator(Comparator comp, size_t& counter): 
     Comparator(comp), mCounter(&counter) {} 

    template <class T, class U> 
    bool operator()(T& lhs, U& rhs) const 
    { 
     ++(*mCounter); 
     return this->Comparator::operator()(lhs,rhs); 
    } 
    private: 
    size_t* mCounter; 
    }; 
} // namespace detail 

template < 
    class Key, 
    class Value, 
    class Cmp = std::less<Key>, 
    class Allocator = std::allocator< std::pair<const Key,Value> > 
> 
class SuperMap 
{ 
    typedef detail::CounterComparator<Cmp> Comparator; 
public: 
    SuperMap(): mCounter(0), mData(Comparator(mCounter)) {} 

    Value& operator[](const Key& key) { return mData[key]; } 

    size_t rank(const Key& key) const 
    { 
    mCounter = 0; mData.find(key); return mCounter; 
    } 

private: 
    typedef std::map<Key,Value, Comparator, Allocator> data_type; 

    mutable size_t mCounter; 
    data_type mData; 
}; // class SuperMap 

int main(int argc, char* argv[]) 
{ 
    SuperMap<int,int> superMap; 
    superMap[1] = 42; 
    std::cout << superMap.rank(1) << std::endl; 
} 

// outputs 
// 2 

Conta il numero di test, ma dal momento che std::map interrompe il test non appena ottiene la chiave giusta ... dovrebbe essere tutto a posto :) Anche se probabilmente c'è qualche compensazione da dedurre (1 o 2) per ottenere il rank.

Se hai dato una definizione migliore di rank, posso lavorare un po 'di più ma non voglio passare troppo tempo nella direzione sbagliata.

Answer 2

Il rango della data chiave K è il numero di chiavi che sono meno o uguale a K.

esempio lasciare set s = {1, 3, 4, 6, 9}. Quindi rank (1) = 1, rank (4) = 3, rank (9) = 5.

La funzione STL distance() può essere utilizzata per calcolare il rango di un elemento x visualizzato nell'insieme s.

rank = distance (s.begin(), s.find (x));

Il problema è che la sua complessità temporale è O (n).

Si noti che la proposta di due mappe (o serie) indicizzate per chiave e per classifica non è la soluzione corretta. Il problema è che un cambiamento di un elemento influenza i ranghi di molti altri. Ad esempio, aggiungendo l'elemento 0 all'insieme di cui sopra, modificare i ranghi di tutti gli elementi esistenti: s '= {0, 1, 3, 4, 6, 9}. rank (1) = 2, rank (4) = 4, rank (9) = 6.

Grazie.

Answer 3

Ho implementato un "albero rosso-nero classificato" che è simile a un albero rosso-nero tranne che ogni nodo memorizza la distanza dal nodo che lo precede tramite una traversata in ordine, piuttosto che memorizzare una chiave.

Questo fa esattamente ciò che si desidera, ad eccezione del "rango" del primo nodo è 0 e non 1 (è possibile aggiungere/sottrarre 1 se necessario).

La mia soluzione è PUBLIC DOMAIN ed è basata su un'esercitazione di pubblico dominio per un normale albero rosso-nero. Tutte le operazioni, inclusi inserimento, rimozione, individuazione e determinazione del rango hanno un tempo logaritmico rispetto al numero di elementi nella struttura dati.

Lo si può trovare qui: http://code.google.com/p/options/downloads/list

Si dovrebbe ottenere l'ultima versione dal link qui sopra, attualmente (al momento della stesura) rrb_v4_release.cpp.

Answer 4

è possibile utilizzare altri tipi di mappe come contenitori.
mantenere i campi di una dimensione può rendere l'accesso alla ricerca di un albero binario di facile accesso casuale. stile
ecco la mia implementazione ...
std, accesso iteratore casuale ...
dimensione equilibrata albero ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
e B + tree ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h