BIT: utilisation d'un arbre indexé binaire? [fermé]
Un arbre indexé binaire a très peu ou relativement aucune théorie à étudier par rapport à d'autres structures de données. Le seul endroit où il est enseigné succinctement est le tutoriel topcoder . Bien que le tutoriel soit complet dans toutes les explications, Je ne peux pas comprendre que quelle est l'intuition derrière un tel arbre? Et comment prouver son exactitude?
Je présume que la preuve est complexe à expliquer. Donc, lorsque vous utilisez BIT, quelle approche suivez-vous?
1 réponses
J'ai trouvé cette réponse par @templatetypedef explique très clairement l'intuition et la preuve d'un arbre indexé binaire: Réponse....
Intuitivement, vous pouvez penser à un arbre indexé binaire comme une représentation compressée d'un arbre binaire qui est lui-même une optimisation d'une représentation de tableau standard. Cette réponse va dans une dérivation possible.
Supposons, par exemple, que vous souhaitez stocker des fréquences cumulées pour un total de 7 élément. Vous pouvez commencer par écrire sept seaux dans lesquels les numéros seront distribués:
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
1 2 3 4 5 6 7
Maintenant, supposons que les fréquences cumulées ressemblent à ceci:
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
1 2 3 4 5 6 7
En utilisant cette version du tableau, vous pouvez incrémenter la fréquence cumulative de n'importe quel élément en augmentant la valeur du nombre stocké à cet endroit, puis en incrémentant les fréquences de tout ce qui vient après. Par exemple, pour augmenter la fréquence cumulative de 3 par 7, Nous pourrions ajouter 7 à chaque élément du tableau à ou après la position 3, comme indiqué ici:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
Le problème avec ceci est qu'il faut du temps à O (n) pour le faire, ce qui est assez lent si n est grand.
Une façon de penser à améliorer cette opération serait de changer ce que nous stockons dans les seaux. Plutôt que de stocker la fréquence cumulative jusqu'au point donné, vous pouvez plutôt penser à stocker simplement la quantité à laquelle la fréquence actuelle a augmenté par rapport la précédente seau. Par exemple, dans notre cas, nous réécrirons les seaux ci-dessus comme suit:
Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
Maintenant, nous pouvons incrémenter la fréquence dans un compartiment dans le temps O (1) en ajoutant simplement la quantité appropriée à ce compartiment. Cependant, le coût total d'une recherche devient maintenant O (n), puisque nous devons recalculer le total dans le compartiment en additionnant les valeurs dans tous les compartiments plus petits.
Le premier aperçu majeur que nous devons obtenir d'ici à un arbre indexé binaire est le suivant: plutôt que de recalculer continuellement la somme des éléments du tableau qui précèdent un élément particulier, que se passe-t-il si nous devions précalculer la somme totale de tous les éléments avant des points spécifiques de la séquence? Si nous pouvions le faire, nous pourrions alors calculer la somme cumulative à un moment donné en résumant simplement la bonne combinaison de ces sommes précalculées.
Une façon de le faire est de modifier la représentation d'un tableau de seaux d'être un arbre binaire de nœuds. Chacun node sera annoté avec une valeur qui représente la somme cumulative de tous les nœuds à gauche de ce nœud donné. Par exemple, supposons que nous construisions l'arbre binaire suivant à partir de ces nœuds:
4
/ \
2 6
/ \ / \
1 3 5 7
Maintenant, nous pouvons augmenter chaque nœud en stockant la somme cumulative de toutes les valeurs, y compris ce nœud et son sous-arbre de gauche. Par exemple, compte tenu de nos valeurs, nous stockerions ce qui suit:
Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
After:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[ +5] [+15] [+52] [ +0]
Compte tenu de cette structure arborescente, il est facile de déterminer la somme cumulative jusqu'à un point. L'idée est la suivante: nous maintenons un compteur, initialement 0, puis une recherche binaire jusqu'à nous de trouver le nœud en question. Comme nous le faisons, nous avons aussi ce qui suit: chaque fois que nous passons à droite, nous ajoutons également la valeur actuelle au compteur.
Par exemple, supposons que nous voulions rechercher la somme pour 3. Pour ce faire, nous procédons comme suit:
- commence à la racine (4). Le compteur est 0.
- aller à gauche au noeud (2). Le compteur est 0.
- allez à droite au nœud (3). Compteur est 0 + 6 = 6.
- trouver le noeud (3). Compteur est 6 + 15 = 21.
Vous pouvez également imaginer exécuter ce processus à l'envers: en commençant par un nœud donné, initialisez le compteur à la valeur de ce nœud, puis remontez l'arbre jusqu'à la racine. Chaque fois que vous suivez un lien enfant droit vers le haut, ajoutez la valeur au nœud auquel vous arrivez. Par exemple, pour trouver la fréquence pour 3, Nous pourrions faire ce qui suit:
- commence au nœud (3). Le compteur est 15.
- Aller vers le haut pour noeud (2). Compteur est 15 + 6 = 21.
- Aller vers le haut au noeud (1). Le compteur est 21.
Pour incrémenter la fréquence d'un nœud (et, implicitement, les fréquences de tous les nœuds qui le suivent), nous devons mettre à jour l'ensemble des nœuds de l'arborescence qui incluent ce nœud dans son sous-arbre gauche. Pour ce faire, nous procédons comme suit: incrémenter la fréquence de ce nœud, puis commencer à marcher jusqu'à la racine de l'arbre. Chaque fois que vous suivez un lien qui vous prend comme un enfant gauche, incrémenter le fréquence du nœud que vous rencontrez en ajoutant la valeur actuelle.
Par exemple, pour incrémenter la fréquence du noeud 1 par cinq, nous ferions ce qui suit:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[ +5] [+15] [+52] [ +0]
À partir du nœud 1, incrémentez sa fréquence de 5 pour obtenir
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[+10] [+15] [+52] [ +0]
Maintenant, allez à sa mère:
4
[+32]
/ \
> 2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Nous avons suivi un lien enfant gauche vers le haut, Donc nous incrémentons également la fréquence de ce nœud:
4
[+32]
/ \
> 2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Nous allons maintenant à son parent:
> 4
[+32]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
C'était un lien enfant gauche, donc nous incrémenter ce nœud aussi:
4
[+37]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Et maintenant c'est fini!
La dernière étape consiste à convertir cela en un arbre indexé binaire, et c'est là que nous pouvons faire des choses amusantes avec des nombres binaires. Réécrivons chaque index de seau dans cet arbre en binaire:
100
[+37]
/ \
010 110
[+11] [+80]
/ \ / \
001 011 101 111
[+10] [+15] [+52] [ +0]
Ici, nous pouvons faire une observation très, très cool. Prenez l'un de ces nombres binaires et trouvez le tout dernier 1 qui a été défini dans le nombre, puis déposez ce bit, ainsi que tous les bits qui viennent après. Il vous reste maintenant ce qui suit:
(empty)
[+37]
/ \
0 1
[+11] [+80]
/ \ / \
00 01 10 11
[+10] [+15] [+52] [ +0]
Voici une observation vraiment, vraiment cool: si vous traitez 0 pour signifier "gauche" et 1 pour signifier "droit", les bits restants sur chaque nombre expliquent exactement comment commencer à la racine et ensuite descendre à ce nombre. Par exemple, le nœud 5 a un motif binaire 101. Le dernier 1 est le dernier bit, donc nous laissons tomber pour obtenir 10. En effet, si vous commencez à la racine, allez à droite (1), puis allez à gauche (0), Vous vous retrouvez au nœud 5!
La raison pour laquelle c'est significatif est que nos opérations de recherche et de mise à jour dépendent du chemin d'accès du nœud jusqu'à la racine et si nous suivons les liens enfants gauche ou droit. Par exemple, lors d'une recherche, nous nous soucions simplement des liens de gauche que nous suivons. Lors d'une mise à jour, nous nous soucions juste des bons liens que nous suivons. Cet arbre indexé binaire fait tout cela super efficacement en utilisant simplement les bits de l'index.
L'astuce clé est la propriété suivante de ce binaire parfait arbre:
Étant donné le nœud n, Le nœud suivant sur le chemin d'accès jusqu'à la racine dans laquelle nous allons à droite est donné en prenant la représentation binaire de n et en supprimant le dernier 1.
Par exemple, jetez un oeil au chemin d'accès pour le nœud 7, qui est 111. Les nœuds sur le chemin d'accès à la racine que nous prenons qui impliquent de suivre un pointeur droit vers le haut sont
- noeud 7: 111
- noeud 6: 110
- noeud 4: 100
Tous ces sont les liens à droite. Si nous prenons le chemin d'accès pour le nœud 3, qui est 011, et regardons les nœuds où nous allons à droite, nous obtenons
- noeud 3: 011
- noeud 2: 010
- (Nœud 4: 100, qui suit un lien de gauche)
Cela signifie que nous pouvons très, très efficacement calculer la somme cumulative jusqu'à un nœud comme suit:
- Ecrire le noeud n en binaire.
- Réglez le compteur sur 0.
- répétez ce qui suit alors que n 0:
- ajouter la valeur au nœud n.
- supprimer le bit 1 le plus à gauche de n.
De même, réfléchissons à la façon dont nous ferions une étape de mise à jour. Pour ce faire, nous voudrions suivre le chemin d'accès jusqu'à la racine, en mettant à jour tous les nœuds où nous avons suivi un lien gauche vers le haut. Nous pouvons le faire en faisant essentiellement l'algorithme ci-dessus, mais en changeant tous les 1 à 0 et 0 à 1.
La dernière étape dans l'arborescence indexée binaire est de noter que parce que de cette supercherie au niveau du BIT, nous n'avons même plus besoin d'avoir l'arbre stocké explicitement. Nous pouvons simplement stocker tous les nœuds dans un tableau de longueur n, puis utiliser les techniques de twiddling au niveau du BIT pour naviguer implicitement dans l'arbre. En fait, c'est exactement ce que fait l'arbre indexé au niveau du BIT - il stocke les nœuds dans un tableau, puis utilise ces astuces au niveau du BIT pour simuler efficacement la marche vers le haut dans cet arbre.
Espérons que cela aide!