Lors de la mise en oeuvre d'une structure de tas, nous pouvons stocker les données dans un tableau de telle sorte que les enfants du nœud en position I sont en position 2i et 2i + 1.
Ma question est pourquoi n'utilisons-nous pas un tableau pour représenter des arbres de recherche binaires et nous traitons plutôt des pointeurs, etc.?
merci
7 Réponses :
Autant que je sache, nous pouvons utiliser un tableau pour représenter des arbres de recherche binaires. Mais il est plus flexible d'utiliser des pointeurs.
Oui, mais vous ne dites rien de l'OP ne savait pas déjà.
Si la position de tous les enfants est précalisée statiquement comme ça, le tableau représente essentiellement un arbre binaire complètement complet et totalement équilibré.
Tous les arbres binaires dans la «vie réelle» sont complètement pleins et parfaitement équilibrés. Si vous devriez avoir quelques branches particulièrement longues, vous devez faire beaucoup plus grand pour accueillir tous les nœuds au niveau le plus bas.
Si un arbre binaire lié au tableau est principalement vide, la majeure partie de l'espace de réseau est gaspillée.
Si seulement certaines des branches de l'arbre sont suffisamment profondes pour atteindre le "fond" de la matrice, il y a aussi beaucoup d'espace perdu.
Si l'arbre (ou une seule branche) doit pousser "plus profond" que la taille de la matrice permettra, cela nécessiterait une "croissance" de la matrice, qui est généralement mise en œuvre comme une copie à un réseau plus grand. Ceci est une opération chronométrique.
Ainsi, l'utilisation des pointeurs nous permet de développer la structure de manière dynamique et flexible. Représentant un arbre dans un tableau est un joli exercice académique et fonctionne bien pour les petits et les cas simples mais ne remplit souvent pas les exigences du calcul "réel".
Et si nous construisons un arbre binaire équilibré? Un tableau serait-il un meilleur choix alors, ou les deux auraient-ils les mêmes? De plus, si la matrice utilisée était redisisable, comme un vecteur en C ++, augmenter la taille de l'arbre ne serait pas un problème, correct?
Je suis totalement d'accord avec le point de mention ci-dessus. J'ai également mis en place un tas basé sur un pointeur. Mon seul préoccupation, tout en interrogant dans le tas (retirez l'index), nous devons rechercher récursivement le dernier élément du tas, pour l'échanger avec la racine, puis bulter la racine. Cette conclusion du dernier élément en cas de mise en œuvre du pointeur prendra du temps linéaire, mais dans la mise en œuvre de la matrice prendra une durée constante. comment pouvons nous résoudre ceci?
@Sabyasachi, pouvons-nous nous souvenir que le dernier pointeur, lorsque nous insérons?
@ Carl-smotricz Pouvez-vous aider avec un exemple de mise en œuvre du tas de vie réelle avec des pointeurs?
personnellement
parce que vous utilisez des pointeurs, il est plus facile de Cultiver la taille de la structure de données Dynamiquement
Je trouve qu'il est plus facile de maintenir la corbeille arbre qu'un tas
Les algorithmes pour équilibrer, éliminer, insérer des éléments dans l'arborescence ne modifieront que les pointeurs et ne pas déplacer ensuite physiquement comme dans un vecteur.
et ainsi de suite ...
Ouais. Les nœuds rotatifs d'un arbre noir rouge ne sont que quelques affectations de pointeur. Dans une mise en œuvre du tableau, ce serait une production énorme.
principalement parce que l'arbre récursif permet un code très simple. Si vous aplatirez l'arborescence dans un tableau, le code devient vraiment complexe car vous devez faire beaucoup de comptabilité que l'algorithme récursif fait pour vous.
En outre, un arbre de hauteur n peut avoir n'importe quoi entre N et 2 ^ (n + 1) -1 nœudes (. Seuls les nœuds réels auront besoin de mémoire. Si vous utilisez un tableau, vous utilisez doit toujours allouer de l'espace pour tous les nœuds (même les vides), à moins que vous n'utilisiez un tableau de race (ce qui rendrait le code encore plus complexe). Donc, alors qu'il est facile de garder un arbre de hauteur 100 à la mémoire, ce serait problématique Pour trouver un ordinateur pouvant allouer 20282409603651670423947251286008 octets de RAM.
Pleinement convenu des besoins en capacité. Pouvez-vous aider avec un bon exemple d'implémentation de tas avec des pointeurs?
Pour insérer un élément dans un tas, vous pouvez le placer n'importe où et l'échanger avec son parent jusqu'à ce que la contrainte de tas soit valide à nouveau. Le swap-with-parent est une opération qui maintient la structure arborescente binaire du tas intact. Cela signifie qu'un tas de taille N sera représenté comme une matrice N-cellules et vous pouvez ajouter un nouvel élément dans le temps logarithmique.
Un arbre de recherche binaire peut être représenté comme une matrice de taille N en utilisant la même structure de représentation qu'un tas (enfants 2n et 2n + 1), mais l'insertion d'un élément de cette manière est beaucoup plus difficile, car contrairement à la contrainte de tas, La contrainte d'arborescence de recherche binaire nécessite des rotations à effectuer pour récupérer un arbre équilibré. Donc, soit que vous réussissez à conserver un arborescent N-noeud dans un réseau N-cellules à un coût supérieur à celui de la logarithmique, ou vous gaspillez de l'espace en gardant l'arborescence dans un tableau plus grand (si ma mémoire sert, un arbre de retour rouge. déchets jusqu'à 50% de votre tableau).
Donc, une arborescence de recherche binaire dans une matrice n'est intéressante que si les données à l'intérieur sont constantes. Et si c'est le cas, vous n'avez pas besoin de la structure de tas (enfants 2n et 2n + 1): vous pouvez simplement trier votre tableau et utiliser Recherche binaire .
La mise en œuvre basée sur la matrice est utile si vous avez besoin d'un tas utilisé comme file d'attente prioritaire dans les algorithmes graphiques. Dans ce cas, les éléments du tas sont constants, vous affichez le plus haut élément et insérez de nouveaux éléments. La suppression de l'élément supérieur (ou du min-élément) nécessite une nouvelle rééquilibrage de devenir un tas à nouveau, ce qui peut être fait de manière à ce que le tableau soit raisonnablement équilibré.
Une référence pour cela est l'algorithme de Goldberg et de Tarjan sur le calcul efficace du flux de réseau optimal dans des graphiques dirigés, IIRC.
La structure de données de tas est un arbre binaire complet contrairement à BST. Par conséquent, l'utilisation de tableaux n'est pas très utile pour BST.