J'ai eu une tâche de ce type. Il est nécessaire de réaliser un conteneur de stockage de données offrant la fonctionnalité suivante :
- insérer un nouvel élément
- supprimer un élément par son numéro d'ordre
- obtenir un élément par son numéro d'ordre
- les données sont stockées de manière triée
Les données sont constamment ajoutées et supprimées, la structure doit assurer une vitesse de traitement rapide. Au début, j'ai essayé de réaliser cela en utilisant les conteneurs standards de std. Ce chemin n'a pas été couronné de succès et j'ai compris qu'il fallait que je développe quelque chose moi-même. La seule chose qui m'est venue à l'esprit était d'utiliser un arbre binaire de recherche. Puisqu'il répond à l'exigence d'une insertion rapide, d'une suppression et du stockage des données de manière triée. Il ne reste plus qu'à réfléchir à la manière d'indexer tous les éléments et de recalculer les index lorsque l'arbre change.
struct node_s {
data_t data;
uint64_t weight; // poids du nœud
node_t *left;
node_t *right;
node_t *parent;
};L'article contiendra plus d'images et de théorie que de code. Vous pourrez consulter le code via le lien en bas.
Poids
Pour cela, l'arbre a subi une légère modification, ajoutant des informations supplémentaires sur le poids du nœud. Le poids d'un nœud est le nombre de descendants de ce nœud + 1 (poids d'un élément unique).
La fonction pour obtenir le poids du nœud :
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Pour une feuille, le poids est donc 0.
Ensuite, passons à une représentation visuelle d'un tel arbre. En noir la clé du nœud sera affichée (la valeur ne sera pas affichée, car cela n'est pas nécessaire), en rouge — le poids du nœud, en vert — l'indice du nœud.
Lorsque l'arbre est vide, son poids est égal à 0. Ajoutons-y l'élément racine :
Le poids de l'arbre devient 1, le poids de l'élément racine est 1. Le poids de l'élément racine est le poids de l'arbre.
Ajoutons quelques éléments supplémentaires :
Chaque fois qu'un nouvel élément est ajouté, nous descendons dans les nœuds et augmentons le compteur de poids de chaque nœud parcouru. Lors de la création d'un nouveau nœud, son poids est défini 1. Si un nœud avec cette clé existe déjà, nous écraserons la valeur et reviendrons en arrière jusqu'à la racine, annulant les modifications des poids de tous les nœuds que nous avons traversés.
S'il y a suppression d'un nœud, alors nous descendons et décrémentons les poids des nœuds parcourus.
Indices
Nous allons maintenant aborder comment indexer les 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, il faudrait du temps O(n) pour mettre à jour les index de tous les nœuds après chaque modification de l'arbre.
Passons à une représentation visuelle. Notre arbre est vide, ajoutons-y le premier nœud :
Le premier nœud a un index 0, et maintenant deux cas sont possibles. Dans le premier, l'index de l'élément racine changera, dans le second, il ne changera pas.
La sous-arbre gauche de la racine pèse 1.
Deuxième cas :
L'index de la racine n'a pas changé, car le poids de son sous-arbre gauche est resté à 0.
Comment l'index d'un nœud est-il calculé ? C'est le poids de son sous-arbre gauche + le nombre passé par le parent. Quel est ce nombre ? C'est le compteur d'index, qui est initialement 0, car la racine n'a pas de parent. Ensuite, tout dépend de la direction où nous descendons, vers l'enfant gauche ou droit. Si vers le gauche, le compteur n'augmente pas. Si vers le droit, nous ajoutons l'index du nœud actuel.
Par exemple, comment se calcule l'index d'un élément avec la clé 8 (l'enfant droit de la racine). C'est "Index de la racine" + "poids de l'arbre gauche du nœud avec la clé 8" + "1" == 3 + 2 + 1 == 6
L'index de l'élément avec la clé 6 sera "Index de la racine" + 1 == 3 + 1 == 4
Par conséquent, pour obtenir ou supprimer un élément par index, il faut du temps O(log n), car pour obtenir l'élément nécessaire, nous devons d'abord le trouver (descendre de la racine jusqu'à cet élément).
Profondeur
Sur la base du poids, il est également possible de calculer la profondeur de l'arbre. Nécessaire pour l'équilibrage.
Pour cela, le poids du nœud actuel doit être arrondi au premier nombre de la puissance 2 qui est supérieur ou égal au poids donné, et nous prenons le logarithme binaire de ce nombre. De cette manière, nous obtiendrons la profondeur de l'arbre, à condition qu'il soit équilibré. L'arbre est équilibré après l'insertion d'un nouvel élément. Je ne vais pas expliquer la théorie sur comment équilibrer les arbres. La fonction d'équilibrage est présentée dans le code source.
Code de conversion du poids en profondeur.
/*
* Возвращает первое число в степени 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));
}Résultats
- L'insertion d'un nouvel élément se fait en O(log n)
- La suppression d'un élément par son numéro se fait en O(log n)
- L'obtention d'un élément par son numéro se fait en O(log n)
Vitesse O(log n) nous payons pour le fait que toutes les données sont stockées sous forme triée.
Je ne sais pas où une telle structure pourrait être utile. C'est juste un exercice pour comprendre comment fonctionnent les arbres. Merci pour votre attention.
Liens
Le projet contient des données de test pour vérifier la vitesse de fonctionnement. L'arbre se remplit 1000000 d'éléments. Et il se produit une suppression, une insertion et une récupération d'éléments successives 1000000 fois. C'est-à-dire 3000000 opérations. Le résultat s'est avéré plutôt bon ~ 8 secondes.
Source : habr.com
