Mi è stata proposta un'attività del seguente tipo. È necessario implementare un contenitore per la memorizzazione dei dati che fornisca le seguenti funzionalità:
- inserire un nuovo elemento
- rimuovere un elemento per numero di sequenza
- ottenere un elemento per numero di sequenza
- i dati vengono memorizzati in ordine
I dati vengono costantemente aggiunti e rimossi, la struttura deve garantire una rapida velocità di funzionamento. Inizialmente ho cercato di realizzare una cosa simile utilizzando i contenitori standard di std. Questo approccio non ha avuto successo e ho capito che dovevo implementare qualcosa da solo. L'unica idea che mi è venuta in mente è stata quella di utilizzare un albero binario di ricerca. Poiché soddisfa il requisito di rapida inserzione, rimozione e memorizzazione dei dati in ordine. Restava solo da ideare come indicizzare tutti gli elementi e riequilibrare gli indici quando l'albero cambia.
struct node_s {
data_t data;
uint64_t weight; // peso del nodo
node_t *left;
node_t *right;
node_t *parent;
};Nell'articolo ci saranno più immagini e teoria che codice. Il codice potrà essere visualizzato seguendo il link qui sotto.
Peso
Per questo, l'albero ha subito una piccola modifica, è stata aggiunta un'informazione aggiuntiva sul peso del nodo. Il peso del nodo è il numero di discendenti di questo nodo + 1 (peso di un elemento singolo).
Funzione per ottenere il peso del nodo:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Il peso della foglia è quindi pari a 0.
Passiamo ora a una rappresentazione visiva di un esempio di tale albero. In nero sarà mostrata la chiave del nodo (il valore non sarà mostrato, poiché non è necessario), in rosso — il peso del nodo, in verde — l'indice del nodo.
Quando l'albero è vuoto, il suo peso è pari a 0. Aggiungiamo il suo elemento radice:
Il peso dell'albero diventa 1, il peso dell'elemento radice è 1. Il peso dell'elemento radice è il peso dell'albero.
Aggiungiamo ancora alcuni elementi:
Ogni volta che viene aggiunto un nuovo elemento, scendiamo nei nodi in basso e aumentiamo il contatore del peso di ciascun nodo attraversato. Quando viene creato un nuovo nodo, gli viene assegnato un peso 1. Se esiste già un nodo con questa chiave, sovrascriviamo il valore e risaliamo verso l'alto fino alla radice annullando le modifiche ai pesi di tutti i nodi attraversati.
Se viene rimossa un nodo, scendiamo e decretiamo i pesi dei nodi attraversati.
Indici
Ora passiamo a come indicizzare i nodi. I nodi non memorizzano il proprio indice, questo viene calcolato in base al peso dei nodi. Se memorizzassero il proprio indice, sarebbe necessario O(n) tempo per aggiornare gli indici di tutti i nodi dopo ogni modifica dell'albero.
Passiamo a una rappresentazione visiva. Il nostro albero è vuoto, aggiungiamo il primo nodo:
Il primo nodo ha indice 0, e ora ci sono due casi possibili. Nel primo l'indice dell'elemento radice cambierà, nel secondo rimarrà invariato.
Alla radice il sottoalbero sinistro pesa 1.
Secondo caso:
L'indice della radice non è cambiato, poiché il peso del suo sottoalbero sinistro è rimasto 0.
Come si calcola l'indice di un nodo, è il peso del suo sottoalbero sinistro + il numero passato dal genitore. Che numero è questo? È il contatore degli indici, inizialmente vale 0, poiché la radice non ha genitore. Dopodiché, tutto dipende da dove scendiamo, al figlio sinistro o destro. Se al sinistro, il contatore non aumenta. Se al destro, aggiungiamo l'indice del nodo corrente.
Ad esempio, come si calcola l'indice dell'elemento con chiave 8 (figlio destro della radice). È «Indice della radice» + «peso del sottoalbero sinistro del nodo con chiave 8» + «1» == 3 + 2 + 1 == 6
L'indice dell'elemento con chiave 6 sarà «Indice della radice» + 1 == 3 + 1 == 4
Pertanto, per ottenere o eliminare un elemento per indice è necessario un tempo O(log n), poiché per ottenere l'elemento desiderato dobbiamo prima trovarlo (scendere dalla radice a questo elemento).
Profondità
Sulla base del peso è possibile calcolare anche la profondità dell'albero. Necessaria per il bilanciamento.
Per questo il peso del nodo corrente deve essere arrotondato al primo numero in potenza di 2 maggiore o uguale a tale peso e prendere il logaritmo binario di esso. In questo modo otterremo la profondità dell'albero, a condizione che sia bilanciato. L'albero viene bilanciato dopo l'inserimento di un nuovo elemento. Non tratterò la teoria su come bilanciare gli alberi. Nei codici sorgente è presente la funzione di bilanciamento.
Codice per il passaggio del peso alla profondità.
/*
* Возвращает первое число в степени 2, которое больше или ровно x
*/
uint64_t bntree::cpl2(uint64_t x) {
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x | (x >> 32);
return x + 1;
}
/*
* Двоичный логарифм от числа
*/
long bntree::ilog2(long d) {
int result;
std::frexp(d, &result);
return result - 1;
}
/*
* Вес к глубине
*/
uint64_t bntree::weight_to_depth(node_t *p) {
if (p == NULL) {
return 0;
}
if (p->weight == 1) {
return 1;
} else if (p->weight == 2) {
return 2;
}
return this->ilog2(this->cpl2(p->weight));
}Conclusioni
- l'inserimento di un nuovo elemento avviene in O(log n)
- l'eliminazione di un elemento per numero di ordine avviene in O(log n)
- l'ottenimento di un elemento per numero di ordine avviene in O(log n)
Velocità O(log n) paghiamo per il fatto che tutti i dati sono memorizzati in ordine.
Non so dove possa essere utile una struttura di questo tipo. È solo un esercizio per capire meglio come funzionano gli alberi. Grazie per l'attenzione.
Link
Il progetto contiene dati di test per verificare la velocità di esecuzione. L'albero viene riempito 1000000 di elementi. E avviene un'eliminazione, un'inserzione e un'ottenzione sequenziale degli elementi 1000000 una volta. Vale a dire 3000000 operazioni. Il risultato si è rivelato piuttosto buono, circa 8 secondi.
Fonte: habr.com
