Ho riscontrato il seguente tipo di problema. È necessario implementare un contenitore di archiviazione dati che fornisca le seguenti funzionalità:
- inserire un nuovo elemento
- rimuovere l'elemento in base al numero di serie
- ottieni l'elemento per numero ordinale
- i dati vengono memorizzati in forma ordinata
I dati vengono costantemente aggiunti e rimossi, la struttura deve garantire un'elevata velocità operativa. All'inizio ho provato a implementare una cosa del genere utilizzando i contenitori standard di std. Questo percorso non è stato coronato dal successo ed è arrivata la comprensione che dovevo implementare qualcosa da solo. L'unica cosa che mi è venuta in mente è stata quella di utilizzare un albero di ricerca binario. Perché soddisfa i requisiti di inserimento, cancellazione e archiviazione rapidi dei dati in forma ordinata. Non resta che capire come indicizzare tutti gli elementi e ricalcolare gli indici quando cambia l'albero.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};L'articolo conterrà più immagini e teoria che codice. Il codice può essere visualizzato al link sottostante.
Peso
Per raggiungere questo obiettivo, l'albero ha subito una leggera modifica, sono state aggiunte ulteriori informazioni peso nodo. Il peso del nodo è numero di discendenti di questo nodo + 1 (peso di un singolo elemento).
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 del foglio è corrispondentemente uguale a 0.
Passiamo quindi alla rappresentazione visiva di un esempio di tale albero. nero la chiave del nodo verrà mostrata a colori (il valore non verrà mostrato, poiché non è necessario), rosso — peso del nodo, verde — indice del nodo.
Quando il nostro albero è vuoto, il suo peso è 0. Aggiungiamo ad esso un elemento radice:
Il peso dell'albero diventa 1, il peso dell'elemento radice diventa 1. Il peso dell'elemento radice è il peso dell'albero.
Aggiungiamo qualche altro elemento:
Ogni volta che viene aggiunto un nuovo elemento, scendiamo nei nodi e aumentiamo il contatore del peso di ogni nodo superato. Quando viene creato un nuovo nodo, gli viene assegnato un peso 1. Se esiste già un nodo con tale chiave, sovrascriveremo il valore e torneremo alla radice, annullando le modifiche nei pesi di tutti i nodi che abbiamo superato.
Se un nodo viene rimosso, scendiamo e decrementiamo i pesi dei nodi passati.
Indici
Passiamo ora a come indicizzare i nodi. I nodi non memorizzano esplicitamente il loro indice, viene calcolato in base al peso dei nodi. Se memorizzassero il loro indice, sarebbe necessario O (n) tempo per aggiornare gli indici di tutti i nodi dopo ogni modifica nell'albero.
Passiamo ad una rappresentazione visiva. Il nostro albero è vuoto, aggiungiamo il primo nodo:
Il primo nodo ha un indice 0, e ora sono possibili 2 casi. Nel primo cambierà l'indice dell'elemento radice, nel secondo non cambierà.
Alla radice, il sottoalbero sinistro pesa 1.
Secondo caso:
L'indice della radice non è cambiato perché il peso del suo sottoalbero sinistro è rimasto 0.
L'indice di un nodo viene calcolato come il peso del suo sottoalbero sinistro + il numero passato dal genitore. Cos'è questo numero? Questo è il contatore dell'indice, inizialmente è uguale a 0, Perché la radice non ha genitore. Quindi tutto dipende da dove scendiamo: il bambino di sinistra o quello di destra. Se a sinistra, non viene aggiunto nulla al contatore. Se aggiungiamo l'indice del nodo corrente a quello di destra.
Ad esempio, come viene calcolato l'indice di un elemento con chiave 8 (il figlio destro della radice). Questo è "Indice radice" + "peso del sottoalbero sinistro del nodo con chiave 8" + "1" == 3 + 2 + 1 == 6
L'indice dell'elemento con chiave 6 sarà "Indice Radice" + 1 == 3 + 1 == 4
Di conseguenza, ci vuole tempo per ottenere ed eliminare un elemento per indice O (log n), perché per ottenere l'elemento desiderato dobbiamo prima trovarlo (scendere dalla radice a questo elemento).
profondità
In base al peso puoi anche calcolare la profondità dell'albero. Necessario per il bilanciamento.
Per fare ciò, il peso del nodo corrente deve essere arrotondato alla prima cifra alla potenza di 2 che è maggiore o uguale al peso indicato e da esso ricavare il logaritmo binario. Questo ci darà la profondità dell'albero, supponendo che sia equilibrato. L'albero viene bilanciato dopo l'inserimento di un nuovo elemento. Non darò una teoria su come bilanciare gli alberi. I codici sorgente forniscono una funzione di bilanciamento.
Codice per convertire il peso in 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));
}Risultati di
- avviene l'inserimento di un nuovo elemento O (log n)
- l'eliminazione di un elemento in base al numero di serie avviene in O (log n)
- ottenere un elemento tramite numero di serie avviene in O (log n)
velocità O (log n) Paghiamo il fatto che tutti i dati siano archiviati in forma ordinata.
Non so dove una struttura del genere potrebbe essere utile. Solo un puzzle per capire ancora una volta come funzionano gli alberi. Grazie per l'attenzione.
riferimenti
Il progetto contiene dati di test per verificare la velocità di funzionamento. L'albero si sta riempiendo 1000000 elementi. E c'è una cancellazione, un inserimento e un recupero sequenziali degli elementi 1000000 una volta. Questo è 3000000 operazioni. Il risultato si è rivelato abbastanza buono ~ 8 secondi.
Fonte: habr.com