Un arbre binaire indexé a très peu ou pas de littérature par rapport à d'autres structures de données. Le seul endroit où il est enseigné est le tutoriel topcoder . Bien que le tutoriel soit complet dans toutes les explications, je ne peux pas comprendre l'intuition derrière un tel arbre? Comment a-t-il été inventé? Quelle est la preuve réelle de son exactitude?
algorithms
binary-trees
trees
Nikunj Banka
la source
la source
Réponses:
Intuitivement, vous pouvez imaginer une arborescence indexée binaire comme une représentation comprimée d'une arborescence binaire, qui est elle-même une optimisation d'une représentation de tableau standard. Cette réponse entre dans une dérivation possible.
Supposons, par exemple, que vous souhaitiez stocker des fréquences cumulées pour un total de 7 éléments différents. Vous pouvez commencer par écrire sept paniers dans lesquels les numéros seront distribués:
Supposons maintenant que les fréquences cumulées ressemblent à ceci:
En utilisant cette version du tableau, vous pouvez incrémenter la fréquence cumulée 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 cumulée de 3 sur 7, nous pourrions ajouter 7 à chaque élément du tableau à ou après la position 3, comme indiqué ci-dessous:
Le problème avec ceci est que cela prend O (n) temps, ce qui est assez lent si n est grand.
Une façon de penser à l’amélioration de cette opération serait de changer ce que nous stockons dans les compartiments. Plutôt que de stocker la fréquence cumulée jusqu'à un point donné, vous pouvez plutôt penser à stocker uniquement le montant de l'augmentation de la fréquence actuelle par rapport au compartiment précédent. Par exemple, dans notre cas, nous réécririons les compartiments ci-dessus comme suit:
Nous pouvons maintenant incrémenter la fréquence dans un intervalle dans le temps O (1) en ajoutant simplement la quantité appropriée à cet intervalle. Cependant, le coût total de la recherche devient maintenant O (n), car nous devons recalculer le total dans le compartiment en additionnant les valeurs de tous les compartiments plus petits.
La première idée importante que nous devons tirer d’ici un arbre indexé binaire est la suivante: au lieu de recalculer continuellement la somme des éléments du tableau qui précèdent un élément particulier, qu’en serait-il si nous devions pré-calculer la somme totale de tous les éléments avant points dans la séquence? Si nous pouvions le faire, nous pourrions alors calculer la somme cumulée à un moment donné en résumant simplement la bonne combinaison de ces sommes précalculées.
Une façon de procéder consiste à changer la représentation, qui passe d’un tableau de compartiments à un arbre binaire de nœuds. Chaque nœud sera annoté avec une valeur qui représente la somme cumulative de tous les nœuds situés à gauche de ce nœud donné. Par exemple, supposons que nous construisions l'arborescence binaire suivante à partir de ces nœuds:
Maintenant, nous pouvons augmenter chaque noeud en stockant la somme cumulative de toutes les valeurs, y compris ce noeud et son sous-arbre de gauche. Par exemple, compte tenu de nos valeurs, nous stockons les éléments suivants:
Étant donné cette arborescence, il est facile de déterminer la somme cumulée jusqu’à un certain point. L'idée est la suivante: nous maintenons un compteur, initialement 0, puis effectuons une recherche binaire normale jusqu'à trouver le nœud en question. Ce faisant, nous avons également les éléments suivants: chaque fois que nous nous déplaçons à droite, nous ajoutons également la valeur actuelle au compteur.
Par exemple, supposons que nous recherchions la somme pour 3. Pour cela, nous procédons comme suit:
Vous pouvez également imaginer exécuter ce processus à l’inverse: en commençant par un nœud donné, initialisez le compteur à la valeur de ce nœud, puis accédez à l’arborescence jusqu’à la racine. Chaque fois que vous suivez un lien enfant droit vers le haut, ajoutez la valeur sur le nœud auquel vous arrivez. Par exemple, pour trouver la fréquence pour 3, nous pourrions procéder comme suit:
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 comprenant ce nœud dans son sous-arbre de gauche. Pour ce faire, procédez comme suit: incrémentez la fréquence de ce nœud, puis commencez à vous déplacer à la racine de l’arbre. Chaque fois que vous suivez un lien qui vous prend comme enfant de gauche, incrémentez la fréquence du nœud que vous rencontrez en ajoutant la valeur actuelle.
Par exemple, pour incrémenter la fréquence du nœud 1 de cinq, procédez comme suit:
À partir du noeud 1, incrémentez sa fréquence de 5 pour obtenir
Maintenant, allez à son parent:
Nous avons suivi un lien enfant de gauche vers le haut, nous avons donc incrémenté la fréquence de ce nœud également:
Nous allons maintenant à son parent:
C'était un lien enfant de gauche, alors nous incrémentons également ce noeud:
Et maintenant nous avons fini!
La dernière étape consiste à convertir cette arborescence 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 compartiment de cette arborescence en binaire:
Ici, nous pouvons faire une observation très, très cool. Prenez n'importe lequel de ces nombres binaires et recherchez le tout dernier 1 qui a été défini dans le nombre, puis supprimez ce bit, ainsi que tous les bits qui le suivent. Vous êtes maintenant avec ce qui suit:
Voici une observation vraiment très intéressante: si vous traitez 0 comme signifiant "à gauche" et 1 comme "correct", les bits restants de chaque nombre précisent exactement comment commencer à la racine et revenir ensuite à ce nombre. Par exemple, le noeud 5 a le motif binaire 101. Le dernier 1 est le dernier bit, nous allons donc laisser tomber pour obtenir 10. En effet, si vous commencez à la racine, allez à droite (1), puis à gauche (0), vous terminez au noeud 5!
La raison pour laquelle cela est important est que nos opérations de recherche et de mise à jour dépendent du chemin d'accès du nœud à la racine et du fait que nous suivons les liens enfants de gauche ou de droite. Par exemple, lors d'une recherche, nous nous soucions seulement des bons liens que nous suivons. Lors d'une mise à jour, nous nous soucions seulement des liens de gauche que nous suivons. Cet arbre indexé binaire fait tout cela très efficacement en utilisant simplement les bits de l'index.
L'astuce clé est la propriété suivante de cet arbre binaire parfait:
Par exemple, examinez le chemin d'accès du noeud 7, qui est le 111. Les noeuds du chemin d'accès à la racine que nous prenons et qui impliquent de suivre un pointeur droit se trouvent vers le haut.
Ce sont tous des bons liens. 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
Cela signifie que nous pouvons calculer très, très efficacement la somme cumulée d’un nœud comme suit:
De même, réfléchissons à la manière 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 de gauche vers le haut. Nous pouvons le faire en faisant essentiellement l’algorithme ci-dessus, mais en commutant tous les 1 en 0 et les 0 en 1.
La dernière étape de l’arborescence indexée binaire consiste à noter qu’en raison de cette astuce au niveau des bits, il n’est même plus nécessaire de stocker l’arborescence explicitement. Nous pouvons simplement stocker tous les nœuds dans un tableau de longueur n, puis utiliser les techniques de rotation par bits pour naviguer de manière implicite 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 progression vers le haut dans cet arbre.
J'espère que cela t'aides!
la source
Je pense que le document original de Fenwick est beaucoup plus clair. La réponse ci-dessus de @templatetypedef nécessite des "observations très intéressantes" sur l'indexation d'un arbre binaire parfait, qui sont déroutantes et magiques pour moi.
Fenwick a simplement déclaré que la plage de responsabilité de chaque nœud de l'arbre d'interrogation serait fonction de son dernier bit défini:
Par exemple, comme le dernier bit défini de
6==00110est un "2 bits", il sera responsable d'une plage de 2 nœuds. Pour12==01100, il s'agit d'un "4 bits", il sera donc responsable d'une plage de 4 nœuds.Donc, quand on interroge
F(12)==F(01100), on enlève les bits un par un, en obtenantF(9:12) + F(1:8). C’est loin d’être une preuve rigoureuse, mais je pense que c’est plus évident quand on le place simplement sur l’axe des nombres et non sur un arbre binaire parfait, quelles sont les responsabilités de chaque nœud, et pourquoi le coût de la requête est-il égal au nombre de définir des bits.Si cela n'est toujours pas clair, le document est très recommandé.
la source