Pourquoi est-ce que std::map implémentée sous forme d’arbre rouge-noir ?

Question

Pourquoi est-ce que std::map implémentée comme un arbre rouge-noir ? Il y a plusieurs équilibré CEST là-bas, ce qui ont été compromis dans le choix des arbres rouge-noir design ?

Answer 1

Probablement les deux plus commun d'auto équilibrage de l'arbre algorithmes sont des arbres Rouge-Noir et AVL arbres. À l'équilibre de l'arbre, après une insertion/mise à jour deux algorithmes utilisent la notion de rotations où les nœuds de l'arbre sont en rotation pour effectuer le ré-équilibrage.

Alors que dans les deux algorithmes d'insérer ou de supprimer des opérations sont en O(log n), dans le cas de la Rouge-Noir arbre de ré-équilibrage de la rotation est un O(1) opérations, alors avec AVL c'est un O(log n) opération, ce qui rend le Rouge-Noir arbre plus efficace dans cet aspect de la ré-équilibrage de la scène et l'une des raisons pour lesquelles il est plus couramment utilisé.

Arbres rouge-Noir sont utilisés dans la plupart de la collection de bibliothèques, y compris les offres de Java et Microsoft .NET Framework.

Answer 2

Cela dépend vraiment de l’utilisation. Arbre AVL a plus grande complexité du rééquilibrage. Donc si votre application ne possède pas trop de d’insertion et les opérations de suppression, mais poids fortement sur la recherche, puis arbre AVL est probablement un bon choix.

std::Map utilise arbre rouge-noir qu’il obtient un compromis raisonnable entre la complexité du nœud insertion/délétion et la recherche.

Answer 3

AVL arbres ont une hauteur maximale de 1,44 logn, tandis que RB arbres ont un maximum de 2logn. L'insertion d'un élément dans un AVL peut impliquer un rééquilibrage à un point de l'arbre. Le rééquilibrage des finitions de l'insertion. Après l'insertion d'une nouvelle feuille, la mise à jour les ancêtres de cette feuille doit être fait jusqu'à la racine, ou jusqu'à un point où les deux sous-arbres sont de la même profondeur. La probabilité d'avoir à mettre à jour k nœuds est de 1/3^k. Le rééquilibrage est O(1). Suppression d'un élément peut impliquer plus d'un rééquilibrage (jusqu'à la moitié de la profondeur de l'arbre).

RB-arbres sont des B-arbres de l'ordre de 4 représentés comme des arbres binaires. 4-nœud dans le B-arbre à deux niveaux dans l'équivalent du BST. Dans le pire des cas, tous les nœuds de l'arbre sont de 2 nœuds, avec une seule chaîne de 3-nœuds vers une feuille. Cette feuille sera à une distance de 2logn à partir de la racine.

Allez vers le bas à partir de la racine du point d'insertion, on chnage de 4 nœuds en 2-nœuds, assurez-vous tout d'insertion ne sera pas de saturer une feuille. En revenant de l'insertion, tous ces nœuds doivent être analysés pour s'assurer qu'ils représentent correctement à 4 nœuds. Cela peut aussi être fait en descendant dans l'arbre. Le coût global sera le même. Il n'y a pas de repas gratuit! Suppression d'un élément de l'arbre est du même ordre.

Tous ces arbres ont besoin que les nœuds portent des informations sur la taille, le poids, la couleur, etc. Seulement Écarter les arbres sont gratuits à partir de ces informations supplémentaires. Mais la plupart des gens ont peur de s'écartent des arbres, à cause de la ramdomness de leur structure!

Enfin, les arbres peuvent aussi transporter des informations de poids dans les nœuds, permettant des poids d'équilibrage. Différents systèmes peuvent être appliquées. On devrait rééquilibrer lorsqu'un sous-arbre contient plus de 3 fois le nombre d'éléments de l'autre sous-arbre. Le rééquilibrage est à nouveau fait soit devant un simple ou double rotation. Cela signifie un pire cas de 2,4 logn. On peut s'en tirer avec 2 fois au lieu de 3, un bien meilleur ratio, mais cela peut signifier qu'il reste un peu moins que 1% de la sous-arbres déséquilibrés ici et là. Délicat!

Quel type d'arbre est le meilleur? AVL pour vous. Ils sont les plus simples à code, et ont leurs pires hauteur la plus proche de logn. Pour un arbre de 1000000 éléments, un AVL sera au plus de hauteur de 29, un RB 40, et un poids équilibré 36 ou 50 selon le rapport.

Il y a beaucoup d'autres variables: l'aléatoire, le ratio des ajouts, des suppressions, des recherches, etc.

Answer 4

C’est juste le choix de votre implémentation - ils pourraient être mis en œuvre comme n’importe quel arbre équilibré. les différents choix sont tous comparables avec des différences mineures donc tout est aussi bon que n’importe quel.