Συνάντησα το παρακάτω είδος προβλήματος. Είναι απαραίτητο να εφαρμόσετε ένα κοντέινερ αποθήκευσης δεδομένων που να παρέχει τις ακόλουθες λειτουργίες:
- εισαγωγή νέου στοιχείου
- αφαιρέστε το στοιχείο κατά σειριακό αριθμό
- πάρτε το στοιχείο με τον τακτικό αριθμό
- τα δεδομένα αποθηκεύονται σε ταξινομημένη μορφή
Τα δεδομένα προστίθενται και αφαιρούνται συνεχώς, η δομή πρέπει να εξασφαλίζει γρήγορη ταχύτητα λειτουργίας. Στην αρχή προσπάθησα να εφαρμόσω κάτι τέτοιο χρησιμοποιώντας τυπικά δοχεία από std. Αυτό το μονοπάτι δεν στέφθηκε με επιτυχία και ήρθε η κατανόηση ότι έπρεπε να υλοποιήσω κάτι ο ίδιος. Το μόνο πράγμα που μου ήρθε στο μυαλό ήταν να χρησιμοποιήσετε ένα δυαδικό δέντρο αναζήτησης. Επειδή πληροί την απαίτηση γρήγορης εισαγωγής, διαγραφής και αποθήκευσης δεδομένων σε ταξινομημένη μορφή. Το μόνο που μένει είναι να καταλάβουμε πώς να καταχωρήσουμε όλα τα στοιχεία και να υπολογίσουμε ξανά τους δείκτες όταν αλλάζει το δέντρο.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Το άρθρο θα περιέχει περισσότερες εικόνες και θεωρία παρά κώδικα. Μπορείτε να δείτε τον κωδικό στον παρακάτω σύνδεσμο.
Βάρος
Για να επιτευχθεί αυτό, το δέντρο υπέστη μια μικρή τροποποίηση, προστέθηκαν πρόσθετες πληροφορίες σχετικά βάρος κόμβος. Το βάρος του κόμβου είναι τον αριθμό των απογόνων αυτού του κόμβου + 1 (βάρος ενός μόνο στοιχείου).
Λειτουργία για τη λήψη βάρους κόμβου:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Το βάρος του φύλλου είναι αντίστοιχα ίσο με 0.
Στη συνέχεια, ας προχωρήσουμε σε μια οπτική αναπαράσταση ενός παραδείγματος τέτοιου δέντρου. Μαύρο το κλειδί κόμβου θα εμφανίζεται έγχρωμο (η τιμή δεν θα εμφανίζεται, καθώς αυτό δεν είναι απαραίτητο), κόκκινος — βάρος κόμπων, πράσινος — ευρετήριο κόμβου.
Όταν το δέντρο μας είναι άδειο, το βάρος του είναι 0. Ας προσθέσουμε ένα ριζικό στοιχείο σε αυτό:
Το βάρος του δέντρου γίνεται 1, το βάρος του ριζικού στοιχείου γίνεται 1. Το βάρος του ριζικού στοιχείου είναι το βάρος του δέντρου.
Ας προσθέσουμε μερικά ακόμη στοιχεία:
Κάθε φορά που προστίθεται ένα νέο στοιχείο, κατεβαίνουμε τους κόμβους και αυξάνουμε τον μετρητή βάρους κάθε κόμβου που περνάει. Όταν δημιουργείται ένας νέος κόμβος, του εκχωρείται ένα βάρος 1. Εάν υπάρχει ήδη ένας κόμβος με τέτοιο κλειδί, τότε θα αντικαταστήσουμε την τιμή και θα επιστρέψουμε στη ρίζα, ακυρώνοντας τις αλλαγές στα βάρη όλων των κόμβων που έχουμε περάσει.
Εάν αφαιρείται ένας κόμβος, τότε κατεβαίνουμε και μειώνουμε τα βάρη των περασμένων κόμβων.
Индексы
Τώρα ας προχωρήσουμε στον τρόπο ευρετηρίασης κόμβων. Οι κόμβοι δεν αποθηκεύουν ρητά το ευρετήριό τους, υπολογίζεται με βάση το βάρος των κόμβων. Εάν αποθήκευαν το ευρετήριό τους, τότε θα ήταν απαραίτητο O (n) χρόνος για ενημέρωση των ευρετηρίων όλων των κόμβων μετά από κάθε αλλαγή στο δέντρο.
Ας περάσουμε σε μια οπτική αναπαράσταση. Το δέντρο μας είναι κενό, ας προσθέσουμε τον 1ο κόμβο σε αυτό:
Ο πρώτος κόμβος έχει ευρετήριο 0, και τώρα είναι πιθανές 2 περιπτώσεις. Στο πρώτο, ο δείκτης του ριζικού στοιχείου θα αλλάξει, στο δεύτερο δεν θα αλλάξει.
Στη ρίζα, το αριστερό υποδέντρο ζυγίζει 1.
Δεύτερη περίπτωση:
Ο δείκτης της ρίζας δεν άλλαξε επειδή το βάρος του αριστερού υποδέντρου της παρέμεινε 0.
Ο δείκτης ενός κόμβου υπολογίζεται ως το βάρος του αριστερού υποδέντρου του + ο αριθμός που πέρασε από τον γονέα. Τι είναι αυτός ο αριθμός; Αυτός είναι ο μετρητής δείκτη, αρχικά ισούται με 0, επειδή η ρίζα δεν έχει γονέα. Τότε όλα εξαρτώνται από το πού κατεβαίνουμε στο αριστερό παιδί ή στο δεξί. Αν προς τα αριστερά, τότε δεν προστίθεται τίποτα στον μετρητή. Αν προσθέσουμε το ευρετήριο του τρέχοντος κόμβου στον δεξιό.
Για παράδειγμα, πώς υπολογίζεται ο δείκτης ενός στοιχείου με κλειδί 8 (το δεξί παιδί της ρίζας). Αυτό είναι "Δείκτης ρίζας" + "βάρος του αριστερού υποδέντρου του κόμβου με κλειδί 8" + "1" == 3 + 2 + 1 == 6
Ο δείκτης του στοιχείου με το κλειδί 6 θα είναι "Root Index" + 1 == 3 + 1 == 4
Αντίστοιχα, χρειάζεται χρόνος για να ληφθεί και να διαγραφεί ένα στοιχείο ανά ευρετήριο O (ημερολόγιο n), γιατί για να πάρουμε το επιθυμητό στοιχείο πρέπει πρώτα να το βρούμε (να κατέβουμε από τη ρίζα σε αυτό το στοιχείο).
Βάθος
Με βάση το βάρος, μπορείτε επίσης να υπολογίσετε το βάθος του δέντρου. Απαραίτητο για εξισορρόπηση.
Για να γίνει αυτό, το βάρος του τρέχοντος κόμβου πρέπει να στρογγυλοποιηθεί στον πρώτο αριθμό στη δύναμη του 2 που είναι μεγαλύτερο ή ίσο με το δεδομένο βάρος και να ληφθεί ο δυαδικός λογάριθμος από αυτόν. Αυτό θα μας δώσει το βάθος του δέντρου, υποθέτοντας ότι είναι ισορροπημένο. Το δέντρο ισορροπεί μετά την εισαγωγή ενός νέου στοιχείου. Δεν θα δώσω μια θεωρία για το πώς να ισορροπήσετε τα δέντρα. Οι πηγαίοι κώδικες παρέχουν μια λειτουργία εξισορρόπησης.
Κωδικός μετατροπής βάρους σε βάθος.
/*
* Возвращает первое число в степени 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));
}Αποτελέσματα της
- η εισαγωγή ενός νέου στοιχείου γίνεται σε O (ημερολόγιο n)
- Η διαγραφή ενός στοιχείου κατά σειριακό αριθμό λαμβάνει χώρα στο O (ημερολόγιο n)
- Η απόκτηση ενός στοιχείου με αύξοντα αριθμό συμβαίνει στο O (ημερολόγιο n)
Ταχύτητα O (ημερολόγιο n) Πληρώνουμε για το γεγονός ότι όλα τα δεδομένα αποθηκεύονται σε ταξινομημένη μορφή.
Δεν ξέρω πού μπορεί να είναι χρήσιμη μια τέτοια δομή. Απλά ένα παζλ για να καταλάβετε για άλλη μια φορά πώς λειτουργούν τα δέντρα. Σας ευχαριστώ για την προσοχή σας.
παραπομπές
Το έργο περιέχει δεδομένα δοκιμής για τον έλεγχο της ταχύτητας λειτουργίας. Το δέντρο γεμίζει 1000000 στοιχεία. Και υπάρχει διαδοχική διαγραφή, εισαγωγή και ανάκτηση στοιχείων 1000000 μια φορά. Αυτό είναι 3000000 επιχειρήσεις. Το αποτέλεσμα αποδείχθηκε αρκετά καλό ~ 8 δευτερόλεπτα.
Πηγή: www.habr.com