J'ai eu le problème suivant. Il est nécessaire d'implémenter un conteneur de stockage de données qui offre les fonctionnalités suivantes:
- insérer un nouvel élément
- supprimer l'élément par numéro de série
- obtenir l'article par numéro de série
- les données sont stockées sous forme triée
Les données sont constamment ajoutées et supprimées, la structure doit fournir une vitesse rapide. Au début, j'ai essayé d'implémenter une telle chose en utilisant des conteneurs standard de std . Ce chemin a été infructueux et la compréhension est venue que vous devez mettre en œuvre quelque chose vous-même. La seule chose qui m'est venue à l'esprit était d'utiliser un arbre de recherche binaire. Puisqu'il répond à l'exigence d'insertion, de suppression et de stockage rapides des données sous forme triée. Il ne reste plus qu'à comprendre comment indexer tous les éléments et recalculer les indices lorsque l'arbre change.
struct node_s { data_t data; uint64_t weight;
L'article contiendra plus d'images et de théorie que de code. Le code peut être consulté sur le lien ci-dessous.
Le poids
Pour cela, l'arbre a subi une légère modification, des informations supplémentaires sur le poids du nœud ont été ajoutées. Le poids d'un nœud est le nombre de descendants de ce nœud + 1 (poids d'un seul élément).
La fonction d'obtention du poids du nœud:
uint64_t bntree::get_child_weight(node_t *node) { if (node) { return node->weight; } return 0; }
La feuille, respectivement, a un poids de 0 .
Ensuite, nous nous tournons vers une représentation visuelle d'un exemple d'un tel arbre. La clé du nœud sera affichée en noir (la valeur ne sera pas affichée, car cela n'est pas nécessaire), rouge est le poids du nœud, vert est l'index du nœud.
Lorsque l'arbre est vide, son poids est égal à 0. Ajoutez-y l'élément racine:
Le poids de l'arbre devient 1, le poids de l'élément racine 1. Le poids de l'élément racine est le poids de l'arbre.
Ajoutez quelques éléments supplémentaires:
Chaque fois qu'un nouvel élément est ajouté, nous descendons les nœuds vers le bas et augmentons le compteur de poids de chaque nœud passé. Lors de la création d'un nouveau nœud, il est défini sur le poids 1 . Si un nœud avec une telle clé existe déjà, réécrivez la valeur et remontez à la racine, annulant les changements de poids de tous les nœuds que nous avons passés.
Si le nœud est supprimé, nous descendons et décrémentons les poids des nœuds passés.
Indices
Passons maintenant à l'indexation des nœuds. Les nœuds ne stockent pas explicitement leur index; il est calculé en fonction du poids des nœuds. S'ils stockaient leur index, alors O (n) temps serait nécessaire pour mettre à jour les index de tous les nœuds après chaque changement de l'arbre.
Passons à une représentation visuelle. Notre arbre est vide, ajoutez-y le 1er nœud:
Le premier nœud a l'index 0 , et maintenant 2 cas sont possibles. Dans le premier, l'index de l'élément racine changera; dans le second, il ne changera pas.
À la racine, le sous-arbre gauche pèse 1.
Deuxième cas:
L'index racine n'a pas changé puisque le poids de son sous-arbre gauche reste 0.
Comme l'index du nœud est considéré, c'est le poids de son sous-arbre gauche + le nombre transmis par le parent. Quel est ce nombre?, Ceci est un compteur d'index, initialement il est 0 , car la racine n'a pas de parent. Ensuite, tout dépend de l'endroit où nous descendons vers l'enfant gauche ou vers la droite. Si à gauche, rien n'est ajouté au compteur. Si à droite, ajoutez l'index du nœud actuel.
Par exemple, comment calculer l'index d'un élément avec la clé 8 (l'enfant droit de la racine). Il s'agit du "Index racine" + "poids du sous-arbre gauche du nœud avec la clé 8" + "1" == 3 + 2 + 1 == 6
L'index de l'élément avec la clé 6 est "Index racine" + 1 == 3 + 1 == 4
Par conséquent, il faudrait O (log n) pour obtenir et supprimer un élément par index, car pour obtenir l'élément, nous devons d'abord le trouver (descendre de la racine à cet élément).
Profondeur
En fonction du poids, vous pouvez également calculer la profondeur de l'arbre. Nécessaire pour l'équilibrage.
Pour ce faire, le poids du nœud courant doit être arrondi au premier nombre de degré 2 supérieur ou égal au poids donné et en prendre le logarithme binaire. Ainsi, nous obtenons la profondeur de l'arbre, à condition qu'il soit équilibré. L'arbre est équilibré après l'insertion d'un nouvel élément. La théorie sur la façon d'équilibrer les arbres ne mènera pas. Le code source fournit une fonction d'équilibrage.
Code pour amener le poids en profondeur.
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)); }
Résumé
- l'insertion d'un nouvel élément se produit dans O (log n)
- la suppression d'élément par numéro de séquence se produit dans O (log n)
- obtenir un élément par son numéro de série se produit dans O (log n)
Avec la vitesse de O (log n), nous payons le fait que toutes les données sont stockées sous forme triée.
Là où une telle structure peut être utile, je ne sais pas. Juste une tâche pour comprendre à nouveau comment fonctionnent les arbres. Merci de votre attention.
Les références
Le projet contient des données de test pour vérifier la vitesse de travail. L'arbre est rempli de 1 000 000 d' éléments. Et il y a une suppression séquentielle, une insertion et une réception d'éléments 1 000 000 de fois. Cela représente 3 000 000 d' opérations. Le résultat était assez bon ~ 8 secondes.